Josephus et compagnie

Les sous-questions à un examen oral peuvent suciter l’intérêt ! Pour une brève présentation du problème de Josephus dont il est question ci-dessous, on peut par exemple consulter le wiki http://en.wikipedia.org/wiki/Josephus_problem

En tout cas, merci à Adrien pour ses réactions. Voici sa question, suivie de quelques pistes.

————————————————————————————

Bonjour M. Rigo.
Lors de mon examen oral de Math. Discrètes ce matin, vous m’avez demandé ce qu’il se passait dans le problème de Josephus lorsqu’une personne sur 3 était éliminée. J’y ai réfléchi à tête reposée, et je suis coincé dans mes calculs…

J’ai essayé d’adapter la preuve vue au cours, mais elle ne fonctionne malheureusement pas. J’ai donc calculé la valeur de J(n) pour les 100 premiers entiers, et, à la main, cette suite n’était pas très difficile à construire (les 22 premiers termes sont 1,2,2,1,4,1,4,7,1,4,7,10,13,2,5,8,11,14,17,20,2,5,…) Il suffit en fait d’ajouter 3 à chaque coup, en réduisant modulo n si J(n)> n .

Si on pose E_n = { m <= n tels que J(m) = 1 ou 2 } , on trouve que J(n) = 3n-1-k(n), où k(n) est la somme de tous les éléments de E_n . Pour obtenir une formule close pour J(n), il faudrait donc en trouver une pour k(n). Les entiers m qui sont tels que J(m) = 1 ou 2 sont donnés par 1,2,3,4,6,9,14,21,31,47,70,105,158,… et donc, la suite k(n) des sommes partielles est donnée par 1,3,6,10,16,25,39,60,91,138,208,313,471,…
On peut vérifier (formule trouvée sur http://oeis.org/) que cette suite vérifie k(n) = Floor[(3*k(n-1)+3)/2] , k(1) = 1 .

C’est là que je suis coincé. En essayant de distinguer les cas pairs et impairs pour se débarrasser du Floor , il est assez compliqué de trouver une formule close pour k(n).

Pensez-vous qu’il en existe une ? Ou bien faut-il s’y prendre autrement pour trouver une formule close pour J(n) ? Avez-vous une solution “simple”, comme pour le Josephus classique ? Le site cité ci-dessus donne une formule “monstrueuse” (voir : http://oeis.org/search?q=1%2C2%2C2%2C1%2C4%2C1%2C4%2C7%2C1%2C4%2C7%2C10&sort=&language=english&go=Search ) , et je ne vois pas du tout d’où elle provient, mais à priori, elle ne provient pas des résultats que j’ai mentionnés…
Comment continuer ?

————————————————————————————

C’est déjà très bien d’avoir mené ton raisonnement jusque là (et quand je pose une question comme celle-là, je m’intéresse surtout à la discussion que l’on peut avoir plutôt qu’à la réponse en tant que telle). Enposant la question, je n’avais pas de réponse précise en tête… En cherchant un peu sur le net, on trouve par exemple le texte suivant http://www.cs.manchester.ac.uk/~shamsbaa/Josephus.pdf

Le mieux est probablement de jeter un oeil au “Concrete Math.” dont je parle ci-dessous.

On trouve aussi des articles de recherche :

L. Halbeisen and N. Hungerbühler. The Josephus problem. Journal de Théorie des Nombres de Bordeaux, 9(2):303–318, 1997.

En voici le résumé : Nous donnons des formules explicites permettant de calculer les nombres de Josephus j(n,2,i) and j(n,3,i) et fournissant une majoration et une minoration explicites de j(n,k,i) qui ne diffèrent que d’au plus 2k-2 (dans le cas k=4, ces bornes sont même meilleures). Nous proposons aussi un nouvel algorithme pour le calcul de ces nombres basé précisément sur ces estimations.

L’article est disponible en ligne avec le lien suivant : http://jtnb.cedram.org/jtnb-bin/fitem?id=JTNB_1997__9_2_303_0

R. Stephan, On a sequence related to the Josephus problem, http://arxiv.org/abs/math/0305348
A. Odlyzko and H. Wilf. Functional iteration and the Josephus problem. Glasgow Math. J., 33(2):235–240, 1991. (Dans cet article, on étudie plutôt des comportements asymptotiques de suites dérivées dont je parle ci-dessous et il ne semble pas facilement accessible en ligne.)
Bien sûr, je dois aussi mentionner le livre de référence (dont je me suis inspiré pour mon cours de math. discrètes) : R. L. Graham, D. E. Knuth and O. Patashnik, Concrete mathematics, Addison-Wesley, Reading, MA, 1989. Dans le chapitre 3.3, on mentionne que $J_3(n)=\lceil \frac{3}{2}J_3(\lfloor \frac{2}{3}n\rfloor)+a_n\rceil\mod n+1$ où $a_n=-2,1,-\frac{1}{2}$ si $n\mod 3$ vaut respectivement $0,1,2$ . Ensuite, les auteurs continuent avec “But this recurrence is too horrible to pursue.” Néanmoins, ils poursuivent avec une autre approche (… il faut donc emprunter le livre à la bibliothèque, mais je peux aussi prêter mon exemplaire personnel).

Je vais m’arrêter là, mais il faut savoir que ce problème et la suite dérivée $D_n^{(q)}$ définie par $D_0^{(q)}=1$ et $D_n^{(q)}=\lceil \frac{q}{q-1} D_{n-1}^{(q)}\rceil$ ont été largement étudiés. En fait le lien entre $D_n^{(q)}$ et le problème de Josephus généralisé $J_q(n)$ est le suivant: $J_q(n)=q n+1-D_k^{(q)}$ où $k$ est le plus petit entier tel que $D_k^{(q)}>(q-1)n$ .

A. Odlyzko and H. Wilf montrent par exemple que $D_n^{(3)}=\lfloor (\frac{3}{2})^n C\rfloor$ où la constante $C$ est proche de 1,622270503. Quel intérêt ? Il se fait que l’apparition de $\frac{3}{2}$ est, de mon point de vue, très intéressante… En effet, cela débouche sur l’étude de systèmes de numération (donc, des moyens pour représenter les nombres entiers/réels) ayant des propriétés surprenantes (en comparaison avec les systèmes usuels en base entière). Ils ont été récemment introduits dans S. Akiyama, C. Frougny, J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems. Israel J. Math. 168 (2008), 53–91. On trouve par exemple l’article ici : http://www.infres.enst.fr/~jsaka/PUB/pub.html

Bien que cet article s’intéresse aux numérations et aux langages associés, il est notamment motivé par une question (très difficile) posée par K. Mahler en 1968 : existe-t il un nombre réel $z$ tel que la partie fractionnaire de $z (3/2)^n$ appartienne à l’intervalle $[0,1/2[$ pour tout $n\ge 1$ ? Mahler a montré que l’ensemble de ces nombres, appelés Z-nombres, est au plus dénombrable. K. Mahler, An unsolved problem on the powers of 3/2, J. Austral. Math. Soc. 8 (1968) 313–321.

Pour être complet, voici encore quelques autres papiers inspirés de Josephus :

Wilson, Gregory L.; Morgan, Christopher L. An application of Fourier transforms on finite abelian groups to an enumeration arising from the Josephus problem. J. Number Theory 130 (2010), no. 4, 815–827.
Dubickas, Artūras On integer sequences generated by linear maps. Glasg. Math. J. 51 (2009), no. 2, 243–252.
Uchiyama, Saburô On the generalized Josephus problem. Tsukuba J. Math. 27 (2003), no. 2, 319–339.
Groër, Chris The mathematics of survival: from antiquity to the playground. Amer. Math. Monthly 110 (2003), no. 9, 812–825

Cet article a été publié le Vendredi 9 septembre 2011 à 08:21 et est classé dans Culture Math.. Suivez toutes les réponses à cet article via le flux RSS 2.0. Vous pouvez laisser un commentaire ou un rétrolien depuis votre site.