Josephus et compagnie

09/09/2011

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+1a_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)}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

Une page de pub…

08/11/2010

En 2011, plusieurs événements pourront intéresser les étudiants « avancés » (par exemple, étudiants de Master ou doctorants) :

deux leçons du Collège Belgique à Bruxelles, au Palais des Académies (de 17h à 19h),

  • 16 février 2011 : Suites automatiques et algébricité de séries formelles, J.-P. Allouche, M. Rigo
  • 16 mars 2011 : Fractions continues en géométrie discrète arithmétique, V. Berthé

Ces leçons se veulent accessibles à un public éclairé. Par exemple, dans la première, on présentera le très joli résultat de Harm Derksen montrant que l’ensemble d’annulation d’une suite linéaire récurrente en caractéristique positive est décrit par un automate fini (il s’agit en fait d’un ensemble p-reconnaissable d’entiers), cf. « A Skolem-Mahler-Lech Theorem in Positive Characteristic and Finite Automata »

En mai prochain, aura lieu la 5th INTERNATIONAL CONFERENCE ON LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2011),  Tarragona, Spain, May 30 – June 3, 2011. Narad Rampersad (post-doc à l’ULg) en est un des conférenciers invités. Son exposé portera sur les numérations abstraites.

En parlant de numération… signalons qu’au Département de Mathématiques de l’Université de Liège se déroulera du 6 au 10 juin 2011 la conférence internationale NUMERATION. La période tombe effectivement assez mal pour les étudiants en bloque, mais il pourrait être intéressant de venir écouter ne serait-ce que quelques exposés pour avoir l’occasion, au moins une fois, d’assister à une conférence de mathématiques.


R comme Q-espace vectoriel

27/09/2010

Suite à l’article « espace vectoriel de dimension finie », j’ai reçu le commentaire suivant :

Monsieur,
Je tombe par hasard sur votre site (tomber au sens littéral !). Votre histoire de R vu comme un Q-espace vectoriel m’intéresse ; pourriez-vous en révéler plus à vos lecteurs ?

——–

Lorsque l’on définit la notion d’espace vectoriel, on précise toujours qu’il s’agit d’un espace vectoriel sur un corps (ou un champ) spécifié. En effet, si \mathbb{K} est un champ et si E est un espace vectoriel sur \mathbb{K}, alors lorsqu’on définit par exemple le concept de combinaison linéaire, on se donne des éléments x_1,\ldots,x_k de E et des scalaires \alpha_1,\ldots,\alpha_k (i.e., des éléments de \mathbb{K}) pour construire l’élément de E, \alpha_1 x_1+\cdots+\alpha_k x_k. Ainsi, si l’on regarde \mathbb{R} comme un espace vectoriel sur \mathbb{Q}, on s’autorise uniquement des combinaisons linéaires du type : q_1 r_1+\cdots +q_k r_k où les q_i sont des rationnels et les r_i des réels. Cela a d’importantes conséquences. Par exemple, si \mathbb{R} est vu comme un espace vectoriel sur \mathbb{R}, 1 et \sqrt{2} sont linéairement dépendants car il est trivial de construire une combinaison linéaire à coefficients réels de ces deux éléments qui est nulle sans que les coefficients le soient, -\sqrt{2}.1+1.\sqrt{2}. Par contre, lorsque l’on consdière \mathbb{R} comme un espace vectoriel sur \mathbb{Q}, la situation est différente, cette fois 1 et \sqrt{2} sont linéairement indépendants (en effet, sinon \sqrt{2} serait rationnel). Dans le même genre, on peut par exemple regarder \mathbb{C} comme un \mathbb{C}-vectoriel ou comme un \mathbb{R}-vectoriel et tester, dans les deux cas, l’indépendance linéaire de 1 et i. On peut alors voir que la dimension de \mathbb{C} comme \mathbb{C}-vectoriel est 1, par contre, sa dimension comme \mathbb{R}-vectoriel vaut 2. Tout ça pour dire que parler d’espace vectoriel sans spécifier le champ sur lequel il est construit est un manque flagrant d’information !


Espace vectoriel de dimension infinie

04/06/2010

Bonjour Mr Rigo,
lors de mon examen oral, vous m’avez demandé de chercher un espace vectoriel de dimension infinie. Sur le coup je n’ai pas trouvé et vous ne m’avez finalement pas donné la réponse…
Cependant, j’ai eu le temps de réfléchir et une idée a surgi de mon esprit, peut-être pas brillante ,certes, mais une idée quand même… J’ai pensé que le vide pouvait être de dimemsion infinie…
Est-ce le cas?

——

Voici une réponse possible :

Pour rappel un espace vectoriel est de dimension finie, s’il contient une partie génératrice finie. L’ensemble vide ne convient guère. Une réponse possible est de considérer \mathbb{R}[X], l’ensemble des polynômes à coefficients réels. En effet, en procédant par l’absurde et en supposant que \mathbb{R}[X] contient une partie génératrice finie formée des polynômes P_1,\ldots,P_t, alors cela signifie que tout polynôme est combinaison linéaire de P_1,\ldots,P_t. Or, le degré d’une telle combinaison \alpha_1 P_1+\cdots +\alpha_t P_t, avec les \alpha_i réels ne peut dépasser le degré maximal des P_i. Ceci est absurde puisque \mathbb{R}[X] contient des polynômes de degré arbitraire.

Ce n’est pas le seul exemple, mais c’est le plus ‘classique’. On peut par exemple penser à \mathbb{R} vu comme un \mathbb{Q}-vectoriel, à l’ensemble \mathbb{R}^\mathbb{N} des suites réelles vu comme \mathbb{R}-vectoriel, mais aussi à des espaces de fonctions. Mais alors, les preuves sont peut-être moins ‘triviales’ et il est d’ailleurs intéressant de chercher des bases de ces espaces de fonctions (mais c’est une autre histoire).


