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 - 19-03-2014 11:15:22

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Voyageur de cmomerce à Hanoï

Petite énigme sans prétention, pour la détente smile

Pour ceux qui ne connaissent pas les tours de Hanoï:
On a trois piquets et N disques qui peuvent se ficher sur les piquets et s'empiler dessus. Les N disques ont tous des tailles différentes et sont empilés (de bas en haut) sur le premier piquet du plus grand au plus petit, pour former une sorte de pyramide.
Le but est de déplacer tous les disques sur le dernier piquet, sachant que:
- on ne peut déplacer qu'un disque à la fois, d'un piquet vers un autre
- le disque déplacé est toujours au sommet de sa pile
- on ne peut pas empiler un disque sur un autre plus petit

Voici une variante : à l'image du voyageur de commerce, les disques doivent à l'arrivée être tous passés au moins une fois sur chacun des piquets, et les états initiaux / finaux sont les mêmes que dans le problème original.
En combien de déplacements peut-on réaliser ces mouvements, en fonction de N ?

La case réponse valide le cas N=50



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 19-03-2014 11:47:21

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

Voyageur de comemrce à Hanoï

Dans la version classique, on raisonne par récurrence:
x(1) = 1 et x(n) = 2.x(n-1) + 1 donnent: x = 2^n – 1
Dans la variante proposée, je raisonne aussi par récurrence:
- pour 1 seul disque, je dois passer par les deux autres piquets: x(1) = 2,
- pour n disques, je suis obligé de déplacer les n-1 disques trois fois pour
  pouvoir déplacer le plus grand disque deux fois: x(n) = 3.x(n-1) + 2,
- ce qui donne: x = 3^n – 1
Pour n = 50, je trouve x = 7,18 x 10^23 environ.
Mais que valide la case-réponse ?
A moins que je me sois trompé dans mon raisonnement.

 #3 - 19-03-2014 12:45:42

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

voyageur de commercz à hanoï

@Franky : 2ème option smile

 #4 - 19-03-2014 15:03:38

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Voyageu rde commerce à Hanoï

On trouve pour le problème initial 2^N-1, donc ici je dirais 3*(2^(N-1)-1)+2, ce qui fait 3*2^(N-1)-1.

Pour N=50, je trouve 1688849860263935, mais ce n'est pas validé par la case réponse.

 #5 - 19-03-2014 21:27:17

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

boyageur de commerce à hanoï

@titoufred : c'est à 1 près. Après, c'est peut être moi qui ait tort, si tu pouvais détailler le raisonnement de ta formule on pourra voir.

 #6 - 20-03-2014 00:06:48

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Voyageur de ccommerce à Hanoï

Ah ben oui, ça ne va pas car le 2ème plateau le plus grand ne passe pas par le centre dans ce cas.

Donc je corrige et propose (pour N > 1) : 7*2^(N-2)-1

Mais apparemment, tu proposes 3*2^(N-1), c'est bien ça ?
Tu arrives à faire 12 coups pour N=3 ?

 #7 - 20-03-2014 08:09:30

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Voyageur de commece à Hanoï

@titoufred : tout à fait

 #8 - 21-03-2014 11:32:06

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

voyagrur de commerce à hanoï

Ah, ben pas de bonne réponse...
Dans le cas initial, l'idée est la suivante : pour N disques, la stratégie est de déplacer les N-1 premiers disques sur le piquet du milieu, puis le dernier disque sur le dernier piquet et les N-1 premiers disques sur le dernier piquet ensuite.

Autrement dit, tous les disques sont passés par tous les piquets sauf le plus grand (ils sont tous sur le piquet de départ au début, puis sur celui de milieu quand on déplace le plus grand; et enfin sur le dernier piquet à la fin). Le plus grand ne passe jamais sur le piquet du milieu.

Si on considère maintenant la stratégie suivante (celle de titoufred) :
- je déplace les N-1 premiers disques sur le dernier piquet
- je déplace le dernier disque au milieu
- je déplace les N-1 premiers disques sur le premier piquet
- je déplace le dernier disque sur le dernier piquet
- et enfin je déplace les N-1 premiers disques sur le dernier piquet
Dans ce cas là, l'avant dernier disque ne passe jamais sur le piquet du milieu; comme l'a remarqué titoufred.

Reste la stratégie suivante
- je déplace les N-1 premiers disques sur le piquet du milieu
- je déplace le dernier disque sur le dernier piquet
- je déplace les N-1 premiers disques sur le premier piquet
- je déplace le dernier disque sur le piquet du milieu
- je déplace le dernier disque sur le dernier piquet
(un aller retour en fait)
- et enfin je déplace les N-1 premiers disques sur le dernier piquet

Les N-1 premiers disques sont tous sur le piquet initial au début, tous au milieu après la première étape et tous sur le dernier à la fin. Et le dernier disque est sur le piquet initial au début, au milieu au début de l'aller retour et sur le dernier piquet à la fin.

Déplacer N disques se fait en 2^N-1 coups.
Par conséquent, pour chaque étape il faut
- 2^(N-1)-1 coups
- puis 1 coup
- puis 2^(N-1)-1 coups
- puis 1 coup
- puis 1 coup
- puis 2^(N-1)-1 coups
Total: 3*2^(N-1)

Exemple pour N=3:

Code:

1  |  |  
2  |  |
3  |  |
---------

|  |  |  
2  |  |
3  |  1
---------

|  |  |  
|  |  |
3  2  1
---------

|  |  |  
|  1  |
3  2  |
---------

|  |  |  
|  1  |
|  2  3
---------

|  |  |  
|  |  1
|  2  3
---------

|  |  |  
|  |  1
2  |  3
---------

|  |  |
1  |  |  
2  |  3
---------

|  |  |
1  |  |  
2  3  |
---------

|  |  |
1  |  |  
2  |  3
---------

|  |  |
|  |  |  
2  1  3
---------

|  |  |
|  |  2  
|  1  3
---------

|  |  1  
|  |  2
|  |  3
---------

 #9 - 21-03-2014 17:59:04

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Vooyageur de commerce à Hanoï

Mais bien sûr ! Comment j'ai fait pour ne pas trouver ?

 #10 - 23-03-2014 15:12:50

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

voyageur de commerce à hznoï

Je me suis laissé piéger aussi.

scarta a écrit:

Total: 2*2^(N-1)

Tu as sans doute voulu écrire:
Total: 3*2^(N-1)

 #11 - 24-03-2014 10:52:19

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1430

Voyageur de commerce à Hanïo

Tout à fait. Merci

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
P2T
08-08-2007 Enigmes Mathématiques
08-09-2008 Enigmes Mathématiques
P2T
Gâteau 111 par Vasimolo
02-12-2015 Enigmes Mathématiques
P2T
16-02-2009 Enigmes Mathématiques
P2T
Gâteau 39 par Vasimolo
29-05-2011 Enigmes Mathématiques
P2T
12-12-2011 Enigmes Mathématiques
P2T
Miroir, miroir... par legeneral
03-10-2008 Enigmes Mathématiques
P2T
12-07-2013 Enigmes Mathématiques
P2T
On va en boîte ? par SaintPierre
04-09-2011 Enigmes Mathématiques

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