Exercice 3 — Énoncé — Olympiades 2012 Amiens

Sujet

Un magicien présente un jeu non truqué de 21 cartes. Un spectateur choisit une carte, qu'il mémorise mais ne révèle pas, et remet la carte choisie n'importe où dans le tas de cartes.
Le magicien procède alors à une opération simple, décrite dans l'algorithme suivant : Il forme trois tas de cartes, dans lesquels sont distribuées les 21 cartes. Chaque tas reçoit donc une carte à tour de rôle, face visible.
Une fois que les trois tas ont été formés, le spectateur désigne le tas contenant sa carte. Le magicien prend alors un des tas qui ne contiennent pas la carte du spectateur, met le tas désigné au-dessus, suivi du troisième tas.

Après que cette opération a été effectuée, combien de cartes au minimum sont sous la carte choisie par le spectateur? Combien au minimum sont au dessus?
Le magicien répète l'opération une seconde fois. Combien de cartes au minimum sont sous la carte choisie par le spectateur? Combien au minimum sont au dessus?
L'opération est répétée une troisième et dernière fois. Montrer que la carte choisie par le spectateur ne peut être que dans une seule position dans le tas de cartes, et préciser cette position.

Chacun des 3 tas contient 7 cartes. Après la première opération, il y a donc au minimum 7 cartes en dessous, et 7 au dessus.
Les 7 premières cartes que le magicien dépose sont forcément mauvaises. Cela permet déjà de constituer 3 tas de 2 cartes (l'un des 3 recevant la \(7^{\text {ème }}\) carte).
Si la bonne carte se trouve en \(8^{\text {ème }}\) ou \(9^{\text {ème }}\) position, elle sera posée sur un tas de 2 cartes.
Si elle est en \(10^{\text {ème }}, 11^{\text {ème }}\) ou \(12^{\text {ème }}\) position, elle sera posée sur un tas de 3 cartes.
Et si elle est en \(13^{\text {ème }}\) ou \(14^{\text {ème }}\) position, elle sera posée sur un tas de 4 cartes.
(on rappelle que la bonne carte se trouve entre la position \(\mathrm{n}^{\circ} 8\) et la \(\mathrm{n}^{\circ} 14\) )
Le magicien dépose alors les 7 dernières cartes.
Lorsqu'il superpose les 3 tas lors de la \(2^{\text {ème }}\) opération, il y a donc au minimum 9 cartes en dessous, et 9 au-dessus de la bonne (les 7 cartes d'un mauvais tas, plus les 2 issues de la distribution des 7 premières ou dernières cartes, mauvaises elles aussi).
Le magicien recommence alors son opération.

La bonne carte est située en \(\mathrm{n}^{\circ} 10,11\) ou 12 .
Il dépose les 9 premières cartes, en 3 tas de 3 cartes.
Il dépose ensuite les cartes \(10,11,12\), ce qui forme la \(4^{\text {ème }}\) couche de cartes. La bonne carte est donc l'une d'entre elles.
Enfin, il dépose les 9 autres cartes, mauvaises, pour former les 3 dernières couches. La bonne carte se trouve donc exactement au milieu d'un des paquets, et lorsque le magicien superpose les tas pour reconstituer le jeu de 21 cartes, la bonne reste au milieu du jeu.
Il n'a plus qu'à la sortir, de manière évidente.