Un défi par semaine

Janvier 2017, 4e défi

Le 27 janvier 2017  - Ecrit par  Ana Rechtman Voir les commentaires (8)

Nous vous proposons un défi du calendrier mathématique 2017 chaque vendredi et sa solution la semaine suivante.

Semaine 4 :

Trouvez un chemin allant de $A$ vers $B$ passant par tous les sommets sans jamais repasser par le même endroit.

PNG - 12.2 ko

Solution du 3e défi de Janvier :

Enoncé

La réponse est $5185$.

Numérotons les lignes du tableau de $0$ à $27$ et les colonnes de $0$
à $36$. Écrivons en rouge les nombres écrits par ligne, et en noir les nombres
écrits par colonne. Par exemple, le nombre gris à la ligne $3$ et à la colonne
$5$ est : $ 1+5+ 3\times 37=117$ et le nombre noir est $1+3+5\times 28=144$.

PNG - 42 ko

De manière générale, le nombre rouge de la ligne $r$ et de la colonne $k$ est
donné par la formule $1+k+37r$ et le nombre noir est donné par $1+r+28k$. Ces deux nombres sont donc égaux si $1+k+37r=1+r+28k$, c’est-à-dire si $36r=27k$ et en simplifiant $4r=3k$. Les valeurs de $r$ sont donc les multiples de $3$ : $0,3,\dots,27$ et celles de $k$ sont alors respectivement $0,4,\dots,36$. Il y a donc $10$ cases dans lesquelles les nombres gris et noirs sont égaux et ils s’écrivent sous la forme :

$1+\frac{4}{3}r+37r=1+4a+111a=1+115a$

où $r=3a$ pour $a=0,\ldots,9.$ On obtient finalement les nombres $1,1+115,1+2\times115+\cdots+1+9\times115$ qui ont pour somme :

$1+ (1+ 115) +\ldots + (1+9 \times 115) = 10 + 115\left (\frac{9\times 10}{2}\right ) = 10 + 115\times 45 = 5185.$

Post-scriptum :

Calendrier mathématique 2017 - Sous la direction d’Ana Rechtman, Maxime Bourrigan - Textes : Antoine Rousseau et Marcela Szopos.
2016, Presses universitaires de Strasbourg. Tous droits réservés.

Partager cet article

Pour citer cet article :

Ana Rechtman — «Janvier 2017, 4e défi» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - Sinclair stammers / SPL-Science photo library / Biosphoto

Commentaire sur l'article

  • Janvier 2017, 4e défi

    le 27 janvier à 08:02, par Bernard Hanquez

    Bonjour,

    Étant au point A, déplaçons nous de :

    1 case vers le bas
    1 case vers la gauche
    1 case vers le bas
    1 case vers la droite
    1 case vers le bas
    2 cases vers la droite
    1 case vers le haut
    1 case vers la gauche
    2 cases vers le haut
    1 case vers la droite
    1 case vers le bas
    1 case vers la droite
    1 case vers le bas

    Nous sommes alors arrivés au point B en étant passés par tous les points sans être repassés au même endroit.

    Répondre à ce message
  • Janvier 2017, 4e défi

    le 27 janvier à 09:17, par ROUX

    Repérer qu’il faut arriver sur B par le haut.
    Ensuite, réfléchir à un codage de la solution.
    BGBDBDDHGHHDBDB.

    Répondre à ce message
  • Janvier 2017, 4e défi

    le 27 janvier à 11:09, par FDesnoyer

    Bonjour,

    il me semble que ce n’est pas un graphe eulérien et qu’il faut essayer de partir de sommets de degrés impairs pour réussir, non ? or A et B sont de degrés pairs...

    amicalement,

    F.D.

    Répondre à ce message
    • Janvier 2017, 4e défi

      le 27 janvier à 13:37, par zgreudz

      Oui mais là on parle des sommets, pas des segments, la solution de Bernard passe par tous les sommets (mais effectivement pas par tous les segments).

      Amicalement

      Z.

      Répondre à ce message
      • Janvier 2017, 4e défi

        le 27 janvier à 17:33, par ROUX

        La mienne aussi ;-).

        Répondre à ce message
        • Janvier 2017, 4e défi

          le 27 janvier à 18:50, par FDesnoyer

          Et oui, je suis tombé dans le piège... mes collègues d’EPS avaient raison

          Amicalement,

          F.D.

          Répondre à ce message
      • Janvier 2017, 4e défi

        le 27 janvier à 19:53, par Niak

        On cherche en effet un chemin hamiltonien, et non eulérien, de A à B. Néanmoins, pour prolonger la remarque, si le graphe de l’énoncé était le line graph d’un graphe G (mais malheureusement ce n’est pas le cas) alors on aurait éventuellement pu déduire un chemin hamiltonien de A à B à partir d’un chemin eulérien de l’arête représentant A à l’arête représentant B dans G.

        Répondre à ce message
  • Janvier 2017, 4e défi

    le 27 janvier à 20:06, par ROUX

    Hum...
    Je vois qu’euler de rien on s’envoie volontiers euler avec Hamilton : eh bah c’est du propre !!!

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM