Un petit fou gourmand et paresseux

[Imod]

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...

Il existe un parcours en 34 déplacements comme Patastronch l'a signalé dès son premier message ( je peux en fournir un si on veut ) donc on peut visiter toutes les cases en 34 déplacements . Mon coloriage montre qu'on ne peut pas le faire en moins de 34 déplacements , tout est là et je ne vois pas en quoi je dois justifier d'un caractère minimal pour le coloriage :hum:

Imod

[Benjamin]

Mon coloriage montre qu'on ne peut pas le faire en moins de 34 déplacements , tout est là et je ne vois pas en quoi je dois justifier d'un caractère minimal pour le coloriage :hum:

Imod

Si pour toi c'est une preuve, je n'ai pas compris ta preuve alors, désolé. Je ne dis pas que ça n'en est pas une, juste que j'ai pas compris. Ce qui me pose problème, tu n'as pas montré qu'il n'existait pas d'autres coloriages où le compte des îles et des cases rouges donnait un compte inférieur à 34. Tu as montré qu'il existait une solution de 34 déplacements, ce n'est pas la même chose (à mon sens).

[Imod]

Tu as montré qu'il existait une solution de 34 déplacements, ce n'est pas la même chose (à mon sens).

Justement , non ! J'ai simplement montré me semble-t-il qu'il n'y avait pas de solution en moins de 34 .

Je vais essayer d'être plus clair . Imaginons un parcours de l'ensemble des cases ( l'échiquier n'est pas colorié ) et dis-moi à quel moment je fais erreur :we:

1°) Je dépose sur l'échiquer un calque avec le coloriage précédent et je vois alors le fou passer d'une case coloriée à une autre .
2°) Le fou parcourt les 20 cases rouges qui sont réparties en 16 îles donc il quitte au moins 15 de ces îles en passant à chaque fois par ( au moins ) une case jaune .
3°) Il est passé au minimum par 15 cases jaunes .
4°) Il est passé au minimum par 20 cases rouges +15 cases jaunes =35 cases .
5°) Il a effectué au moins 34 déplacements .

Imod

[Benjamin]

Justement , non ! J'ai simplement montré me semble-t-il qu'il n'y avait pas de solution en moins de 34 .

Je vais essayer d'être plus clair . Imaginons un parcours de l'ensemble des cases ( l'échiquier n'est pas colorié ) et dis-moi à quel moment je fais erreur :we:

1°) Je dépose sur l'échiquer un calque avec le coloriage précédent et je vois alors le fou passer d'une case coloriée à une autre .
2°) Le fou parcourt les 20 cases rouges qui sont réparties en 16 îles

Pour moi, ici il y a une erreur. Et si ton coloriage n'avait que 13 îles ? Ici, tu ne traites qu'un cas, celui de ton coloriage. Quid des autres cas ? En fait, la réponse est que tu ne peux pas construire un coloriage avec moins de 16 îles j'ai l'impression. C'est ça qu'il faut montrer. Si tu me montres qu'il n'existe pas de coloriage présentant moins de 16 îles, je dirais : oui c'est une preuve. Mais pour moi, ça reste vraiment un cas particulier ce que tu fais...

[Patastronch]

Mon coloriage montre qu'on ne peut pas le faire en moins de 34 déplacements
Imod

Justement c 'est la ou je suis pas d'accord, ton coloriage dit qu'on ne peut pas faire en moins de 34 deplacements si on parcours d'un trait chacun des 4 ilots de 2 cases. Mais qui te dis qu'il existe pas un meilleur chemin dans notre probleme qui passerait en 2 temps sur un des 4 ilots de 2 cases ?

Pour ma part rien ne prouve qu'un coloriage quelconque fournisse une borne inférieur a notre probleme dès lors qu'on a des ilots de plus d'une case.

[Imod]

Pour moi, ici il y a une erreur. Et si ton coloriage n'avait que 13 îles ? Ici, tu ne traites qu'un cas, celui de ton coloriage. Quid des autres cas ? En fait, la réponse est que tu ne peux pas construire un coloriage avec moins de 16 îles j'ai l'impression. C'est ça qu'il faut montrer. Si tu me montres qu'il n'existe pas de coloriage présentant moins de 16 îles, je dirais : oui c'est une preuve. Mais pour moi, ça reste vraiment un cas particulier ce que tu fais...

Oui mon coloriage est un cas particulier et j'aurais pu colorier autrement . Quand en géométrie on construit une bissectrice ou une parallèle pour établir un résultat , on ne justifie pas pourquoi on l'a fait parce que le tracé ne change en rien la validité de la conclusion . Mon coloriage montre qu'il faut au moins 34 déplacements , tu peux enlever ou changer le coloriage le résultat est toujours là .

Je ne mets pas de mauvaise volonté mais je ne vois pas où est le problème , pour moi c'est de la logique élémentaire :mur:

Imod

[lapras]

Bonjour
je suis entierement d'accord avec le raisonnement d'Imod, le coloriage est superficiel , on peut l'enlever ou bien le mettre mais il est juste un outil pour faire la démonstration, enfin ca me semble logique.

[Imod]

Justement c 'est la ou je suis pas d'accord, ton coloriage dit qu'on ne peut pas faire en moins de 34 deplacements si on parcours d'un trait chacun des 4 ilots de 2 cases. Mais qui te dis qu'il existe pas un meilleur chemin dans notre probleme qui passerait en 2 temps sur un des 4 ilots de 2 cases ?

