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

Voygaeur de commerce à 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 : 2777
Lieu: Luxembourg

voyaheur de commerce à 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 : 1448

Voyageur de ocmmerce à Hanoï

@Franky : 2ème option smile

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

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

Voyageur de comerce à 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 : 1448

Voyageuur 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 d commerce à 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 : 1448

voyaheur de commerce à hanoï

@titoufred : tout à fait

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

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

Voyageurr 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

Voyageur de commmerce à 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 : 2777
Lieu: Luxembourg

Voyageuur de commerce à Hanoï

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

Voyageur de commerce àHanoï

Tout à fait. Merci

 

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 : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
09-09-2013 Enigmes Mathématiques
P2T
Vendu ! par SaintPierre
26-04-2011 Enigmes Mathématiques
P2T
30-09-2013 Enigmes Mathématiques
P2T
Un rapport difficile ? par SaintPierre
10-03-2011 Enigmes Mathématiques
P2T
Une bonne note par scrablor
09-09-2010 Enigmes Mathématiques
P2T
28-09-2011 Enigmes Mathématiques
P2T
Pliage 1 par looozer
06-03-2010 Enigmes Mathématiques
02-07-2013 Enigmes Mathématiques
P2T
21-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