Problème délicat ..
Bonsoir, on m'a posé un problème, je souhaite aidé quelqu'un mais je ne vois pas comment , peut être vous aurrez une idée ? elle sera la bienvenue ..
On dispose N personnes en cercle qui sont numérotées dans l'ordre de 1 à N.
On décide de tuer la personne qui porte le premier numéro , puis de laisser la vie sauve au numéro 2, puis de tuer le numéro 3 et ainsi de suite en en supprimant un sur deux jusqu'à ce qu'il n'en reste plus qu'un qui sera le survivant.
Par exemple si on a 6 personnes au départ, on tue le 1, puis le 3, puis le 5, puis le 2, puis le 6 et il ne reste donc que le 4.
La question est Peut on trouver une formule qui donne le numéro du dernier survivant en fonction du nombre de participants, et si oui qu'elle est-elle ?
Merci ..
On dispose N personnes en cercle qui sont numérotées dans l'ordre de 1 à N.
On décide de tuer la personne qui porte le premier numéro , puis de laisser la vie sauve au numéro 2, puis de tuer le numéro 3 et ainsi de suite en en supprimant un sur deux jusqu'à ce qu'il n'en reste plus qu'un qui sera le survivant.
Par exemple si on a 6 personnes au départ, on tue le 1, puis le 3, puis le 5, puis le 2, puis le 6 et il ne reste donc que le 4.
La question est Peut on trouver une formule qui donne le numéro du dernier survivant en fonction du nombre de participants, et si oui qu'elle est-elle ?
Merci ..
Réponses
-
salut,
je crois que c'est N si N est une puissance de 2 et 2(N - p) où p est la plus grande puissance de 2 inférieure à N sinon.
(analyser la représentation de N en binaire). -
Bonjour
Euh, tu peux expliquer davantage stp?
Merci -
bonjour, ce problème est traité en détail dans le premier chapitre de:
{\it Mathématiques concrètes} de Knuth et consorts...
Bon courageA demon wind propelled me east of the sun -
Coucou, ressemble étrangement au problème de Flavius Josephus évoqué ici même il y a 2,3 jours...
\lien{http://www.les-mathematiques.net/phorum/read.php?3,375982,375982#msg-375982}
Super dimanche à tous. -
Le qualificatif "Mathématiques concrètes" me laisse songeur...
-
Dans ce cas, il s'agissait d'un problème concret puisque sauf erreur de ma part les Juifs enfermés dans Massada avaient décidé d'un suicide collectif...A demon wind propelled me east of the sun
-
Knuth explique dans la préface qu'il s'agit à la fois de mathématiques CONtinues et disCRETES.
-
J'ai eu l'occasion de visiter Massada peu de temps après la série américaine du même nom.
Les enfants, les femmes, plus les hommes qui n'avaient pas le courage de se suicider étaient tués par d'autres Juifs, qui ensuite se seraient donnés la mort, selon le procédé de Flavius Josèphe. Plutôt morts, qu'esclaves ou prisonniers des Romains.
Un grand moment d'Histoire et de ...mathématiques. -
salut Sandrine,
je n'avais jamais entendu parler de ce Flavius Josèphe, de son problème et sa tragique histoire !
Dans ton problème, j'ai simplement observé que pour trouver la liste des survivants à chaque cycle, il suffisait de compter en binaire en accolant les derniers bits de N, plus un 0. Mais c'est très informel (bien que ma formule soit correcte, je pense) et bien sûr les références qu'on t'a fournies sont plus sérieuses -
D'accord, merci .. !
Bonne soirée! -
qu'est ce qui ne va pas dans mon raisonnement? (désolé ce soir je suis HS)
si on numérote de 0 à N-1 les personnes (avec N>1), tout le monde sera tué si et seulement si 2 est un générateur de Z/NZ, donc si et seulement si 2 est premier avec N. -
Ce qui ne va pas c'est qu'au deuxième tour ceux qui ont été éliminés au premier ne comptent plus donc le n°2 par exemple deviendra le n°1 etc...
De toute façon le pb est d'avoir le n° du dernier survivant. -
Ce qui ne va pas dans ton raisonnement est que le nombre de personnes sur le cercle va diminuer à chaque "tour de cercle" : par exemple, écris sur ta feuille 1,2,3,4,5,6 en cercle. Tu barres le 1, puis le 3, puis le 5. Mais tu ne t'arrêtes pas là. Tu barres ensuite le 2 et il reste un survivant : le 4.
-
Merci à vous .. !
-
donc j'avais mal lu l'énoncé, je croyais qu'il fallait tué tout le monde
c'est mon côté psychopate ça
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 164.7K Toutes les catégories
- 46 Collège/Lycée
- 22.1K Algèbre
- 37.4K Analyse
- 6.3K Arithmétique
- 57 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 19 CultureMath
- 50 Enseignement à distance
- 2.9K Fondements et Logique
- 10.6K Géométrie
- 80 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 73 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 331 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 792 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres