Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Chemins passant une seule fois à travers chaque carré



  1. #1
    Witten

    Chemins passant une seule fois à travers chaque carré


    ------

    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

    -----

  2. Publicité
  3. #2
    Korgox

    Re : Chemins passant une seule fois à travers chaque carré

    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.
    Dernière modification par Korgox ; 01/06/2006 à 19h49.

  4. #3
    Witten

    Re : Chemins passant une seule fois à travers chaque carré

    Citation Envoyé par Korgox
    -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.

  5. #4
    Gwyddon

    Re : Chemins passant une seule fois à travers chaque carré

    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 quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  6. A voir en vidéo sur Futura
  7. #5
    Witten

    Re : Chemins passant une seule fois à travers chaque carré

    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.

Discussions similaires

  1. fonction dérivable UNE SEULE FOIS dans R...
    Par jecario dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 24/11/2016, 16h49
  2. pic qui lis son programme une seule fois...
    Par Raphael2 dans le forum Électronique
    Réponses: 17
    Dernier message: 11/06/2007, 18h25
  3. [Brun] Ampli Thomson : fusible qui grille à chaque fois
    Par jeyce dans le forum Dépannage
    Réponses: 4
    Dernier message: 06/02/2007, 13h35
  4. Manger une seule fois par jour
    Par Garion dans le forum Maigrir sans régime, c'est possible
    Réponses: 2
    Dernier message: 08/11/2006, 22h27
  5. windows xp ne reconnait plus mon profil et fait un premier redémarrage à chaque fois
    Par temroc dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 07/01/2005, 21h19