Défis du calendrier mathématique Volver a la sección

Un défi par semaine

Septembre 2021, 3e défi

El 17 septiembre 2021 - Escrito por Ana Rechtman Ver los comentarios (3)
Leer el artículo 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?

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,

Comentario sobre el artículo

Septembre 2021, 3e défi

le 17 de septiembre de 2021 à 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 de septiembre de 2021 à 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 de septiembre de 2021 à 15:37, par Al_louarn

C’est très élégant, merci !
Répondre à ce message

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexión | inscribirse | ¿contraseña olvidada?

El autor

Ana Rechtman

Un défi par semaine

Septembre 2021, 3e défi

Solution du 2e défi de septembre :

Comentario sobre el artículo