Je n'ai jamais dit que chaque ilot devait être visité complètement en une fois mais simplement qu'il fallait bien débarqué sur chaque ilot pour le visiter ( à la limite on peut très bien débarquer plusieurs fois sur le même ilot ) donc qu'il fallait passer par 15 cases jaunes .

Imod

[Patastronch]

Bonjour
je suis entierement d'accord avec le raisonnement d'Imod, le coloriage est superficiel , on peut l'enlever ou bien le mettre mais il est juste un outil pour faire la démonstration, enfin ca me semble logique.

Je me repete mais avoir un ilot de plus d'une case impose des mouvements obligatoire. Donc la borne fournit est une borne pour tous les chemins prenant en compte ces mouvements imposés et non dans l'ensemble des chemins possible.

[Imod]

Le coloriage n'impose rien , c'est un outil pour décrire le parcours .

Imod

[Benjamin]

Moi non plus, je ne mets pas de mauvaise volonté, je t'assure. Quand on établie un résultat géométrique, il y a souvent des chiffres derrières (un angle etc...) et surtout, on précise souvent : dans le cas où blablabla... les calculs se déroulent de la même façon.

Une bissectrice coupe un angle en 2 et a certaines propriétés bien précises.

Ce qu'on veut montrer c'est : On appelle un chemin le trajet suivi par le fou pour parcourir toutes les causes de l'échiquier. Le chemin minimal a une taille de 34.

Voilà comment je vois les choses :
Il existe un chemin de taille 34 (ton dessin le prouve, je suis ok avec ça, mais pour moi, ton dessin est juste la preuve qu'il existe un chemin de 34 mouvements).

Supposons qu'il existe un chemin de taille plus petite,
Alors.... (tu peux t'appuyer sur des propriétés de ton dession pour avancer, ça ne me generait pas) donc .... (une contradiction)
Donc il n'existe pas de chemin de taille inférieure à 34.

Raisonnement par l'absurde. Si tu me complétes les pointillés, où que tu me montres vraiment qu'il n'existe pas de plus petit chemin, je serais d'accord. Désolé si je t'ennuie, c'est vrai pas le but, mais là, je fais un blocage total. Ca se trouve que c'est tout con en plus :mur: :mur:

[Imod]

Reprenons calmement :bad:

Je n'ai jamais montré qu'il existait un parcours en 34 déplacements JAMAIS . J'ai simplement dit que si je pose mon coloriage sur un parcours de petit fou je vois celui-ci passer par au moins 15 cases jaunes et 20 cases rouges : C'est tout .

Imod

[Patastronch]

Le coloriage n'impose rien , c'est un outil pour décrire le parcours .

Imod

Ok imaginons le coloriage fictif suivant ou on aurait 16 ilots dont 5 de 2 cases. Je ne sais pas si il est possible (surement que non). Dans ce cas on aurait une borne de 35 qui serait fausse. Mon doute repose justement la dessus, en quoi un coloriage quelconque permet de s'assurer qu'il fournira bien une borne.

[lapras]

Ok imaginons le coloriage fictif suivant ou on aurait 16 ilots dont 5 de 2 cases. Je ne sais pas si il est possible (surement que non). Dans ce cas on aurait une borne de 35.

Il n'existe pas.
Preuve : le coloriage de Imod existe et il existe une situation ou 34 déplacements conviennent.

[Patastronch]

Il n'existe pas.
Preuve : le coloriage de Imod existe et il existe une situation ou 34 déplacements conviennent.

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.

[lapras]

On s'heurte a un probleme de logique là (je ne peux pas prouver que la mienne est bonne, ni que la tienne est bonne)... Va falloir formaliser le probleme mathématiquement pour que vous soyez convaincu.

[Benjamin]

Reprenons calmement :bad:

Je n'ai jamais montré qu'il existait un parcours en 34 déplacements JAMAIS . J'ai simplement dit que si je pose mon coloriage sur un parcours de petit fou je vois celui-ci passer par au moins 15 cases jaunes et 20 cases rouges : C'est tout .

Imod

Oui c'est vrai, tu as parfaitement raison, pardon. Tu as montré qu'avec ton coloriage, le déplacement optimal était de 34. Je me suis mal exprimé. Je suis d'accord avec ça depuis le début en fait :error:
Là où je bloque, c'est pourquoi avec tous les autres dessins possible, on tombera toujours sur 34. En fait, je suis exactement comme Patastronch. Le dessin d'Imod montre que le minimum de déplacement est 34. Mais pourquoi pas un autre dessin ? Si le formalisme dont parle Lapras est trop lourd à mettre en place, laissez tomber. Mais c'est vrai que j'en aurai besoin là :hum:

[lapras]

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

[Benjamin]

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.

Lapras a raison là. C'est bien une preuve au fait que le dessin que tu proposes n'existe pas. Si il existait, alors le minimum serait de 35. Or, on sait grâce au dessin d'Imod que le minimum est inférieur à 34. Absurde. Donc, un tel dessin n'existe pas.

[Benjamin]

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

Je ne comprends pas ta proposition B. Une île, si je me souvient bien le problème, c'est une case rouge qui est entouré que de jaune. Une ile de 2 cases, j'ai du mal du coup. Ensuite, mais ca c'est un détail, il faudrait rajouter : "au moins" : le fou passe par au moins. Si tu me dis ce que tu appelles ilots, je comprendrais surement (enfin j'espère lol)