Comment puis-je résoudre ce Puzzle?
Répondre à la discussion
Affichage des résultats 1 à 13 sur 13

Comment puis-je résoudre ce Puzzle?



  1. #1
    christine123

    Cool Comment puis-je résoudre ce Puzzle?


    ------

    Bonjour à tous,

    Je travaille sur un projet et je suis tombé sur ce problème:


    J'ai des nombres de 1 à 36 que je veux mettre sur une matrice 6 * 6, comment calculer le nombre de possibilités existantes, et lister toutes les solutions possibles, aucun nombre ne doit être répété sur la matrice.


    Merci beaucoup.

    -----

  2. #2
    Dynamix

    Re : Comment puis-je résoudre ce Puzzle?

    Salut

    Citation Envoyé par christine123 Voir le message
    lister toutes les solutions possibles
    Lister 36! matrice 6x6 , plusieurs générations ne suffiront pas .

  3. #3
    christine123

    Re : Comment puis-je résoudre ce Puzzle?

    Merci pour votre reponse,

    je veux juste savoir comment les parcourir via un algorithme.

    Merci infiniment

  4. #4
    Deedee81
    Modérateur

    Re : Comment puis-je résoudre ce Puzzle?

    Salut,

    Puisque c'est juste parcourir toutes les permutations, tu peux utiliser : https://fr.wikipedia.org/wiki/Algorithme_de_Heap
    (avec quelques adaptations mineurs pour "afficher" les résultats sous forme de matrice)
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  5. A voir en vidéo sur Futura
  6. #5
    Médiat

    Re : Comment puis-je résoudre ce Puzzle?

    Salut

    A raison de 1000 matrices par page (ce qui est optimiste) il faut prévoir plus de feuilles de papiers

    Et un algorithme pouvant traiter 100 000 000 000 de matrices par seconde prendra plus de 117 958 310 118 563 298 283 865 années
    Dernière modification par Antoane ; 26/07/2020 à 17h08. Motif: A la demande de l'auteur, correction latex
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  7. #6
    Deedee81
    Modérateur

    Re : Comment puis-je résoudre ce Puzzle?

    C'est clair que si elle veut parcourir toutes les permutations du début à la fin, il lui faudrait "un certain temps" (comme le fût du canon ).

    Par contre si elle veut juste parcourir le début jusqu'à ce qu'elle en ait mare ou qu'il y ait une pane de courant, où si elle veut une approche purement théorique. Why not.
    Mais pour une approche pratique.... là évidemment on ne peut que parcourir une partie et il convient de dire si Heap convient ou s'il y a divers critères permettant de juger de la pertinence de l'échantillon. Les méthodes de type Monte Carlo ne se font pas n'importe comment. Mais là seule Christine pourra répondre, ça dépend totalement du projet en question dont on ne sait rien.
    Dernière modification par Deedee81 ; 26/07/2020 à 16h13.
    "Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)

  8. #7
    minushabens

    Re : Comment puis-je résoudre ce Puzzle?

    je me demande comment on pourrait aborder des questions comme: quelle est la proportion de ces 36! matrices qui sont inversibles? ou bien : quel est le déterminant moyen de ces matrices? ou encore: quelle proportion ont un déterminant négatif? On peut évidemment estimer ces quantités par sondage aléatoire, mais est-ce qu'on pourrait calculer les valeurs théoriques, sans lister les 36! matrices?

  9. #8
    Paraboloide_Hyperbolique

    Re : Comment puis-je résoudre ce Puzzle?

    Bonjour,

    Citation Envoyé par minushabens Voir le message
    je me demande comment on pourrait aborder des questions comme: quelle est la proportion de ces 36! matrices qui sont inversibles? ou bien : quel est le déterminant moyen de ces matrices? ou encore: quelle proportion ont un déterminant négatif? On peut évidemment estimer ces quantités par sondage aléatoire, mais est-ce qu'on pourrait calculer les valeurs théoriques, sans lister les 36! matrices?
    Cela devrait pouvoir se calculer théoriquement (au moins en partie) en se servant d'un peu de combinatoire et des propriétés du déterminant. Par exemple, le déterminant est nul si une ligne/colonne de la matrice est entièrement nulle ou si deux lignes/colonnes sont combinaison linéaire d'une troisième. Reste à déterminer combien il y a de telles matrices 6x6.

  10. #9
    minushabens

    Re : Comment puis-je résoudre ce Puzzle?

    des matrices 6x6 contenant les entiers de 1 à 36 il n'y en a pas beaucoup qui ont une colonne nulle.

  11. #10
    Médiat

    Re : Comment puis-je résoudre ce Puzzle?

    En tout cas, chaque pattern correspond à (6!)² matrices en permutant lignes et colonnes
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #11
    Dynamix

    Re : Comment puis-je résoudre ce Puzzle?

    Citation Envoyé par Paraboloide_Hyperbolique Voir le message
    si deux lignes/colonnes sont combinaison linéaire d'une troisième.
    Si une ligne/colonne est combinaison linéaire d' une des deux autres .
    C' est le cas d' une ligne/colonne nulle
    Dernière modification par Dynamix ; 27/07/2020 à 13h41.

  13. #12
    Médiat

    Re : Comment puis-je résoudre ce Puzzle?

    Citation Envoyé par Médiat Voir le message
    En tout cas, chaque pattern correspond à (6!)² matrices en permutant lignes et colonnes
    Je voulais dire en permutant les lignes entre elles et/ou les colonnes entre elles.


    Si compter les matrices telles qu'une colonne soit multiple d'une autre est assez simple (et encore) mais compter les matrices où 5 colonnes sont nécessaire pour exprimer la 6ième me paraît très compliqué (ou je rate quelque chose).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #13
    minushabens

    Re : Comment puis-je résoudre ce Puzzle?

    tiens, je me suis amusé à tirer au hasard cent mille matrices 6x6 avec les nombres entiers de 1 à 36 et j'ai tracé l'histogramme de leurs déterminants. Comme on a une belle courbe en cloche centrée sur zéro, on pourrait penser que la proportion de matrices non inversibles n'est pas négligeable, mais en fait aucune des cent mille matrices n'a un déterminant nul. Le déterminant le plus petit en valeur absolue est 1021. On peut pourtant facilement fabriquer des matrices avec deux colonnes proportionnelles et donc non inversibles. Mais elles sont très peu nombreuses comparativement à 36!.
    Images attachées Images attachées  
    Dernière modification par minushabens ; 29/07/2020 à 12h40.

Discussions similaires

  1. comment resoudre ...?
    Par ARMIA dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 22/05/2012, 15h02
  2. Comment résoudre
    Par invite92413b28 dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 17/10/2011, 11h04
  3. comment résoudre?
    Par invite8e46bc95 dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 13/03/2009, 17h16
  4. Comment résoudre ?
    Par invite01e3f9b6 dans le forum Mathématiques du collège et du lycée
    Réponses: 13
    Dernier message: 27/01/2008, 00h13
  5. comment puis-je ?
    Par invite8dd007f4 dans le forum Orientation après le BAC
    Réponses: 3
    Dernier message: 04/03/2007, 14h11