 |
#1 - 20-03-2014 01:22:56
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Hanoi à4 piquets
On joue aux tours de Hanoi mais avec 4 piquets au lieu de 3. Saurez-vous tirer parti de cet avantage pour passer les plateaux le plus rapidement possible du piquet de départ au piquet d'arrivée ?
1) Pour 6 plateaux ?
2) Pour 10 plateaux ?
3) Pour 100 plateaux ?
4) Pour un milliard de plateaux ?
5) Pour un nombre de plateaux égal à un gogol ?
#2 - 20-03-2014 08:19:10
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1984
Hano ià 4 piquets
Pour 6 plateaux je trouve 17, mais la généralisation ne va pas être simple ...
#3 - 20-03-2014 08:43:55
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1984
Hanoi à 4 piuqets
Après avoir défini une méthode, calculé les premières valeurs et cherché les termes sur OEIS, je suis fier de pouvoir annoncer que ma méthode est conjecturée comme étant la bonne, mais ça n'a pas été démontré. En plus il faut pour celà calculer tous les termes précédents. Donc pour le gogol faudra repasser 
En gros: Spoiler : [Afficher le message] U(n) est le nombre de termes nécessaires pour déplacer mes n plateaux sur 4 piquets. - j'en déplace un nombre n' (compris entre 0 et n-1) sur 4 piquets : U(n') - j'en déplace n-n' sur 3 piquets (le quatrième est déjà utilisé) : tours de Hanoï classique, soit 2^(n-n')-1 - je déplace les n' premiers sur 4 piquets (peu importe que le piquet d'arrivée ne soit pas vide, je peux tout à fait poser mes plateaux dessus vu qu'ils sont plus petits) : U(n')
Au final, U(n) = min(2^(n-n')-1 + 2U(n'), n'=0..n-1) Premiers résultats
#4 - 20-03-2014 14:23:35
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Hanoi à 4 piuets
Oui, scarta, c'est bien cela, bravo.
Pour le gogol, c'est faisable, même si cela fait de très grands nombres à manipuler.
Allez, disons un milliard de plateaux pour rester plus modeste, ça te semble faisable ?
#5 - 20-03-2014 19:52:26
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1984
Hani à 4 piquets
Même le gogol c'est jouable. Mais le coup de la différence qui vaut 2^N N+1 fois avant de passer au N suivant, au delà de 30 ça reste une conjecture (et jusqu'à 30 c'est de la recherche exhaustive)
Mais bon, en gros, U(n(n+1)/2) = 2^n * (n-1) + 1 pour les termes de rang "nombre triangulaire", donc on repère le plus proche du terme qui nous interesse et après on ajoute jusqu'à n fois 2^n pour aller jusqu'à notre "cible".
#6 - 20-03-2014 20:01:50
- Spirou
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 500
Hanoi à piquets
pour 4, c'est 7*2+1=15 pour 5, c'est 15*2+1=31 pour 6 c'est donc 31*2+1=63
Mais je pense que pour 1 milliard, ca serai trop long a faire, je dois trouver plus court... 
#7 - 20-03-2014 20:01:54
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1984
Hanoi à 4 piquet
Pour un milliard ça fait donc: 2^44720 * 44719 +1 + 38440 * 2^44720, soit 83159 * 2^44720 + 1
Et pour le gogol : 2^141421356237309504880168872420969807856967187537694 * 184882637637851345918212995981821713329192258350028 + 1
le nombre de chiffres de ce nombre comporte à lui seul pas moins de 49 chiffres...
Pour ce que ça vaut 
#8 - 20-03-2014 23:40:54
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3236
- Lieu: Luxembourg
Hanoi à 4piquets
On aura toujours la relation: F(n) = 2.F(n-2) + 3 Avec F(0) = 0 et F(1) = 1, cela nous donne: - si n est pair: F(n) = 3.[2^(n/2) - 1] - si n est impair: F(n) = 3.[(2/3).2^((n+1)/2) - 1] Du coup, on aura: 1) F(6) = 3.(2^3 - 1) = 21 2) F(10) = 3.(2^5 - 1) = 93 3) F(100) = 3.(2^50 - 1) = env. 3,38.10^15 4) F(10^9) = 3.(32^(10^8) - 1) = beaucoup 5) F(10^100) = 3.(32^(10^99) - 1) = beaucoup
#9 - 21-03-2014 10:51:42
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1984
haboi à 4 piquets
Allez la formule générale (sous réserve que la conjecture soit valide, bien entendu)

(Désolé si je passe par un autre site pour afficher mon Latex)
Et la formule Excel pour ceux qui veulent jouer avec :
#10 - 21-03-2014 17:40:51
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
hanoi à 4 piquetq
@scarta : Oui, c'est bien ça. Merci tatie Daniele 
Je te signale que la conjecture porte sur le fait que la méthode que tu as trouvée fournit la meilleure solution pour n>30, pas sur le fait que les différences sont ce qu'elles sont.
Donc, pour aller au fond des choses, saurais-tu prouver tout seul comme un grand que (pour l'algorithme que tu as trouvé) les différences sont bien ce qu'elles sont lorsqu'on ajoute un plateau ?
@Spirou : on peut faire mieux. N'oublie pas qu'il y a 4 piquets, pas 3.
@Franky : on peut faire mieux.
|
 |
Prise2Tete
Forum
Statistiques
Liste des membres
Hall of Fame
Contact
|