Répondre à la discussion
Affichage des résultats 1 à 22 sur 22

Dénombrement et combinaisons ( tour de hanoï)



  1. #1
    miido

    Dénombrement et combinaisons ( tour de hanoï)


    ------

    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.

    -----

  2. Publicité
  3. #2
    ansset
    Animateur Mathématiques

    Re : Dénombrement et combinaisons ( tour de hanoï)

    bonsoir,
    tu pourrais commencer par nous dire ce que tu as essayé de faire.
    déjà pour la première question.!
    cordialement.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  4. #3
    miido

    Re : Dénombrement et combinaisons ( tour de hanoï)

    pour la première

  5. #4
    Tryss2

    Re : Dénombrement et combinaisons ( tour de hanoï)

    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

    Code:
    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?)

  6. A voir en vidéo sur Futura
  7. #5
    ansset
    Animateur Mathématiques

    Re : Dénombrement et combinaisons ( tour de hanoï)

    edit : à mieux re exprimer
    Dernière modification par ansset ; 17/03/2017 à 01h03.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  8. #6
    miido

    Re : Dénombrement et combinaisons ( tour de hanoï)

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

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

  9. Publicité
  10. #7
    ansset
    Animateur Mathématiques

    Re : Dénombrement et combinaisons ( tour de hanoï)

    un doute pour la première : ne manque t il pas un facteur 3! qui correspond aux combinaisons des tours ?
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  11. #8
    miido

    Re : Dénombrement et combinaisons ( tour de hanoï)

    par exemple pour 5 disque on a 3^ 5 non

  12. #9
    miido

    Re : Dénombrement et combinaisons ( tour de hanoï)

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

  13. #10
    Tryss2

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Citation Envoyé par miido Voir le message
    pour le 2)a) ce n'est pas : ?

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

    Citation Envoyé par ansset Voir le message
    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)

    Citation Envoyé par miido Voir le message
    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) :
    Code:
    5 
    1   3
    2 . 4
    
    Correspond à :  2 1 5 | | 4 3

  14. #11
    ansset
    Animateur Mathématiques

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Citation Envoyé par Tryss2 Voir le message
    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  15. #12
    miido

    Re : Dénombrement et combinaisons ( tour de hanoï)

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

  16. Publicité
  17. #13
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Citation Envoyé par miido Voir le message
    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

  18. #14
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Et pour le 2 b) juste n!

  19. #15
    Médiat

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Pour le 2a je confirme
    Pour le 2b je trouve
    Dernière modification par Médiat ; 17/03/2017 à 18h15.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #16
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Citation Envoyé par redrum13 Voir le message
    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)

  21. #17
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

    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.

  22. #18
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

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

  23. Publicité
  24. #19
    Médiat

    Re : Dénombrement et combinaisons ( tour de hanoï)

    Citation Envoyé par redrum13 Voir le message
    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)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #20
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

    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?

  26. #21
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

    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é
    Dernière modification par redrum13 ; 17/03/2017 à 21h27.

  27. #22
    redrum13

    Re : Dénombrement et combinaisons ( tour de hanoï)

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

Discussions similaires

  1. Analyse combinatoire: dénombrement-permutations-arrangements-combinaisons
    Par snakes1993 dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 26/05/2011, 21h16
  2. Analyse combinatoire: dénombrement-permutations-arrangements-combinaisons
    Par snakes1993 dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 25/05/2011, 00h04
  3. tour d'hanoi
    Par hard-fifigirl dans le forum Logiciel - Software - Open Source
    Réponses: 6
    Dernier message: 11/06/2010, 16h37
  4. Problème : La Tour de Hanoï
    Par maite33 dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 23/04/2006, 21h56
  5. combinaisons/denombrement, help!
    Par daaa57150 dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 28/04/2004, 15h52