Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 16-11-2013 10:46:36

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2956

me dernier jeton.

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.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 16-11-2013 11:02:26

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 301
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 : 2956

Le denier 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 : 2956

le detnier jeton.

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 : 2717
Lieu: Luxembourg

Le dernier jeon.

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 : 301
Lieu: Montargis

Le dernier jetn.

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

 #7 - 16-11-2013 14:48:43

MarcLog
Amateur de Prise2Tete
Enigmes résolues : 5
Messages : 1

Le dernier jeon.

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

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 : 2956

Le dernier jteon.

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 : 301
Lieu: Montargis

le dernier jzton.

Proposition 2

Avec la contrainte supplémentaire d'usage unique de la main, voici la réponse, indice B lol

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

 #10 - 16-11-2013 16:14:27

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2717
Lieu: Luxembourg

Le edrnier 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 : 2956

Le derneir 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 dernier 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 dernuer 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 : 2956

me dernier 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 : 2956

Le deriner jeton.

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 dernier jeron.

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).

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete