Les bonbons, solution

Distribution de bonbons ( libérale avancée)

n enfants sont placés en cercle. On distribue des bonbons en tournant toujours dans le même sens sur le cercle, de la façon suivante :
On donne un bonbon à un enfant, on passe le suivant, on donne un bonbon au troisième, on passe les deux suivants, on donne un bonbon au sixième enfant, et ainsi de suite ... ( Quand on a donné le kème bonbon, on passe k enfants).

Pour quelles valeurs de n les enfants auront-ils tous au moins un bonbon ?

Solution

Les enfants sont numérotés de 1 à n. Appelons u_k le numéro de l'enfant qui reçoit le kème bonbon distribué.

u₁=1
u₂=3...
u_k=1+2+...+k mod(n)
On vérifie facilement que u_2n-1=u_2n=n
On connaît toute la suite dès que l'on connaît u₁,u₂,...u_n-1. En effet, u₁=u_2n-2;u₂=u_2n-3...u_n-1=u_n. La condition pour que tous les enfants aient un bonbon est donc que tous les u_k soient différents et prennent les valeurs 1, ...,n-1 pour k = 1, ...,n-1.
On va montrer que ce n'est possible que si n est une puissance de 2.

Si n n'est pas une puissance de 2, n admet un diviseur impair donc peut se décomposer en somme d'entiers consécutifs.
Il existe i, j dans {1,2,...,n-1} tels que (i+1)+...+j =n donc u_i=u_j.

Si n = 2^m
Aucun u_k ne peut être égal à n, car k(k+1)/2 a un facteur impair (soit k, soit k+1).
Quels que soient i, j dans {1,2,...,n-1} (i+1)+...+j n'est pas un multiple de n donc u_i!=u_j, en effet :
(i+1)+...+j =(j-i)(i+j+1)/2
Si j-i est pair j+i +1 est impair et réciproquement ( leur somme est impaire). Il y a donc deux possibilités exclusives pour que (i+1)+...+j soit un multiple de 2^m : ou j-i est multiple de 2^m+1, ou i+j+1 est multiple de 2^m+1, ce qui est impossible puisque i et j sont strictement inférieurs à 2^m .