Un défi par semaine

Janvier 2017, 4e défi

Le 27 janvier 2017  - Ecrit par  Ana Rechtman Voir les commentaires (8)
Lire l'article en  

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 rouge à 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 rouges 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.

Article édité par Ana Rechtman

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

Voir tous les messages - Retourner à l'article

  • Janvier 2017, 4e défi

    le 27 janvier 2017 à 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

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é ?