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 - 20-03-2014 01:22:56

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

hanoi à 4 piquetq

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 ?

  • |
  • Répondre

#0 Pub

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

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

Hanoi à 4 ipquets

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

Hannoi à 4 piquets

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 smile

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

Code:

1    1
2    3
3    5
4    9
5    13
6    17
7    25
8    33
9    41
10    49
11    65
12    81
13    97
14    113
15    129
16    161
17    193
18    225
19    257
20    289

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

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

Hanoi à 4 piquetss

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

Hanoi à 4 piquet

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
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 458

Hnaoi à 4 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... big_smile

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

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

Hano à 4 piquets

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 smile

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

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

Hanoi à 4 piquet

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

hanoi à 4 piquers

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

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

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

HHanoi à 4 piquets

@scarta : Oui, c'est bien ça. Merci tatie Daniele wink

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.

 

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
05-02-2008 Enigmes Mathématiques
26-01-2010 Enigmes Mathématiques
P2T
Les taupes par Promath-
11-10-2010 Enigmes Mathématiques
P2T
Suite Logique par bleuazur
25-03-2012 Enigmes Mathématiques
P2T
10-09-2011 Enigmes Mathématiques
26-12-2010 Enigmes Mathématiques
01-07-2011 Enigmes Mathématiques
P2T
Formes mystères par w9Lyl6n
24-03-2012 Enigmes Mathématiques
P2T
Trouver 758 par lolek
18-09-2013 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