Chemins passant une seule fois à travers chaque carré

[invited927d23c]

Bonjour,

Aujourd'hui je suis tombé sur quelque chose de bizzare. J'ai tracé 25 petits carrés qui forme un grand carré, et j'ai essayé de trouver un chemin qui passent une unique fois par chaque petit carré et qui termine à la case départ.
Quand on se trouve sur une case on a droit de bouger vers la gauche/droite/haut/bas, mais seulement si c'est possible, si on se trouve au bord on ne revient pas de l'autre côté.

Après pas mal de temps de recherche en vain j'ai conclu que ce n'était pas possible pour un nombre impair de case (mais j'en sais rien). Le programme que j'ai écrit n'a rien trouvé non plus.

Est-ce qu'il y a une explication mathématique à ça?

Merci
-----

[invite14ea0d5b]

Salut,

je crois même qu'il y a une explication simple :

tu as 4 mouvements à disposition haut (H) bas (B) gauche (G) et droite (D).

-première remarque : tu dois faire exactement autant de G que de D, et de H que B; ceci afin de revenir à la case départ.

-deuxième remarque : à chaque fois que tu effectues un mouvement, tu couvre une nouvelle case. Tu dois donc faire autant de mouvement qu'il y a de carrés.

Alors c'est clair que pour un nombre impair de cases, c'est pas possible : par la première remarque tu dois faire un nombre pair de mouvement horizontaux + un nombre pair de mouvement verticaux. Tu dois donc faire un nombre pair de mouvements. Et par la deuxième tu dois faire un nombre impair de mouvement. Donc c'est pas possible.

La prochaine étape serait de montrer que pour un carré de côté pair, c'est toujours possible. Mais en fait c'est trivial, on voit tout de suite le chemin à prendre et il se généralise pour n'importe quelle taille de carré.

EDIT:

en fait depuis là c'est autant facile de montrer que si t'as une grille rectangulaire de taille m x n, alors il existe un tel chemin fermé ssi m ou n est pair.

[invited927d23c]

-première remarque : tu dois faire exactement autant de G que de D, et de H que B; ceci afin de revenir à la case départ.

Bien vu . J'y aurais pas pensé, et en effet ça devient très logique qu'il n'existe pas de solution .

Je me sens bête là .

En fait, je suis tombé sur ce problème en réfléchissant au problème du voyageur de commerce . Bon il va falloir que je change un peu mon idée d'algorithme.

[invite9c9b9968]

Chouette ! Tu as retrouvé l'adresse du défi auquel j'ai participé (même si on ne me voit pas parmi les concurrents, vu que je n'ai pas envoyé le code)

Le site était mort une semaine avant mon passage en oral

[A voir en vidéo sur Futura]

[invited927d23c]

Chouette ! Tu as retrouvé l'adresse du défi auquel j'ai participé (même si on ne me voit pas parmi les concurrents, vu que je n'ai pas envoyé le code)

Au moins cette discussion aura servi à quelque chose .

Après avoir obtenu des résultats acceptables par des méthodes classiques, j'essaye des algorithmes complétement different. Si j'arrive à faire marcher celui que je suis entrain de développer (sais pas si il existe déjà) et qu'il donne de bon résultat je te le dis.