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

Voyageur de commerce à Hanï

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

Voyageur de commerrce à 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 : 1470

Voyageur de commerec à Hanoï

@Franky : 2ème option smile

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

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

voyageur se 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 : 1470

voyageur de commerce à haniï

@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 commerce à Hannoï

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

Vyoageur de commerce à Hanoï

@titoufred : tout à fait

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

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

Vyageur 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

voyageir 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 : 2793
Lieu: Luxembourg

voyageur de commerce à janoï

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

Voyageur de comemrce à 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 : Tim, Tam et ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 114 par Vasimolo
15-12-2015 Enigmes Mathématiques
P2T
Gateau 57 par gabrielduflot
17-12-2012 Enigmes Mathématiques
P2T
Avions par schaff60
28-01-2010 Enigmes Mathématiques
P2T
En nage ? par SaintPierre
24-08-2011 Enigmes Mathématiques
07-01-2016 Enigmes Mathématiques
P2T
Vélo par Gadjo
25-11-2008 Enigmes Mathématiques
17-06-2015 Enigmes Mathématiques
P2T
Phrase nombres premiers. par gilles355
30-08-2012 Enigmes Mathématiques
P2T
Equation Differentielle par salehseghiri
30-11-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