Un petit fou gourmand et paresseux

[Patastronch]

Logiquement si on note A la proposition "le fou parcourt toutes les cases qu'il peut" et B : "le fou passe par 4 ilots de 2 cases et 16 d'une case"
alors
A=>B

B=>A pour ma part puisque parcourir un ilot c'est parcourir toutes ses cases d'une certaine maniere. Donc le probleme B est une restriction du probleme A (l'ensemble des chemins possible pour B est un sous ensemble de chemins possible pour A). C'est bien la tout le probleme selon moi.

[Imod]

Non tu suppose qu'un coloriage fournit une borne inférieur quoiqu'il arrive pour ta pseudo demo ce qui est justement le sujet de discorde pour ma part.

Es-tu d'accord ?
1°) Il existe un parcours en 34 déplacements .
2°) Tout parcours passe par 15 cases jaunes .

Imod

[Cyril Mar]

Je crois que je suis en mesure d'expliquer pourquoi il ne peut y avoir moins de 33 déplacements (par un autre moyen que celui d'Imod). Pour expliquer qu'il y en a 34, c'est un peu plus long. Si vous m'en laissez la possibilité, j'essaie de vous faire un exposé.

[lapras]

Ca me rappelle une question sur le produit scalaire :
On définie le produit scalaire comme u.v = ||u||*||v||*cos(u,v)
avec cette définition on démontre al kashi, la médiane etc...
mais qu'est ce qui nous dit que si on défini le produit scalaire autrement (mais qui respecte les regles de commutativité, de distributivité sur +, etc....), comment peut on etre sur qu'on va retomber sur nos théoremes ?
Bah la réponse c'est que si je défini quelquechose comme "produit scalaire" et qu'il vérifie telle propriété qui me permettent de démontrer une proposition logique, alors ces propositions sont vraies puisqu'elles sont démontrées... Y'a pas a chercher plus loins !
Ici on a défini un coloriage qui nous prouve quelquechose. Bien sur tu peux choisir un autre coloriage mais ca ne change rien au résultat !

[Cyril Mar]

Bon, tant pis ! (Si vous acceptez, je n'ai pas intérêt à me planter.)

[Cyril Mar]

En partant d'une case du bord (quelle qu'elle soit), on tombe forcément sur une case ayant 3 possibilités de mise en relation. Toutefois, après ce premier déplacement, il n'y a plus que 2 possibilités de déplacement. Nous avons alors, en tous les cas, le choix entre au moins une case ayant 2 possibilités (et une case ayant soit 2 soit 3 possibilités de mise en relation). Or, si nous choisissons de laisser de côté la case (ou l'une des 2 cases) qui n'a (qui n'ont) que 2 possibilités de mise en relation, nous devrons terminer par elle. Sinon quoi, nous devrons compter un déplacement de plus. Cela signifie aussi qu'il est important de ne pas laisser de côté d'autres cases n'ayant que deux possibilités (si le choix se présentait).

Je vous envoie la suite dans un instant.

[Imod]

Pour un parcours en 34 déplacements :

a8-b7-a6-b5-a4-b3-a2-b1-c2-d1-e2-d3-c4-d5-c6-d7-c8-d7-e8-f7-e6-f5-e4-f3-g2-f1-g2-h1-g2-h3-g4-h5-g6-h7-g8

Imod

[Cyril Mar]

Par ailleurs, il y a au commencement deux figures de cas possibles. Tout d'abord, si nous partons d'une case du bord qui n'est pas dans un des coins (en haut à gauche et en bas à droite sur le dessin d'Imod), alors nous devrons forcément utiliser 2 fois chacun des chemins qui mènent aux cases des coins. Par conséquent, le nombre de déplacements total ne peut être inférieur à 33.

Dois-je continuer ?

[Benjamin]

En partant d'une case du bord (quelle qu'elle soit), on tombe forcément sur une case ayant 3 possibilités de mise en relation.

Oui ok.

Toutefois, après ce premier déplacement, il n'y a plus que 2 possibilités de déplacement.

Là je comprends pas :s.

