Exercice 1 — Un problème de tas — Olympiades 2007 Nantes

Sujet

On dispose de 7 objets que l'on répartit en autant de tas que l'on veut, chaque tas contenant autant d'objets que l'on veut. Une manipulation consiste à enlever un objet de chaque tas et à faire un nouveau tas des objets ainsi récupérés.

Exemple : la répartition \((4,3)\) devient, après une manipulation, \((3,2,2)\). On considère que \((4,3)\) et \((3,4)\) sont identiques, de même que \((3,2,2)\), \((2,3,2)\) et \((2,2,3)\).

1. On part de la répartition \((7)\). Quelle répartition obtient-on après 3, 7, 11, puis 2007 manipulations ?

2. On ne connaît pas la répartition initiale, mais après 2007 manipulations on obtient \((4,2,1)\). Indiquer toutes les répartitions initiales possibles.

3. Paul dispose les objets sans montrer la répartition à Virginie, simule 2007 manipulations, et ne montre que la répartition finale. Virginie hésite alors entre trois répartitions initiales possibles. Sachant qu'elle a raisonné correctement, quelle répartition finale a-t-elle vue ?

Dessiner l'arbre de toutes les répartitions possibles de 7 (il y en a 15) et les flèches "manipulation" entre elles : on observe qu'au bout de quelques étapes, on entre dans un cycle de 4 répartitions qui se répète indéfiniment. Comme 2007 est grand, il suffit de trouver le reste de 2007 dans ce cycle de longueur 4 pour savoir où l'on atterrit — et, pour remonter dans le temps (questions 2 et 3), de regarder quelles répartitions mènent à chaque élément du cycle en exactement ce même reste de manipulations.

Le diagramme complet des répartitions de 7 et des manipulations qui les relient montre qu'à partir de n'importe quelle répartition, on finit par entrer dans un cycle de 4 répartitions : \((4,2,1) \to (3,2,1,1) \to (3,2,2) \to (3,3,1) \to (4,2,1) \to \cdots\)

1. En partant de \((7)\), on atteint \((4,2,1)\) en 3 manipulations, puis on entre dans le cycle de longueur 4. Comme \(2007=501\times4+3\), après 2007 manipulations on obtient encore \((4,2,1)\) (même reste que pour 3 manipulations).

2. Comme 2007 manipulations reviennent à « 3 manipulations dans le cycle », il suffit de « remonter » de 3 flèches à partir de chaque élément du cycle pour trouver toutes les répartitions initiales qui y aboutissent en 2007 étapes :

Répartitions initiales possibles	Aboutissent en 2007 manipulations à
\((7)\), \((2,1,1,1,1,1)\), \((3,3,1)\), \((4,3)\)	\((4,2,1)\)
\((6,1)\), \((3,1,1,1,1)\), \((3,2,2)\)	\((3,3,1)\)
\((5,2)\), \((3,2,1,1)\), \((2,2,1,1,1)\), \((2,2,2,1)\)	\((3,2,2)\)
\((4,2,1)\), \((5,1,1)\), \((4,1,1,1)\), \((1,1,1,1,1,1,1)\)	\((3,2,1,1)\)

Pour la question 2 (répartition finale \((4,2,1)\)) : les répartitions initiales possibles sont donc \((7)\), \((2,1,1,1,1,1)\), \((3,3,1)\) et \((4,3)\).

3. Virginie hésite entre exactement trois répartitions initiales : en regardant le tableau, seule la ligne aboutissant à \((3,3,1)\) propose exactement 3 répartitions initiales possibles (\((6,1)\), \((3,1,1,1,1)\), \((3,2,2)\)) — les autres lignes en proposent 4. Virginie a donc vu la répartition finale \((3,3,1)\).