Un défi par semaine

Septembre 2021, 3e défi

Le 17 septembre 2021  - Ecrit par  Ana Rechtman Voir les commentaires (3)
Lire l'article en  

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

Le calendrier 2021 est en vente ! Il s’intitule : « Le ciel dans tous ses états ».

De janvier à décembre, à travers 12 textes superbement illustrés, découvrez l’histoire des équations cachées dans les trajectoires des planètes et des étoiles ainsi que le développement des grandes théories qui ont accompagné cette ­aventure.

Semaine 37

Lequel de ces graphes peut-on recouvrir en partant de $A$, en arrivant à $B$ et sans jamais lever le crayon ni passer deux fois par la même arête ?

PNG - 30.1 ko

Solution du 2e défi de septembre :

Enoncé

La réponse est : $375$

Choisissons dix nombres consécutifs autour du cercle et appelons les $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, $i$ et $j$, avec $a$ noir.

On a donc $b=ac$, donc $c=\frac{b}{a}$.

Comme $c=b+d$, on en déduit : $d=c-b=\frac{b(1-a)}{a}$. Comme $d=ce$, on a : $e=\frac{d}{c}=1-a$.

En continuant ces substitutions, on obtient :
\[ \begin{eqnarray*} f & = & e-d\,=\,\frac{(1-a)(a-b)}{a}\\ g & = & \frac{f}{e} \, =\, \frac{a-b}{a}\\ h & = & g-f \,=\,a-b\\ i & = & \frac{h}{g}\,=\,a\\ j & = & i-h \,=\,b. \end{eqnarray*} \]
Il s’ensuit que le motif se répète tous les huit nombres.

Soit $S$ la somme des huit nombres, on obtient :
\[ \begin{align*} S& = a+b+\frac{b}{a} +\frac{b(1-a)}{a} +(1-a) +\frac{(1-a)(a-b)}{a}\\ & \;+\frac{(a-b)}{a}+(a-b)\\ & = a+b+(1-a)+(a-b)\\ & \; + \frac{b+b(1-a)+(1-a)(a-b)+(a-b)}{a}\\ & = 1+a+2-a =3. \end{align*} \]
Comme $1000=8\times 125$, la somme des 1000 nombres est $3\times 125 =375$.

Post-scriptum :

Calendrier mathématique 2021 - Sous la direction d’Ana Rechtman,

Partager cet article

Pour citer cet article :

Ana Rechtman — «Septembre 2021, 3e défi» — Images des Mathématiques, CNRS, 2021

Commentaire sur l'article

  • Septembre 2021, 3e défi

    le 17 septembre à 09:46, par Al_louarn

    Si je parcours mon appartement de la pièce $A$ à la pièce $B$ en passant une fois et une seule par chaque porte, alors forcément :

    • je sors une fois de plus de $A$ que j’y entre
    • j’entre une fois de plus dans $B$ que j’en sors
    • j’entre autant de fois dans toute autre pièce que j’en sors

    Pour que ce soit possible il faut que :

    • les pièces $A$ et $B$ possèdent chacune un nombre impair de portes
    • toutes les autres pièces doivent avoir un nombre pair de portes
      Ajoutons qu’il faut aussi que l’appartement soit d’un seul tenant.

    Dans le langage des graphes nous cherchons un chemin eulérien de $A$ à $B$, ce qui requiert au moins ces $3$ conditions :

    • les sommets $A$ et $B$ doivent être de degré impair
    • tous les autres sommets doivent être de degré pair
    • le graphe doit être connexe

    Les graphes $1$ et $3$ sont éliminés car $B$ y est de degré pair (et ils possèdent de toute façon un sommet intermédiaire de degré $3$).
    Seul le graphe $2$ remplit toutes les conditions et il est facile d’en trouver un parcours solution.

    Par contre je ne sais plus si cette liste de conditions est suffisante dans tous les cas...

    Répondre à ce message
    • Septembre 2021, 3e défi

      le 17 septembre à 12:15, par Niak

      C’est suffisant. Par connexité, il existe un chemin de A à B ne réutilisant pas d’arête. Comme expliqué, un tel chemin utilise un nombre impair d’arêtes en A et B et un nombre pair en tout sommet intermédiaire. En retirant ce chemin, on déconnecte le graphe en composantes connexes où tous les degrés sont pairs. Dans chacune de ces composantes, il existe un cycle eulérien (visitant toutes les arêtes exactement une fois). Chacun de ces cycles est connecté au chemin retiré. On peut, au premier point de connexion venu, faire un détour par le cycle pour visiter la composante oubliée. Ainsi on fabrique un chemin eulérien de A à B.

      Le fait qu’il existe un cycle eulérien lorsque tous les degrés sont pairs se démontre par induction de la même façon. Partons d’un sommet quelconque A et parcourons le graphe de façon quelconque en retirant les arêtes empruntées. Chaque sommet traversé perd 2 arêtes sur un nombre pair, on n’est jamais bloqué jusqu’à revenir en A, le seul à n’avoir perdu qu’une arête au début. Les composants restantes vérifient la même propriété, on leur applique le résultat par induction et on rapièce pour obtenir un cycle eulérien.

      Répondre à ce message
      • Septembre 2021, 3e défi

        le 17 septembre à 15:37, par Al_louarn

        C’est très élégant, merci !

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