Résolution de l'enigme 2
Les trouveurs !
L’énigme 2 a été résolue par Thibault Hervier, Clément Arnould et Samy Vincent.
Félicitations !
Ci-dessous, l’énoncé de l’énigme est rappelée, puis les démarches de nos trois chercheurs sont présentées.
Vous trouverez également en lien le détail des résolutions de Samy et Thibault.
Énoncé
Aurore écrit sur un tableau tous les entiers de 1 à 2019.
Puis elle en sélectionne deux au hasard (a et b), les efface et écrit à la place le nombre max(a ;b)-min(a ;b).
Elle recommence l’opération jusqu’à n’avoir plus qu’un seul entier au tableau.
Le dernier nombre écrit au tableau est 3.
Montrer qu’Aurore s’est trompée dans ses opérations.
max(a ;b) désigne le plus grand des deux nombres a et b. min(a ;b) le plus petit des deux.
Exemple de partie
Effectuons une partie de ce jeu en n’écrivant au départ que les entiers de 1 à 9.
On écrit les entiers de 1 à 9 : 1, 2, 3, 4, 5, 6, 7, 8, 9.
On choisit deux entiers au hasard (par exemple 9 et 7), on les efface et on écrit 9-7 : 1, 2, 2, 3, 4, 5, 6, 8.
On choisit deux entiers au hasard (par exemple 2 et 2), on les efface et on écrit 2-2 : 0, 1, 3, 4, 5, 6, 8.
On choisit deux entiers au hasard (par exemple 3 et 6), on les efface et on écrit 6-3 : 0, 1, 3, 4, 5, 8.
... à vous de poursuivre.
Recherche d’une idée
Samy et Clément ont tous les deux commencé par rechercher des pistes en simulant une partie du jeu d’Aurore à l’aide d’un programme Python.
Un exemple de programme en langage Python :
from random import randint # pour des tirages au hasard
def une_partie(n):
"""
n désigne un entier naturel> 1.
La fonction mène une partie du jeu d'Aurore
et renvoie le dernier nombre écrit au tableau.
"""
# on écrit au tableau les nombres de 1 à n
tableau = [i for i in range(1,n+1)]
# boucle du jeu:
while len(tableau)>1: # tant qu'il reste plus d'un nombre au tableau
# on choisit un nombre au hasard sur le tableau et on l'efface:
a = tableau.pop(randint(0, len(tableau)-1))
# idem avec un second nombre:
b = tableau.pop(randint(0, len(tableau)-1))
# on écrit sur le tableau max(a,b)-min(a,b), c'est à dire valeur_absolue(b-a):
tableau.append(abs(b-a))
# on renvoie le nombre unique obtenu en fin de partie:
return tableau[0]
print(une_partie(2019))
En relançant un grand nombre de fois la simulation, on constate que tous les nombres de fin de partie obtenus sont des nombres pairs.
Cela permet de conjecturer que le résultat final est certainement pair (ce qui interdit le nombre 3 en résultat final).
Samy vous propose également dans son fichier html un script javascript (qui s’exécutera donc dans votre navigateur) pour observer cela directement.
Il reste à trouver un argument prouvant cette conjecture.
Des résolutions
L’argument de Thibault Hervier et de Samy Vincent
La somme S des entiers de 1 à 2019 est égale 2 039 190.
Lorsqu’on efface deux nombres a et b (a ≤ b) et qu’on ajoute b−a, la somme devient S’ = S−a−b+(b−a), soit S’ = S − 2a. On enlève un nombre pair (2a) à un nombre pair (S). Le résultat est pair.
On peut recommencer le raisonnement avec la nouvelle somme S’ puis recommencer encore et encore, jusqu’à la fin.
On obtient donc que la dernière somme (qui est égale à l’unique nombre restant au tableau) est paire. Le dernier nombre ne peut donc pas être impair.
L’argument de Clément Arnould
Au départ, il y a 1010 nombres impairs écrits au tableau (1, 3, 5, 7, ..., 2019).
Si on choisit deux nombres pairs a et b (a ≤ b), la différence b-a est paire. On n’enlève pas d’impair et ne remet pas d’impair. Le nombre d’impairs n’est pas modifié.
Si on choisit un pair et un impair, la différence b-a est impaire : on enlève un impair et on remet un impair. Le nombre d’impairs n’est pas modifié.
Si on choisit deux impairs, la différence est paire. Le nombre d’impairs est diminué de deux.
Dans tous les cas, on constate que la parité du nombre d’impairs n’est pas modifiée.
A la fin, il ne peut donc pas rester le nombre 3 car alors on aurait un nombre impair d’impairs alors qu’au départ le nombre d’impairs était pair.
Remarque.
Clément précise que pour compter facilement les impairs au début, on peut faire des paquets de 2 : 1,2 ❙ 3,4 ❙ 5,6 ❙ 7,8 ❙ ... ❙ 2017, 2018 ❙ 2019, (2020). Le nombre d’impairs est donc 2020/2.
Ci dessous la solution de Sami en HTML
2ème énigme :
Les nombres au tableau
Aurore écrit sur un tableau tous les entiers de 1 à 2019.
Puis elle en sélectionne deux au hasard (a et b), les efface et écrit à la place le nombre max(a;b)-min(a;b).
Elle recommence l'opération jusqu'à n'avoir plus qu'un seul entier au tableau.
Le dernier nombre écrit au tableau est 3.
Montrer qu'Aurore s'est trompée dans ses opérations.
• max(a;b) désigne le plus grand des deux nombres a et b. min(a;b) le plus petit des deux.
• Une piste: raisonner avec la somme des nombres écrits au tableau.
Pour avoir une idée du résultat que nous devrions obtenir, on peut tout d'abord programmer l'énigme pour simuler un grand nombre de parties et voir si les résultats qu'on obtient ont certaines caractéristiques.
Dernier nombre au tableau pour les parties :
On remarque qu'avec 2019, le dernier nombre est toujours pair, ce qui nous amène effectivement à penser qu'Aurore a fait une erreur.
► Résolution :
Soit T l'ensemble des nombres écrits au tableau. On a T = {1 ; 2 ; 3 ; ... ; 2018 ; 2019}.
Soient x1 et x2 les 2 nombres pris au hasard au tableau. On a x1, x2 \(\in\) T2 tels que x1 ⩽ x2.
Pour résoudre le problème, on peut faire la somme de tous les éléments de T, puis soustraire 2 nombres au hasard, et ajouter leur différence.
La première fois, on a : \(\displaystyle \sum_{i=1}^{2019} i\) - x1 - x2 + (x2 - x1) = \(\displaystyle \sum_{i=1}^{2019} i\) - 2x1
On définit alors l'ensemble T', qui correspond aux nombres qu'il reste au tableau. C'est donc l'ensemble T privé de x1 et x2, auquel on a ajouté (x2 - x1). La somme de tous les éléments de T' est donc le résultat trouvé ci-dessus.
A nouveau, on choisit 2 nombres au hasard qu'on soustrait à la somme des éléments de T, et on ajoute la différence des 2 nombres.
Soient x3 et x4 ces 2 nombres tels que x3 ⩽ x4.
On a : \(\displaystyle \sum_{i=1}^{2019} i\) - 2x1 - x3 - x4 + (x4 - x3) = \(\displaystyle \sum_{i=1}^{2019} i\) - 2x1 - 2x3
On continue ainsi jusqu'à ce qu'il ne reste plus qu'un nombre dans l'ensemble, qui correspond au nombre restant au tableau.
A chaque fois qu'on fait cette opération, on enlève un nombre pair à la somme des nombres au tableau (2xn est toujours pair). La parité du résultat final dépend donc de la somme des nombres du tableau au tout départ, donc dans notre cas, de la somme de 1 à 2019. Or \(\displaystyle \sum_{i=1}^{2019} i\) = 2 039 190, qui est pair. Donc on va à chaque opération lui enlever un nombre pair, et la différence de 2 pairs est toujours paire (on l'a démontrée dans la 1ère énigme). En conséquence, le dernier nombre restant devrait lui aussi être pair, ce qui nous assure qu'Aurore s'est trompée en trouvant 3.
Par Samy VINCENT