Travaux Dirigés de Structures Discrètes n^{o} 4

— Licence Informatique —

▶ Exercice 1 (Problème de Josephus) On dispose les entiers de 1 à n sur un cercle. En commençant avec 2 et en tournant sur le cercle, on élimine successivement un nombre sur deux jusqu’à ce qu’il n’en reste plus qu’un seul. On appelle J(n) le dernier entier qui reste sur le cercle. Ainsi si n est égal à 10, au premier tour, on élimine 2, 4, 6, 8 et 10. Il reste alors 1, 3, 5, 7 et 9 et au second tour, on élimine 3, 7 et 1. Au troisième tour, le nombre 9 est éliminé et le nombre 5 est le dernier à rester. On a donc J(10) = 5.

1. Calculer les valeurs de J(n) pour n = 1, …, 10.

2. Montrer que, pour tout entier n, on a J(2n) = 2J(n) − 1.

3. En déduire que, pour tout entier k, on a J(2^{k}) = 1 et J(5.2^{k}) = 2^{k+1} + 1.

4. Montrer que, pour tout entier n, on a J(2n + 1) = 2J(n) + 1.

5. Calculer les valeurs de J(n) pour n = 1, …, 20.

6. Montrer que, pour tout entier k, on a J(2^{k} − 1) = 2^{k} − 1.

7. On écrit n = 2^{k} + l où 0 ≤ l ≤ 2^{k} − 1. Montrer que J(n) = 2l + 1.

8. Résoudre les équations J(n) = n et J(n) = n/2.

9. On écrit l’entier n en base 2 : n = (b_{k} … b_{1}b_{0})_{2}. Donner l’écriture binaire de l puis de J(n).

10. On note J^{2}(n) = J(J(n)) et plus généralement on note J^{q} l’itérée q-ième de J, c’est à dire J^{q}(n) = J(J(… J(n) …)) où il y a q applications de la fonction J imbriquées. Montrer que, pour q assez grand, l’entier J^{q}(n) est une constante que l’on notera J^{ω}(n). Déterminer J^{ω}(n) en fonction de n.

11. Soient α, β et γ trois entiers fixés. Soit f la fonction vérifiant les relations

f(1) = α
f(2n) = 2f(n) + β pour n ≥ 1
f(2n + 1) = 2f(n) + γ  pour n ≥ 1

Calculer f(n) pour n = 1, …, 10.

12. Déterminer f(n) quand α = 1 et β = γ = 0.

13. Déterminer α, β et γ pour avoir f(n) = 1 pour tout entier n ≥ 1.

14. Déterminer α, β et γ pour avoir f(n) = n pour tout entier n ≥ 1.

15. En déduire une expression de f(n) en fonction de α, β et γ.

16. Montrer ce résultat par récurrence.