Question : rang et systèmes

31/05/2010

Bonjour Mr Rigo,
j’ai une question à propos du corollaire VI.3.6 (si le système(S)est compatible,il est équivalent au système (S’) obtenu en ne considérant que les lignes lin. ind. et en nombre égal au rang de A.):
Dans la démo,vous dites que, par construction de (S’), toute ligne Li de A est comb. lin. des r=rgA lignes de la matrice de (S’); mais ce que je ne comprends pas c’est que, dans toutes les lignes de A, il y a les r=rgA lignes lin. ind. donc comment peuvent-elles etre comb. lin. des r lignes de la matrice de (S’)? ces r lignes seraient lin. dép. alors, non? c’est un point que je ne comprends pas et tout en espérant que ma question est assez claire, je vous remercie d’avance pour l’aide que vous pourrez m’apporter.

————————

On considère une matrice A de rang r. Cela signifie que le nombre maximum de lignes linéairement indépendantes de A vaut r et donc que parmi les lignes de A, on peut en trouver exactement r (et pas plus, simultanément) qui sont linéairement indépendantes. Soient L_{i_1},\ldots,L_{i_r} ces r lignes.

Tout ligne L de A est combinaison linéiare de ces r lignes L_{i_1},\ldots,L_{i_r}. En effet, si L est une des lignes L_{i_1},\ldots,L_{i_r}, c’est immédiat (c’est une fois la ligne en question et on obtient immédiatement une combinaison linéaire). Si L est une ligne différente de L_{i_1},\ldots,L_{i_r}, alors les r+1 lignes L,L_{i_1},\ldots,L_{i_r} sont linéairement dépendantes (sinon le rang de A serait >r) et de là, on en tire que L est combinaison linéaire de L_{i_1},\ldots,L_{i_r}. (En effet, si x_1,\ldots,x_r sont linéairement indépendants alors, x,x_1,\ldots,x_r sont linéairement dépendants si et seulement si x est combinaison linéaire de x_1,\ldots,x_r.)

A ce stade, je n’ai pas encore parlé du système (S') mais celui-ci est construit en sélectionnant certaines équations de (S) et précisément, la sélection se fait en choisissant des équations correspondant aux lignes de A linéairement indépendantes (et en nombre maximum). Cela devrait alors à présent être clair.

Bon travail.


Question : connexité

15/05/2010

Bonjour (ou bonsoir). J’espère être au bon endroit pour poster ceci..

J’ai une idée pour raccourcir de manière assez significative la fin d’une longue démonstration du cours de théorie des graphes, et j’aimerais savoir si elle est valable (pour un examen oral par exemple). Il s’agit de la démonstration du corollaire II.2.6 , pages 75 et 76 du cours (spectre symétrique implique graphe biparti).

Contexte :
Nous avons notamment montré que les ensembles V1 et V2 sont disjoints, et que tout chemin reliant un sommet de V1 à un sommet de V2 est nécessairement de longueur impaire. Pour conclure la preuve, au dernier paragraphe (“Supposons à présent que, dans G,un chemin…”) , il reste à montrer que 2 sommets de V1 (et V2 mais preuve identique) sont forcément reliés par des chemins de longueur paire. Ce qui est développé dans les feuilles est assez long et compliqué, et j’ai pensé à ceci.

J’aurai besoin de
(1) Les sommets de V1 (resp. V2) sont reliés à u par un chemin de longueur impaire (resp paire).
(2) V1 et V2 sont disjoints.

Soient a et b des sommets de V1. Vu (1) , a est joint à u par C1 de long. impaire , b à u par C2 de long. impaire. Procédons par l’absurde et supposons que a et b sont joints par un chemin de long. impaire C3. Alors le chemin qui part de u, prend C1 puis C3 et arrive à b est de long. paire (impaire+impaire = paire). Vu (1), on obtient que b appartient aussi à V2 , d’où contradiction vu (2). (de meme, a est dans V2 aussi).

Donc a et b sont forcément joints par un chemin de longueur paire , ce qui conclut.

Serait-il possible que vous confirmiez si cela est correct s’il vous plait ?

Merci d’avance.

Adrien Deliège , 2 BM

——————————

Tout d’abord un commentaire général : lors d’un examen oral, je suis ravi de pouvoir discuter avec un étudiant de preuves alternatives ou de variantes aux démonstrations présentées. En effet, le plus intéressant pendant l’examen est de savoir si les étudiants ont réfléchi et muri les concepts développés aux cours. Donc, même si un étudiant me proposait à un oral une preuve originale mais inexacte, il serait alors très intéressant de discuter avec lui pour sortir de l’examen avec une nouvelle preuve correcte. (Bien sûr, je comprends très bien que dans l’immense majorité des cas, on reprenne la preuve vue au cours).

Bon, à présent pour ce qui est spécifiquement de l’argument proposé. Il me paraît tout à fait valable et est d’ailleurs basé sur le même genre d’argument que celui développé dans le cours. Donc, cela me convient très bien.


Trivial mathematics

08/03/2010

Une citation intéressante de Doron Zeilberger et un petit article intéressant à lire : There is no trivial mathematics, there are only trivial mathematicians! A mathematician is trivial if he or she believes that there exists trivial mathematics. Being a non-trivial mathematician myself, I will describe ten different proofs of the seemingly trivial fact that the number of ways of choosing k people out of n people is less than or equal to the number of ways of choosing k+1 people out of n people, provided that k is less than half of n. http://arxiv.org/abs/1003.1273

Doron Zeilberger est notamment l’un des auteurs du livre A=B que l’on ne peut que conseiller.