Les entiers naturels de 0 à n sont écrits au tableau noir. Zig et Puce, chacun à son tour, effacent exactement k d’entre eux s’il en reste 2k ou 2k+1.La partie s’arrête quand il reste deux entiers a et b, b > a qui ont pour différence d = b – a.Par exemple pour n = 6, on a la liste des sept entiers : 0,1,2,3,4,5,6. Au premier tour, Zig efface trois d’entre eux, par exemple 2,4 et 5. Il reste 0,1,3,6. Puce efface les deux entiers 0 et 3. La partie s’arrête avec les deux entiers b = 6 et a = 1 dont la différence est d = 5.

Le joueur qui commence la partie choisit n et son objectif est d’obtenir la valeur de d la plus élevée possible tandis que le second joueur cherche au contraire à la minimiser. On suppose que les deux joueurs jouent de manière optimale.

Q₁ : Zig choisit n = 2013 et commence la partie.Quelle valeur de d obtient-il?

Q₂ : C’est au tour de Puce de commencer la partie. Il choisit le plus petit n qui lui permet d’obtenir une valeur de d une fois et demie plus grande que celle obtenue précédemment par Zig. Que vaut n ?

 Solution

Jean Drabbe,Jean Moreau de Saint Martin et Paul Voyer ont résolu le problème.