Un petit fou gourmand et paresseux

[Imod]

Après la tour , le petit fou :we:

Un petit fou est une pièce d'échec se déplaçant comme un fou mais d'une seule case . Un petit fou est placé dans un coin d'un échiquier , quel est le nombre minimal de déplacement qu'il doit faire pour visiter les 32 cases de l'échiquier qui lui sont accessibles ?

Bon courage :zen:

Imod

[Patastronch]

Avec preuve de minimalité ?

J'ai un parcours avec 34 déplacements, il est évident qu'on peut pas le faire en moins de 31 déplacements. Après pour prouver qu'on peut pas faire mieux ... ben ... je cherche !

[Imod]

34 c'est le top !!! Et maintenant , pourquoi pas moins :zen:

Imod

[Patastronch]

J'arrive a peu près a prouver dans un jargon qui m'est propre qu'on peut pas le faire en moins de 33 déplacements. Après pourquoi on peut pas le faire en 33 déplacements ... je patauge un peu pour le moment :)

[Imod]

Là , pour te citer ( de mémoire ) , une petite figure et une petite phrase et tout est emballé !

Imod

PS: Un petit coloriage pas évident :mur:

[nodgim]

Plus généralement, je dirais que pour un échiquier de 2n*2n cases, le nombre minimal de déplacements est de 2n²+n-2. :happy2:

[Imod]

Je n'ai pas regardé plus loin mais la formule ne marche pas pour n=1 :marteau:

Imod

[nodgim]

Pour n=1, échiquier de 2*2 cases ,donc 2 cases blanches et 2 noires, donc 1 déplacement.

[Imod]

Pour n=1, échiquier de 2*2 cases ,donc 2 cases blanches et 2 noires, donc 1 déplacement.

Tiens oui :error: Je regarde plus en détail !

Imod

[Imod]

En effet ça à l'air de marcher , sûrement par récurrence sur . Je verrai ça demain :dodo:

Imod

[Imod]

La formule 2n²+n-2 donne bien le nombre minimal de déplacement . Pourquoi ne peut-on pas faire mieux ?

Imod

[ffpower]

Avec tous ces exos,va falloir que j investisse dans un echiquier\damier moi^^

[Imod]

Encore un problème sans solution :hum:

Imod

[Imod]

Un petit coloriage à interpréter ( pas facile !!! ) mais quand on a la solution on se cache sous la table



Imod

[Imod]

Bon je donne la solution : vraiment difficile !!!

Il y a 16 îles rouges dont on ne peut sortir que par une case jaune , or il n'y a que 12 cases jaunes .

Imod

[Patastronch]

Bon je donne la solution : vraiment difficile !!!

Il y a 16 îles rouges dont on ne peut sortir que par une case jaune , or il n'y a que 12 cases jaunes .

Imod

Et pourquoi ce coloriage en ilot rouge serait optimal ? Je vois pas ce qui permet de dire que le nombre de déplacements minimal théorique déduit de ce coloriage (34 ici : 15 entrées dans un ilot rouge + 15 sorties d'un ilot rouge + 4 mouvements supplémentaire pour parcourir les ilots rouge de 2 cases) sera une vraie borne inférieur au nombre de déplacement.

Je sais pas si je suis assez clair. Mais si par exemple on considère le coloriage ou les bandes pairs sont jaune et les impair rouge, alors on a 16 ilots rouge avec 16 cases jaune et toujours la meme propriété. Soit un nombre de déplacement minimal théorique de 30 (on va rentrer 15 fois dans un ilot rouge et on va ressortir 15 fois d'un ilot rouge et chaque ilot rouge se parcours en 0 mouvements). On voit donc qu'on peut obtenir une borne différente selon le coloriage choisis. Je me doute bien qu'on peut pas trouver un coloriage qui fournirait une borne inférieure dont la valeur serait strictement supérieur à 34 mais rien ne le prouve. Ce qui manque selon moi c'est la preuve que le chemin optimal dans le "nouveau jeu" créée par un coloriage quelconque de ce type est toujours inférieure à la solution optimale dans le problème initial.

Ou alors j'ai zappé quelque chose dans la puissance de ce coloriage.

[Imod]

L'objectif est de montrer qu'on ne peut pas faire mieux que 34 , c'est tout .

Imod

[Patastronch]

L'objectif est de montrer qu'on ne peut pas faire mieux que 34 , c'est tout .

Imod

Oui mais je suis pas convaincu que ce coloriage fournisse une borne inférieur au problème initial. Voila comment je comprends ta démo :

L'évaluation minimal d'un échiquier colorié vaut ( en supposant que les points d'arrivé et de départ se font sur des îlots rouges ) :
(Nombre d'îlots rouges - 1) * 2 + (Nombre de cases rouge - nombre d'îlots rouge)

Et je ne pense pas qu'on puisse conjecturer aussi facilement que l'évaluation minimal d'un coloriage soit toujours inférieur au nombre de mouvement du chemin optimal de notre problème initial. En fait l'évaluation minimal d'un coloriage ajoute la contrainte qui n'existait pas auparavant que les îlots rouges doivent être parcouru par bloc (c'est a dire qu'un îlot doit être visité entièrement avant d'être quitté). Qu'est ce qui prouve que le chemin optimal de notre problème initial parcours ces îlots par blocs ? Si chaque îlot était réduit a une case on aurait évidement une borne inférieur a notre problème (d'ailleurs 30 est bien une borne inférieur mais inutile ) puisque chaque îlot sera parcouru par bloc (on ne peut pas parcourir une demi case) dans le chemin optimal.

Bon je sais pas si j'ai été clair cette fois ci mais bon, c'est pas trop grave, si tout le monde pense que la démo est correcte c'est que quelque chose doit m'échapper.

[Imod]

Je vais essayer d'être plus clair :zen:

Il y a 16 îles rouges que le fou doit visiter donc il quitte au moins 15 fois une île rouge pour rejoindre une voisine en passant à chaque fois par au moins une case jaune : il rencontre 15 cases jaunes au minimum . Il doit visiter toutes les cases et il y a en tout 20 cases rouges , il parcourt au moins 20+15=35 cases et il doit effectuer au minimum 34 déplacements .

Imod

[Benjamin]

salut,
Je comprends très bien ton raisonnement mais je suis de l'avis Patastronch. Le problème n'est pas là. Tu pars de l'hypothèse que ton dessin représente un coloriage optimal. Mais ça, tu ne le montres pas. Après, si on dit que ton dessin est la situation optimale, alors oui, le décompte du nombre de cases n'est pas très compliqué. Mais l'hypothèse de départ ne me semble absolument pas justifié. Pourquoi as-tu colorié comme ça et pas autrement ? A cette question, tu n'as jamais répondu...