|
REIMS N°1 La
carte restante. On
réalise la manipulation suivante avec une pile de n cartes numérotées de 1 à
n, la carte du dessus portant le numéro 1, la suivante le numéro 2,… On
prend la première carte de la pile, on la met à la dernière place de la pile,
on prend la suivante et on la retire du jeu, on renouvelle ces opérations
jusqu'au moment où il ne reste plus qu'une carte dans le paquet. On
se demande quel est le numéro de la carte restante. |
|
Répondre
à la question si n est une puissance de 2, puis dans le cas général.
Quelles sont les valeurs de n telles que la carte restante porte le numéro treize?
Solution.
La calculatrice va nous permettre, à l'aide d'un programme d'essayer plusieurs cas et d'émettre une conjecture.
Solution.
Commençons par prendre n = 25 et regardons ce qui nous reste après chaque "tour".
Départ: L0 = {1;2;3;4;…;22;23;24;25} 25 éléments
L1 = {1;3;5;7;…;21;23;25} 13 éléments
L2 = {3;7;11;15;19;23} 6 éléments
L3 = {3; 11;19} 3 éléments
L4 = {3; 19} 2 éléments
L5 = {19}
Remarquons que:
Pour passer de Ln à Ln+1, on prend un terme sur deux de la première.
Si Ln et Ln+1 se terminent par
le même nombre, le premier nombre de Ln+2 est le deuxième de
Ln+1
Si Ln et Ln+1 ne se terminent pas par le même nombre, le premier nombre de Ln+2 est le premier de Ln+1
Créons un programme utilisant cet algorithme:
Appliquons ce programme à quelques exemples et notons le résultat r:
|
n |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
|
r |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
1 |
3 |
5 |
7 |
9 |
11 |
On constate que si n est une puissance de 2, la dernière carte a le numéro 1, et si n est de la forme 2k + m, alors le numéro restant est 2m+1.
Justification.
Si n est une puissance de 2, toutes les listes de notre essai précédent auront un nombre pair d'éléments (sauf la dernière) donc elles se termineront toutes par des éléments différents (car on ne garde que les éléments de rang impair de la liste précédente), donc elles commenceront toutes par le même élément, c'est à dire 1.
Si n est de la forme 2k + m, il suffit d'enlever m éléments de la liste de départ pour se retrouver dans le cas précédent, le premier de la liste sera alors le numéro 2m+1.
Télécharger la solution au format RTF:
reims.rtf(331k)