Nous avons alors, en tous les cas, le choix entre au moins une case ayant 2 possibilités (et une case ayant soit 2 soit 3 possibilités de mise en relation). Or, si nous choisissons de laisser de côté la case (ou l'une des 2 cases) qui n'a (qui n'ont) que 2 possibilités de mise en relation, nous devrons terminer par elle. Sinon quoi, nous devrons compter un déplacement de plus. Cela signifie aussi qu'il est important de ne pas laisser de côté un d'autres cases n'ayant que deux possibilités (si le choix se présentait).

Je vous envoie la suite dans un instant.

Non mais laissez tomber. Merci à vous, mais des fois, c'est en s'acharnant que la solution vient encore moins. Je suis sûr que demain matin, je ne me poserai même plus la question lol. Juste une chose, Lapras, tu peux traduire un peu mieux ce que veut dire ta proposition B ?
Encore merci.

[Cyril Mar]

Si vous partez d'une case du bord, vous tombez sur une case qui est en relation avec 3 autres cases. Cependant, une fois sur cette seconde case, il n'y a de choix qu'entre deux chemins. (Vous éviterez de réutiliser le chemin que vous venez d'utiliser ; sinon quoi, il faudra ajouter 1 au nombre des déplacements.) Êtes-vous d'accord ?

[Benjamin]

Si vous partez d'une case du bord, vous tombez sur une case qui est en relation avec 3 autres cases. Cependant, une fois sur cette seconde case, il n'y a de choix qu'entre deux chemins. Êtes-vous d'accord ?

Ben non. En plus après le tout premier déplacement, 4 sont possibles (même si c'est débile, on peut revenir sur ces pas). Et une fois sur la 2ème case, interdisant le retour en arrière, il reste 3 chemins et non pas 2. Définitivement, j'ai du mal. Encore merci, mais laisse mûrir dans ma tête, je suis sûr que ça va venir tout seul

[Patastronch]

Merci à vous, mais des fois, c'est en s'acharnant que la solution vient encore moins.

Non mais qu'on puisse pas le faire en 33 coups je le remet pas en cause. J'avais une démo tres laborieuse pour le prouver mais tellement laide que j'ai pas osé la poster (je prouvais d'abord que 32 coups était impossible et qu'un nombre impaire de coup etait forcément sous-optimal. Donc on arrivait a 34 comme nombre de déplacement minimal vu qu'un chemin en 34 existe). La conclusion d'Imod est evidement juste, ce qui me taraude c'est la démonstration pas la conclusion !

Je me laisse le temps de réfléchir plus longuement sur la démo d'Imod avant de réintervenir, je crois que vous avez mes arguments et j'ai les votre. laissons murir le tout et on en reparle demain ! bonne soirée !

[Cyril Mar]

Ben non. En plus après le tout premier déplacement, 4 sont possibles (même si c'est débile, on peut revenir sur ces pas). Et une fois sur la 2ème case, interdisant le retour en arrière, il reste 3 chemins et non pas 2. Définitivement, j'ai du mal. Encore merci, mais laisse mûrir dans ma tête, je suis sûr que ça va venir tout seul

On cherche bien à comprendre pourquoi le nombre minimal ne peut être inférieur à 34 oui ou non ? Soit vous ne prenez pas le temps de bien me lire, soit je n'ai rien compris.

[Cyril Mar]

Je vous envoie la fin de mon argumentation. Faites-en ce que vous voulez ? Mais, après tout, je le dis ecore, soit je n'ai rien compris, soit vous n'avez pas pris le temps de bien me lire.

Ensuite, si nous choisissons de partir d'une des 2 cases dans les coins, alors nous laissons forcément de côté une case ayant 2 possibilités de mise en relation. Or, nous devons finir par l'autre case dans le coin. Nous aurons donc nécessairement un déplacemnt de plus (soit pas moins de 32 en tout). Or, j'ai dit qu'il était important de ne pas laisser de côté d'autres cases n'ayant que deux possibilités. La case qui vient à l'issue du second déplacement mène automatiquement sur un choix entre une case du bord (n'ayant que 2 possibilités de mise en relation) et une case ayant 3 possibilités. On est obligé de suivre le bord pour éviter de laisser d'autres cases ayant 2 possibilités. Si l'on suit le bord, on terminera le parcours du bord avec la première case ayant 2 possibilités que nous avons laissée de côté. Or, en la laissant de côtés, nous l'avons privée de l'une de ses 2 possibilités de mise en relation. Comme nous n'avons pas terminé le parcours du petit fou, nous devrons passer 2 fois sur la dernière possibilité de mise en relation de cette case. Ce qui nous coûtera un déplacement de plus.

Maintenant, si vous avez des questions, je reste à votre disposition, mais il faudra attendre un peu...

Après, si vous voulez une preuve mathématique, je pense qu'il suffit d'utiliser les outils de la théorie des graphes (avec sans doute des questions de symétrie).

[Cyril Mar]

Et une fois sur la 2ème case, interdisant le retour en arrière, il reste 3 chemins et non pas 2.

D'accord, là, c'est moi qui ne t'ai pas bien lu. Mais, cela n'enlève rien à mon argumentation, qui concerne surtout les cases du bord.

[Benjamin]

Je suis vraiment un âne et un abruti quand je m'y mets. Je suis désolé pour la perte de temps. C'est effectivement enfantin. La démonstration de Imod en est une. Et on peut enlever le dessin, c'est pareil. Je l'avais bien dit que c'était un blocage. Pourquoi, je ne peux pas vous le dire, mais c'est débloqué lol.
Merci,
A +

[lapras]

AH enfin benjamin tu as compris :we: Le coloriage c'est invisible tu peux l'enlever c'est juste pour démontrer quelquechose qu'on l'utilisé.
Reste Patastronch :happy2:

[Benjamin]

AH enfin benjamin tu as compris :we: Le coloriage c'est invisible tu peux l'enlever c'est juste pour démontrer quelquechose qu'on l'utilisé.
Reste Patastronch :happy2:

Oui carrément. En fait, le coloriage, c'est juste pour désigner des cases bien précises qui ont des propriétés particulières complètement indépendantes du coloriage. Je peux mettre toutes les cases de couleurs différentes, la démo est la même. Juste qu'au lieu de dire les cases jaunes, il faudra dire la case verte, bleu, violette.... Vraiment, j'en reviens pas que j'ai bloqué là-dessus :ptdr:

[Patastronch]

Bon j'ai trouvé l'exemple qui va débloquer notre quiproco.



Quelle est la borne qui serait renvoyé par ce coloriage selon vous ? (je sais il est crado).

Comment je comprends la démarche d'Imod je dirais 35 et justement c'est pas une borne. 35 parceque :
Pour effectuer un parcours il faut :
Entrer 7 fois au minimum dans un ilot rouge
Sortir 7 fois au minimum d'un ilot rouge
13 déplacements au minimum pour parcourir l'ilot de taille 10.
6 déplacements au minimum pour parcourir l'ilot de taille 5
2x1 déplacements au minimum pour parcourir les ilots de taille 2
Ce qui ferait un total de 35 déplacements minimum.

Si justement c'est pas 35 la valeur qu'Imod aurait renvoyée c'est qu'il y a un malentendu sur le calcul de la borne et tout risque de s'éclaircir sur le détail du calcul.

[Benjamin]

Bon j'ai trouvé l'exemple qui va débloquer notre quiproco.



Quelle est la borne qui serait renvoyé par ce coloriage selon vous ? (je sais il est crado).

Comment je comprends la démarche d'Imod je dirais 35 et justement c'est pas une borne. 35 parceque :
Pour effectuer un parcours il faut :
Entrer 7 fois au minimum dans un ilot rouge
Sortir 7 fois au minimum d'un ilot rouge
13 déplacements au minimum pour parcourir l'ilot de taille 10.
6 déplacements au minimum pour parcourir l'ilot de taille 5
2x1 déplacements au minimum pour parcourir les ilots de taille 2
Ce qui ferait un total de 35 déplacements minimum.

Si justement c'est pas 35 la valeur qu'Imod aurait renvoyée c'est qu'il y a un malentendu sur le calcul de la borne et tout risque de s'éclaircir sur le détail du calcul.

Ton dessin n'est pas le même, tu ne peux pas faire le même raisonnement que Imod. Le comptage que fait Imod sur son dessin est propre à son dessin. Ce qu'il faut voir, c'est les propriétés des cases sur les bords, et des cases des 2ème/7ème rangées/colones et les propriétés des cases centrales c'est tout. Le dessin ne sert qu'à dire de quoi on parle. Il ne démontre rien.