Défis du calendrier mathématique Retour à la rubrique

Un défi par semaine

Septembre 2021, 4e défi

Le 24 septembre 2021 - Ecrit par Ana Rechtman Voir les commentaires (5)
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 38

Trois piles ont $11$, $7$ et $6$ pièces. Un jeu consiste à déplacer des pièces d’une pile à une autre de sorte qu’à chaque mouvement, une pile double son nombre de pièces et une seule pile diminue son nombre de pièces. Quel est le nombre minimal de mouvements à faire pour obtenir trois piles égales ?

Solution du 3e défi de septembre :

Enoncé

La réponse est : le graphe $2$.

Observons tout d’abord que c’est possible pour le graphe $2$ : il suffit de partir de $A$, de recouvrir tout le contour extérieur du graphe pour revenir en $A$ puis de recouvrir les deux diagonales pour arriver en $B$.

Montrons maintenant que c’est impossible pour les graphes $1$ et $3$. Cela est dû au fait qu’il doit nécessairement y avoir un nombre impair d’arêtes qui partent du sommet $B$.

En effet, quand on recouvre le graphe, à chaque fois que l’on passe par $B$ sans s’y arrêter, on recouvre exactement deux arêtes partant de $B$ et, comme on doit finir en $B$, cela rajoute une arête supplémentaire, ce qui nous donne bien un nombre impair d’arêtes partant de $B$. Or, pour les graphes $1$ et $3$, il y a respectivement deux et quatre arêtes partant de $B$, ce qui rend impossible le recouvrement.

Remarque : en utilisant le même raisonnement, on montre facilement qu’une condition nécessaire pour pouvoir recouvrir un graphe en partant de $A$, en arrivant en $B$, sans jamais lever le crayon ni passer deux fois par la même arête, est que des sommets $A$ et $B$, il parte un nombre impair d’arêtes et que de chacun des autres sommets, il parte un nombre pair d’arêtes.

Si, en revanche, on veut tracer le graphe en partant d’un sommet $A$ et en finissant au sommet $A$, il faut que de chaque sommet parte un nombre pair d’arêtes. Un célèbre théorème d’Euler affirme que ces conditions sont suffisantes.

Post-scriptum :

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

Commentaire sur l'article

Septembre 2021, 4e défi

le 24 septembre à 08:00, par ROUX

11 7 6
11 1 12
10 2 12
8 4 12
8 8 8

4 mouvements.
Répondre à ce message

Septembre 2021, 4e défi

le 24 septembre à 08:42, par Al_louarn

En $3$ mouvements :
$11,7,6$
$4,14,6$
$4,8,12$
$8,8,8$

Pour montrer que cette solution est optimale, considérons l’opération inverse qui consiste à déplacer la moitié d’une pile sur une autre. Partant de $8,8,8$, au premier mouvement inverse on remonte forcément à $4,8,12$ dont tous les nombres sont multiples de $4$. Au deuxième mouvement inverse on va donc déplacer $2$ pièces et obtenir $3$ nombres pairs. Il est donc impossible de remonter à $11,7,6$ en deux mouvements.
Répondre à ce message

Septembre 2021, 4e défi

le 24 septembre à 08:47, par Al_louarn

Oups, je voulais dire :

Au deuxième mouvement inverse on va donc déplacer un nombre pair de pièces et obtenir $3$ nombres pairs.
Répondre à ce message
Septembre 2021, 4e défi

le 24 septembre à 12:40, par ROUX

@ Al_Louarn
Bravo et la démonstration de l’optimisation est si simplement belle 😊😊😊
Merci !
Répondre à ce message

Septembre 2021, 4e défi

le 24 septembre à 08:47, par pogarreau

Allez, cherchez un peu plus :-), y’a une solution en 3 mouvements
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.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Ana Rechtman

Un défi par semaine

Septembre 2021, 4e défi

Solution du 3e défi de septembre :

Commentaire sur l'article