Enigme Hanoi à 4 piquets @ Prise2Tete

titoufred · #1

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 ?

scarta · #2

Pour 6 plateaux je trouve 17, mais la généralisation ne va pas être simple ...

scarta · #3

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]
Premiers résultats

Code:

titoufred · #4

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 ?

scarta · #5

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

Spirou · #6

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

scarta · #7

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

Franky1103 · #8

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

scarta · #9

Allez la formule générale (sous réserve que la conjecture soit valide, bien entendu)

$http://latex.codecogs.com/gif.download?U_N%3D2%5E%7B%5Cleft%5Clfloor%7B%5Cfrac%7B%5Csqrt%7B8N+1%7D-1%7D%7B2%7D%7D%5Cright%5Crfloor%7D*%5Cleft%28N-%5Cfrac%7B%5Cleft%5Clfloor%7B%5Cfrac%7B%5Csqrt%7B8N+1%7D-1%7D%7B2%7D%7D%5Cright%5Crfloor%5Cleft%28%5Cleft%5Clfloor%7B%5Cfrac%7B%5Csqrt%7B8N+1%7D-1%7D%7B2%7D%7D%5Cright%5Crfloor-1%5Cright%29%7D%7B2%7D-1%5Cright%29+1$

(Désolé si je passe par un autre site pour afficher mon Latex)

Et la formule Excel pour ceux qui veulent jouer avec :

Code:

POWER(2;FLOOR((SQRT(8*A1+1)-1)/2;1))*(-1+A1-((FLOOR((SQRT(8*A1+1)-1)/2;1))*((FLOOR((SQRT(8*A1+1)-1)/2;1))-1))/2)+1

titoufred · #10

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

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 20-03-2014 01:22:56

Hanoi à piquets

#0 Pub

#2 - 20-03-2014 08:19:10

aHnoi à 4 piquets

#3 - 20-03-2014 08:43:55

Hanoi à 4 piqutes

Code:

#4 - 20-03-2014 14:23:35

hanoi à 4 piqyets

#5 - 20-03-2014 19:52:26

Hanoi à 4piquets

#6 - 20-03-2014 20:01:50

hanoi à 4 piqyets

#7 - 20-03-2014 20:01:54

Hani à 4 piquets

#8 - 20-03-2014 23:40:54

Hani à 4 piquets

#9 - 21-03-2014 10:51:42

hanoi à 4 piqyets

Code:

#10 - 21-03-2014 17:40:51

Hanoi à 4 piiquets

Réponse rapide

Sujets similaires

Pied de page des forums