Dénombrement et combinaisons ( tour de hanoï)

[miido]

Bonjour,
J’ai de mal à répondre aux questions suivantes

Sachant qu'on part d'une tour de Hanoï. 3 tours et n disques
Soit Sn la suite de coups permettant de déplacer les n disques d'une tour vers une autre. On note cn le nombre de coups de Sn

Question 1 Combien existe-t-il de façons de placer les 9 disques de sorte à ce qu'il y ait 3 disques sur chaque tour. On ne considérera que les placements corrects.

Question 2 Combien existe-t-il de façons de placer sur les trois tours :
— n disques de manière correcte ?
— n disques, éventuellement de manière incorrecte ?

Question 3 On souhaite maintenant coder un placement correct de n disques sur les trois tours. Peut-on coder ce placement avec 2n bits ? Justifiez votre réponse.

Question 4 Combien existe-t-il de façons de placer les 6 disques de sorte à ce qu'il y ait 2 disques sur chaque tour. On considérera cette fois-ci tous les placements possibles même ceux qui ne sont pas corrects. Cela signifie que les disques ne sont pas forcément empilés par taille décroissante de bas en haut. Deux placements sont différents si on peut trouver un disque qui n'est pas à la même position (en partant du haut) dans une tour dans les deux placements ou si on peut trouver un disque qui n'est pas sur la même tour dans les deux placements.

Question 5 On souhaite maintenant coder un placement (pas nécessairement correct) de n disques sur les trois tours. Peut-on coder ce placement avec 2n[log(n)] bits ? En cas de réponse positive donner le codage et en cas de réponse négative donner un argument prouvant l'impossibilité d'un tel codage.
-----

[ansset]

bonsoir,
tu pourrais commencer par nous dire ce que tu as essayé de faire.
déjà pour la première question.!
cordialement.

[miido]

pour la première

[Tryss2]

Pour la question 2)a), on peut s’intéresser, pour chaque disque, au numéro de la tour sur laquelle il se trouve.

Pour la question b), c'est un peu plus sournois. une façon de faire, c'est de représenter la situation par une liste des numéro des disques avec deux séparateurs à placer.

Par exemple, on pourra représenter la situation

5 
1 
2 3 4

Par 2 1 5 | 3 | 4

A partir de là, il n'est pas trop difficile de calculer le nombre de telles listes (combien de listes de n nombres? Combien de façon de placer deux séparateurs (pouvant être collés !) dans une liste?)

[A voir en vidéo sur Futura]

[ansset]

edit : à mieux re exprimer

[miido]

pour le 2)a) ce n'est pas : ?

pour b) c'est un exemple de 5 disques ?

[ansset]

un doute pour la première : ne manque t il pas un facteur 3! qui correspond aux combinaisons des tours ?

[miido]

par exemple pour 5 disque on a 3^ 5 non

[miido]

pour les deux réparateurs j'ai trouvé une combinaison de 2 paris 7

[Tryss2]

pour le 2)a) ce n'est pas : ?

pour b) c'est un exemple de 5 disques ?

Oui et oui

un doute pour la première : ne manque t il pas un facteur 3! qui correspond aux combinaisons des tours ?

Non : dès que tu fixes les disques par tour, il n'existe qu'un seul placement correct (les disques doivent nécessairement être rangés dans l'ordre sur chaque tour pour que le placement soit valide)

pour les deux réparateurs j'ai trouvé une combinaison de 2 paris 7

Non, car les deux séparateurs peuvent être à la même position (ça correspond à une tour vide) :

5 
1   3
2 . 4

Correspond à :  2 1 5 | | 4 3

[ansset]

Non : dès que tu fixes les disques par tour, il n'existe qu'un seul placement correct (les disques doivent nécessairement être rangés dans l'ordre sur chaque tour pour que le placement soit valide)

OK, faut que je revois précisément les règles.

[miido]

Bonjour
pour la question 4 j'ai trouvé : c'est juste ?

[redrum13]

pour le 2)a) ce n'est pas : ?

pour b) c'est un exemple de 5 disques ?

Pour la première question je trouve 1680 aussi.

Pour le 2 a) je prends un n multiple de 3 sinon il y a un reste c'est plus compliqué, je trouve plutôt

[redrum13]

Et pour le 2 b) juste n!

[Médiat]

Pour le 2a je confirme
Pour le 2b je trouve

[redrum13]

Pour la première question je trouve 1680 aussi.

Pour le 2 a) je prends un n multiple de 3 sinon il y a un reste c'est plus compliqué, je trouve plutôt

Mauvaise compréhension de la question ne pas tenir compte de ma réponse du 2 a)

[redrum13]

Pour la 3) par contre je dirais (avec prudence) que le nombre de codages est supérieur au nombre de bons placements des n disques: donc oui.

[redrum13]

Pour la 4) 6! (produit des arrangements de 2 parmi 6 en décrémentant de 2)

[Médiat]

Pour la 4) 6! (produit des arrangements de 2 parmi 6 en décrémentant de 2)

Ou directement 6! (on prend une permutation quelconque, on met les 2 premiers éléments sur la première pique , les 2 suivants sur la deuxième et les 2 derniers sur le 3ième)

[redrum13]

Pour la 2 b) je tombe sur al même chose: 3 placements au premier disque, 4 placements possibles pour un deuxième disque, 5 pour un troisième etc qque soit la configuration par piquet, soit 3*4*5*...*(n+2)=
C'est comme rajouter un piquet de plus à chaque fois non?

[redrum13]

Dernière question comparer 2n(log(n)) avec 0.5(n+2)!

factorielle croit plus vite que n.log(n) d'après mes souvenirs de complexité

[redrum13]

A priori 0.5(n+2)! > 2n(log(n)) pour tout entier n,donc le codage ne suffit pas.