![](/img/vague-bas-gauche.png) |
#1 - 16-11-2013 10:46:36
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
le dernier jrton.
Bonjour à tous. Ce problème est assez classique: Vous disposez de n jetons numérotés placés dans l'ordre de 1 à n en cercle. On ôte le 1 puis un jeton sur 2 (3,5,..) jusqu'à ce qu'il n'en reste plus qu'un seul. Pourriez vous inventer la technique qui permet, avec le seul nombre n, de trouver le n° du dernier jeton ? Ah, petite précision: tout ça doit se faire sans calculette ni aide informatique.... Indice: Perso, j'ai trouvé avec le nombre n écrit en binaire, mais ce n'est pas une obligation.
Bon amusement.
#2 - 16-11-2013 11:02:26
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
L dernier jeton.
On ôte le 1 puis un jeton sur 2 (3,5,..)
Je n'ai pas bien compris, pourquoi 1 sur 2, 3, 5, ... (pourquoi pas sur 4 aussi)? Et puis comment sont choisis les lots de 2, 3, ... jetons parmi lesquel le jeton est retiré?
#3 - 16-11-2013 11:45:13
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le derniier jeton.
C'est écrit 1 sur 2; donc en commençant par ôter le 1, on ôte ensuite le 3, puis le 5,... Exemple complet avec 7: 1234567: après 1 tour reste: 246. Comme 7 a été ôté, le 2 qui suit le 7 est conservé, et on prend le 4. le 6 est conservé, on prend le 2. Reste le 6.
#4 - 16-11-2013 12:17:07
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le dernier eton.
Pour 12345: reste 24, comme on a ôté 5, le suivant 2 est épargné, on ôte 4, reste 2.
Pour 1234, on ôte 13, reste 24, le dernier ôté est 3, 4 est épargné, on prend ensuite 2. Reste 4.
Pour 123456, reste 246, 2 est ôté puis 6, reste 4.
Evidemment, c'est loin d'être une bijection. Il est évident que le dernier est toujours pair, puisque tous les impairs sont ôtés au premier tour.
#5 - 16-11-2013 13:54:22
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Le edrnier jeton.
Cette énigme est similaire à celle des 999 victimes postée par Azdod: http://www.prise2tete.fr/forum/viewtopic.php?id=9686
Avec (ent) représentant la partie entière et (log) un logarithme (peu importe lequel), le reste sera de: 2.n – 2^{ent [log(n-1) / log(2)] + 1} qu’on peut aussi écrire: 2.(n – 2^{ent [log(n-1) / log(2)]})
#6 - 16-11-2013 14:04:16
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
lr dernier jeton.
Proposition:
On cherche le plus grand [latex]k[/latex] tel que [latex]2^k\leq n[/latex] soit [latex]k=PE(\frac{ln(n)}{ln(2)})[/latex]
où [latex]PE[/latex]=fonction partie entière.
On calcule le nombre [latex]nb=n-2^k[/latex]
On détermine enfin le numéro du dernier jeton:
Si nb=0 alors dernier(n)=n
Sinon dernier(n)=2*nb.
Voilà ![smile](img/smilies/smile.png)
#7 - 16-11-2013 14:48:43
- MarcLog
- Amateur de Prise2Tete
- Enigmes résolues : 5
- Messages : 1
le dernier jeyon.
Pour tous les n étant des puissances entières de 2, le dernier sera n
Pour tous les autres l'indice du dernier est [latex]2*( n-2^[log_2(n)] )[/latex]
Comprendre [x] la partie entière de x ![big_smile](img/smilies/big_smile.png)
PS : Désolé en revanche, je débute avec les formules latex...
#8 - 16-11-2013 15:33:29
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le dernier jton.
Pour les nombreuses réponses qui sont déja arrivées: Pas de calculette ni moyen informatique ! Alors pour le log, sauf si d'aucuns trouvent plus rapide de le recalculer à la main...
#9 - 16-11-2013 16:01:02
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
Le dernier jetoon.
Proposition 2
Avec la contrainte supplémentaire d'usage unique de la main, voici la réponse, indice B ![lol](img/smilies/lol.png)
On décompose n en nombre binaire, soit x ce nombre.
Désignons par [latex]k[/latex] le nombre de chiffres dans x moins 1.
Et là je retombe sur mes pattes :
On calcule le nombre [latex]nb=n-2^k[/latex]
On détermine enfin le numéro du dernier jeton:
Si nb=0 alors dernier(n)=n
Sinon dernier(n)=2*nb.
A noter quand même que dans x dont la longueur donne [latex]k[/latex], il n'y a pas de zéros inutiles au bébut
Voilà ![smile](img/smilies/smile.png)
#10 - 16-11-2013 16:14:27
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Le ernier jeton.
Avec cette restriction, je cherche la plus petite puissance de 2 supérieure ou égale au nombre de départ. Je retranche cette puissance de 2 au double du nombre de départ. Ex1: n = 25; ppp2 = 32; 2 x 25 - 32 = 18 Ex2: n = 32; ppp2 = 32; 2 x 32 - 32 = 32 Ex3: n = 65; ppp2 = 128; 2 x 65 - 128 = 2
#11 - 16-11-2013 17:39:30
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
ke dernier jeton.
OK Franky pour la solution la plus directe. Oui, kossi. Bon, ce problème là n'aurait pas dû être posé, trop classique....
#12 - 17-11-2013 13:19:11
- Neotenien
- Passionné de Prise2Tete
- Enigmes résolues : 43
- Messages : 56
le drrnier jeton.
Bonjour
J'ai essayé cette suite en boucle avec différentes valeurs pour N, N étant le nombre de jetons.
Il s'avère qu'effectivement, les nombres binaires interviennent pour la résolution de ce problème.
Ce que j'a constaté c'est que le nombre restant étant N en binaire décalé d'un bit à gauche (et en supprimant le bit de poids fort).
Autrement dit, le résultat est N*2-(2^k) avec 2^k étant la puissance de 2 immédiatement supérieure à N.
Je pense pouvoir démontrer la première partie du résultat (c'est à dire pour la suite de bits de poids faible étant tous 0). Mais pour la suite, je n'ai pas poussé les investigations plus loin.
Pour les bits faibles étant à 0, en effet, on constate qu'un élimine tous les nombres précédents à N dont le bit 0 est à 1, le bit 1 à 1 etc... tant que le numéro d'ordre du bit est inférieur à celui où l'on trouve le premier bit à 1 dans N.
#13 - 17-11-2013 18:21:21
- eudoxie
- Habitué de Prise2Tete
- Enigmes résolues : 12
- Messages : 33
le derbier jeton.
bon voici une réponse, non justifiée ....
je calcule [latex]\alpha = E( \frac {\ln n }{\ln 2})[/latex] . si [latex]n = 2 ^\alpha [/latex] alors le numéro cherché est n
si n est [latex] 2 ^{^\alpha} + k [/latex] alors le numéro cherché est 2 k .
#14 - 18-11-2013 19:01:21
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
le dernoer jeton.
Eudocie et Néotenien, oui ! Une tentative d'explication serait cependant la bienvenue...
#15 - 19-11-2013 18:08:43
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Le dernier jetonn.
Toutes les réponses données sont bonnes, la plupart d'entre vous connaissaient déja ce problème, d'autres le découvraient. Ce problème avait déja été proposé sur ce site, comme l'un d'entre vous l'a rappelé.
Je voudrais tout de même revenir sur l'explication du résultat.
Si un nombre est une puissance de 2, alors le résultat est identité, la même puissance de 2. En effet, au 1er tour on ôte les impairs, le 2^n est épargné. Du coup, le 2 est le 1er du second tour à être ôté, et comme on en ôte 1 sur 4, ce sont les 2+4k ôtés, donc le 2^n est préservé. Et ainsi de suite à chaque tour: on ôte les 2^(k-1) +2^k, ce qui garantit qu'on 2^n est préservé jusqu'au final.
Si le nombre vaut 1+2^n , il suffit alors d'ajouter dans le cercle un jeton juste avant le jeton 2^n, de sorte que quand on joue ce 1er jeton on retombe sur le 1, et donc on finira sur le 2^n. Mais en ajoutant ce surnuméraire, qu'on joue en premier, le jeton 2^n devient 2. Donc 1+2^n aura comme reste 2.
Si le nombre vaut 2+2^n, on ajoute encore un jeton surnuméraire entre 2^n-1 et 2^n-3, de sorte qu'en jouant les 2 surnuméraires, on retombe encore sur 1. Dans cette configuration, 2^n prend alors la position 4 et sera le jeton final.
Et ainsi de suite.
Le reste vaudra donc pour k+2^n: 2(k+2^n-2^n)=2k.
Bien entendu, k ne peut être supérieur à 2^n, ça correspondrait à plus d'un tour complet de jetons surnuméraires. Il faut donc prendre pour n le 2^n immédiatement inférieur au nombre choisi.
Si on tente maintenant d'ôter un jeton sur 3, ou sur k>2, on n'obtient plus de résultat aussi facile à trouver.
#16 - 22-11-2013 23:34:14
- Neotenien
- Passionné de Prise2Tete
- Enigmes résolues : 43
- Messages : 56
Le edrnier jeton.
OIk tentative d'explication alors
J'ai fait des essais. Pour N, j'ai constaté que tant que le plus faible bit de N était supérieur au rang du tour (n=1,2 etc), N était conservé. D'où ma première partie de démonstration. "Pour les bits faibles étant à 0, en effet, on constate qu'un élimine tous les nombres précédents à N dont le bit 0 est à 1, le bit 1 à 1 etc... tant que le numéro d'ordre du bit est inférieur à celui où l'on trouve le premier bit à 1 dans N."
Quand on arrive au rang du plus faible bit de n à 1, N est alors éliminé. Il reste les nombres s'écrivant xxx00000 (par exemple) sachant que N s'écrit xxx10000.
Or, à partir de là, on n'élimine non pas les nombres à partir du premier et tous les 2 coups mais à partir du 2eme... là j'avoue que je sèche et j'ai pas envie de chercher la suite.
En tous cas, j'ai constaté que le résultat était pour N 1 décalage de 1 bit sur la gauche (en supprimant le nouveau bit de poids fort) et, comme tous ceux qui ont fait de l'analyse numérique le savent, un décalage d'un bit sur la gauche est la même chose que multiplier par 2 (ça je peux le démontrer par contre).
|
![](/img/vague-haut-droite.png) |