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

Hanoi à 4 piquetss

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 ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

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

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

Hanoi à 4 piquetss

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

Hanoi à 4piquets

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

hanoi à 4 piqyets

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

haboi à 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
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 440

Hnoi à 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


Il vaut mieux mobiliser son intelligence sur des choses betes que de mobiliser sa betise sur des choses intelligentes.

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

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

Hanoi à 4 ppiquets

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

Hanoi à 4 ppiquets

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

Hanoi à 4 piquts

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

anoi à 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 (numériquement) à la petite énigme suivante : 

Si il y a 88 pommes et que vous en prenez 44, combien vous en avez ?

Sujets similaires

Sujet Date Forum
P2T
Ca eut payé par Vasimolo
30-10-2009 Enigmes Mathématiques
P2T
Puissances de 5 par dhrm77
28-06-2009 Enigmes Mathématiques
P2T
24-02-2012 Enigmes Mathématiques
02-01-2010 Enigmes Mathématiques
P2T
Rectangle nombre d'or par spleenface
07-02-2009 Enigmes Mathématiques
21-06-2010 Enigmes Mathématiques
P2T
Gâteau 2 par Vasimolo
09-04-2010 Enigmes Mathématiques
P2T
04-04-2013 Enigmes Mathématiques
P2T
24 avec 1,3,4,6 par RumKisser
05-12-2009 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