Exercice 3 — Énoncé — Olympiades 2016 Versailles

Sujet

Neuf personnes sont assises autour d'une table. Un sac contient 8 pièces de 1 euro et 8 pièces de 2 euros. On pose devant chaque personne une pièce prise au hasard dans le sac.
On demande dans un premier temps à chaque personne ayant reçu une pièce de 2 euros de la donner à son voisin de gauche. Dans un second temps, chaque personne ayant reçu une pièce de 1 euro doit la donner au voisin de droite de son voisin de droite.

Exemple :

Distribution initiale

Passage des «2 euros » à gauche

Passage des << 1 euro >> 2 fois à droite

On reprend l'exemple précédent, en remplaçant les pièces de 1 euro par des pièces de 2 euros et vice-versa. Quelle distribution obtient-on après les deux mouvements de pièces?
a) Montrer que si une personne, son voisin de droite et son voisin de gauche ont chacun reçu une pièce de 2 euros, un des participants au moins est démuni à l'issue des mouvements.
b) Quelles sont les distributions initiales qui permettent que chaque personne ait une pièce à l'issue des mouvements?

On procède de la même façon avec 10 personnes attablées et un sac contenant 9 pièces de 1 euro et 9 pièces de 2 euros. On fait l'hypothèse qu'après les deux temps de redistribution, chaque personne a au moins une pièce devant elle.
3. a) Montrer que deux voisins ne peuvent pas avoir chacun une pièce de 2 euros.
b) Montrer qu'il est impossible qu'une personne, son voisin de droite et son voisin de gauche aient chacun une pièce de 1 euro.
c) Montrer que toute personne ayant une pièce de 1 euro ne peut pas être entourée de voisins ayant chacun une pièce de 2 euros.
d) Conclure quant à la validité de l'hypothèse «après les deux temps de redistribution, chaque personne a au moins une pièce devant elle».

Distribution obtenue après les deux mouvements de pièces?

Distribution initiale

Passage des « 2 euros » à gauche

Passage des « 1 euro» deux fois à droite

a) Supposons que \(\mathrm{A}, \mathrm{B}\) et C aient reçu chacun une pièce de 1 euro. Lors des échanges, la pièce détenue par A va à C , celle détenue par B va à D . Si D avait au départ une pièce de 2 euros, elle est passée à C , qui a donc deux pièces à l'issue des échanges. Donc, s'il n'y a pas de «trou», D avait au départ une pièce de 1 euro. De proche en proche, on en déduit que toutes les pièces distribuées étaient des pièces de 1 euro.
Supposons que A et B aient reçu une pièce de 1 euro, et que C et I ont reçu une pièce de 2 euros. Lors des échanges, C reçoit la pièce de 1 euro de \(\mathrm{A}, \mathrm{D}\) celle de \(\mathrm{B}, \mathrm{B}\) reçoit la pièce de 2 euros de C . Si D avait reçu une pièce de 2 euros, elle serait passée à C , qui aurait ainsi 2 pièces. Donc D a reçu une pièce de 1 euro, qu'il a donnée à F . Si E avait reçu une pièce de 2 euros, elle serait passée à D , qui en aurait deux. Donc E a reçu une pièce de 1 euro.
A doit avoir reçu une pièce de 1 euro, qui lui vient donc de H . H reçoit la pièce de 2 euros de I . Mais alors I doit recevoir une pièce de 1 euro, qui lui vient de G . Il ne reste que F à munir, d'ne pièce de 2 euros, le 1 euro étant interdit par ce qui précède.

	I	H	G	F	E	D	C	B	A
Début	2	\(\mathbf{1}\)	\(\mathbf{1}\)	2	\(\mathbf{1}\)	\(\mathbf{1}\)	2	1	1
Echange	\(\mathbf{1}\)	2	1	1	2	1	1	2	\(\mathbf{1}\)

Se peut-il qu'une personne ayant reçu une pièce de 1 euro soit entourée de voisins possédant chacun une pièce de 2 euros ? Le tableau suivant procède à une discussion analogue à celle qui précède :

	I	H	G	F	E	D	C	B	A
Début	2	\(\mathbf{2}\)	\(\mathbf{1}\)	2	2	\(\mathbf{1}\)	\(\mathbf{2}\)	2	1
Echange	\(\mathbf{1}\)	2	\(\mathbf{2}\)	\(\mathbf{1}\)	2	2	1	\(\mathbf{2}\)	2

Les distributions qui ne conduisent pas à des « trous» sont faites de paires de pièces de 2 euros séparées par des pièces de 1 euro ou de paires de pièces de 1 euro séparés par des pièces de 2 euros.
b) Quelles sont les distributions initiales qui permettent que chaque personne ait une pièce à l'issue des mouvements?