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

Une énigme.....



  1. #1
    FlyingMarco

    Talking Une énigme.....


    ------

    Salut à tous,

    Je bute sur une énigme mathématique :

    Quinze jeunes filles d'une école se promènent trois par trois les sept jours d'une semaine. Et-il possible de les répartir journellement de telle sorte que deux d'entre-elles ne marchent jamais deux fois côte à côte ?

    J'ai réussi à répondre à la question, j'ai une solution, mais je voudrais savoir s'il existe d'autres solutions que la mienne, ou s'il existe une méthode de recherche ou encore peut-on démontrer l'existence d'une solution avant d'en donner une ??

    Merci
    Marc

    -----

  2. Publicité
  3. #2
    shokin

    Re : Une énigme.....

    Quinze jeunes filles d'une école se promènent trois par trois les sept jours d'une semaine. Et-il possible de les répartir journellement de telle sorte que deux d'entre-elles ne marchent jamais deux fois côte à côte ?
    Donc une fille aura marché pendant 1 jour avec 2 filles, pendant 2 jours avec 4 filles, pendant n jours avec 2n filles, pendant 7 jours avec 14 filles.

    Oui ! c'est possible ! Si c'est possible pour une fille, c'est possible pour les 14 autres filles. Toutes les filles suivent la même règle du jeu !

    Il faut encore trouver comment arranger le coup ! mais oui ! c'est possible.

    Quant à trouver une méthode, je vais y réfléchir (à commencer par des cas plus simples : groupes de 2, moins d'élèves...).

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  4. #3
    Korgox

    Re : Une énigme.....

    Citation Envoyé par shokin
    Oui ! c'est possible ! Si c'est possible pour une fille, c'est possible pour les 14 autres filles. Toutes les filles suivent la même règle du jeu !
    Ca me convainc pas vraiment...quelqu'un d'autre confirme le raisonnement de shokin ?

  5. #4
    FlyingMarco

    Re : Une énigme.....

    Salut à tous les deux

    Shokin il me semble qu'il y a une erreur dans ton raisonnement :
    La fille de droite (ou de gauche) d'un des groupes de 3, n'aura qu'une fille à éviter le lendemain (elle n'a qu'une voisine) --> les groupes de 3 sont séparés .

    Ex :
    1°jour)--> 1;2;3 -- 4;5;6
    2°jour)--> 6;2;4 -- 3;1;5
    .....etc

    Enfin c'est qu'un exemple avec 6 filles sur 2 jours.

    Enfin moi j'ai une solution : je sais que c'est possible, mais ce sont les autres questions qui m'intéréssent. Mais proposez vos réponses

    Marc

  6. #5
    shokin

    Re : Une énigme.....

    Oups ! j'ai mal compris la donnée !

    Mais alors ! c'est encore plus possible !

    Je vais y réfléchir mieux.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  7. A voir en vidéo sur Futura
  8. #6
    olle

    Re : Une énigme.....

    un exemple pour montrer que le raisonnement de shokin est très bancal :

    soient deux filles, la fille A et la fille B.

    l'objectif à atteindre est d'être à droite de qqun

    la fille A peut y arriver
    la fille B peut y arriver tout autant (les mêmes règles sont applicables à toutes les filles)

    MAIS

    A et B ne peuvent être à droite de qqun en même temps.

    ce qui démontre qu'il faut être bcp plus rigoureux mon petit shokin
    car si chaque fille peut avoir de nouvelles voisines chaque jour, rien ne dit que toutes les filles sont capable d'en faire autant en même temps.
    Dernière modification par olle ; 12/01/2005 à 20h35.

  9. Publicité
  10. #7
    cricri

    Re : Une énigme.....

    au debut je trouvais hyper simple donc je me disait que j avais pas comprit
    en fait faut faire 5 groupe de 3 et cela chaque jour
    reste une question si on prend A B C A est t il a cote de C je pense que oui

    il y a 105 combinaison 2 a 2 des 15
    3 combinason pour 3 personne donc 105/3 =35 soit 5 groupe *7 jour
    il y a donc 1 seule solution

  11. #8
    shokin

    Re : Une énigme.....

    Excuse, j'ai mal compris la donnée, j'ai imaginé complètement faux la situation.

    Si les filles sont au nombre de 15 et toujours par groupe de 3, l'une à gauche, l'une au milieu, l'une à gauche, toutes tournées vers le bel enseignant,

    en un jour, 5 se retrouvent à côté de 2, 10 se trouvent à côté de 1.

    Le deuxième jour, ça se complique, car les 5 filles médiantes peuvent rester médiantes et les autres peuvent changer de groupe (chacune 8 possibilités) ou elles peuvent aussi bouger... pour avoir meilleure vue sur le prof ...



    Disons que le fait que A soit à côté de B définisse une relation R.

    Pour 15 filles, il y a donc 15*14/2=105 relations possibles au total.

    A chaque jour, il y a 10 relations différentes.

    Le but étant de n'avoir qu'une fois au plus chaque relation.

    Il ne peut donc y avoir plus de 10 jours consécutifs respectant ce but.

    Mais peut-il y en avoir 10 ? combien au max ?


    Combien y a-t-il de groupes de 3 possibles ? 15*14*13, l'ordre importe.

    Combien y a-t-il de groupes de 3 possibles où seule la fille du miileu importe ? 15*14*13/2=1365

    Combien y a-t-il de combinaisons de 5 groupes de 3 possibles pour 1 jour, respectant le but ? l'ordre des groupes n'important pas. (15!/5!)/(2^5) [15! pour chaque place, /5! car l'ordre des 5 groupes n'importe point, /(2^5) car à chacun des 5 groupes, 2 possibilités équivalent (seul la fille médiante importe)]

    Parmi les 1365 groupes de 3 possibles où seule la fille du milieu importe, à un de ces groupes, combien en sont compatibles ? (deux groupes de 3 sont compatibles s'ils n'ont aucune fille commune) 12*11*10/2=660. Mais parmi ces 660 (incompatibles entre eux, bien sûr), je ne pourrai en choisir que 4, vu que je n'ai que 15 filles à disposition, dont 3 déjà fichées.

    Parmi les 1365 groupes de 3 où seule la fille du milieu importe, à un de ces groupes, combien sont but-compatibles ? (deux groupes sont buts-compatibles s'ils n'ont pas de relation commune) 12*11*10/2 + 12*11*3/2 + 12*2*1/2 + 12*2*1/3 = 660+198+12+8 = 878.

    Mais cela va-t-il m'être utile ? même pas sûr !

    Allez ! et peut-être que j'ai encore dit des bêtises !

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  12. #9
    FlyingMarco

    Re : Une énigme.....

    Salut à tous ,

    Je vous file la solution que j'ai trouvé :
    1° jour ) {1;2;3} ; {4;5;6} ;{7;8;9} ; {10;11;12} ; {13;14;15}
    2° jour ) {1;4;13} ; {2;6;11} ; {3;5;9} ; {7;12;15} ; {8;10;14}
    3° jour ) {1;5;10} ; {2;7;14] ; {3;4;12} ; {6;8;15} ; {9;11;13}
    4° jour ) {1;6;7} ; {2;12;13} ;{3;10;15} ;{4;9;14} ; {8;11;15}
    5° jour ) {1;8;12} ; {2:9:10} ; {3;6;14} ; {4;11;15} ; {5;7;13}
    6° jour ) {1;11;14} ; {2;5;15} ; {3;8;13} ; {4;7;10} ; {6;9;12}
    7° jour ) {1;9;15} ; {2;4;8} ; {3;7;11} ; {5;12;14} ; {6;10;13}


    Voila voila

    Marc

  13. #10
    olle

    Re : Une énigme.....

    je pense qu'i n'y a aucun intéret à chercher une solution par essai, mais qu'il faut plutot démontrer la possibilité de trouver une solution...

    sinon elle est fause, car :
    4° jour ) {8;11;15}
    5° jour ) {4;11;15}

  14. #11
    yat

    Re : Une énigme.....

    A mon avis, pour ce genre de problème, il est bien plus facile de trouver une solution que de démontrer que c'est possible.
    A l'inverse, si ce n'était pas possible, il serait bien plus facile de le démontrer que de chercher une solution, non ?
    En cherchant un peu à manipuler les données, on trouve que 7 jours c'est justement le nombre maximum de triplets dans lesquels une fille donnée peut se trouver, on trouve qu'il y a 105 binomes en tout, et que comme chaque triplet donne deux binomes, il faut exactement 35 triplets (comme par hasard, c'est le nombre de groupes différents au cours des 7 jours)... pour un binome donné il y a 13 triplets possibles, et comme dans chaque groupe de 13 on ne peut en prendre qu'un, il en faut 455, ce qui est exactement le nombre de triplets possibles...
    Forcément, tout tombe pile, mais je vois mal comment on pourrait affirmer sans la trouver qu'il existe nécessairement une solution.
    Et de même, de là à dire qu'il n'y a qu'une solution... une fois qu'on en a une, je pense qu'en inversant les numéros 1 et 2 on obtiendra une solution différente.

    olle, je pense que l'erreur que tu soulignes n'est qu'une faute de frappe : au jour 4 il faut lire (8;11;5)

  15. #12
    FlyingMarco

    Re : Une énigme.....

    Salut Olle et Yat,

    Alors biensûr , au 4° jour, il faut lire {8;11;5} , puisque le 15 est déja ailleurs (faute de frappe). Je pense bien qu'il est plus facile de trouver une solution que de démontrer le problème je pense.

    Merci à tous
    Marc

  16. Publicité
  17. #13
    yat

    Re : Une énigme.....

    Je tiens peut-être un truc...

    On peut définir un opérateur + qui dit quelle est la fille qui viendra compléter le triplet, pour un binome donné. Naturellement, on part du principe qu'il existe une solution, afin de s'intéresser à l'opérateur de cette solution.
    C'est à dire que si par exemple dans ma solution le premier jour les filles 1, 2 et 3 se mettent ensemble, alors 1+2=3, 1+3=2 et 2+3=1.

    Dans un premier temps, le problème de l'agencement en jours me parait un peu complexe à modéliser sous cette forme, donc je considère simplement que je dois construire 35 triplets d'éléments de l'ensemble "jeunes filles" (que je numérote de 1 à 15), tels qu'un binome n'apparaisse jamais dans deux triplets différents.

    Si je connais l'opérateur +, il me suffira de l'appliquer à tous les binomes possibles et de supprimer les doublons.

    Soient A, B, C et D quatre éléments de l'ensemble.

    On part des postulats évidents (pour que l'opérateur réponde à la question) que A+B=B+A, et que si A+B=C alors A+C=B.

    Si A+B=C alors B=C+A, donc si A+D=C alors D=C+A=B. Pour A et C donnés il existe donc un et un seul élément B tel que A+B=C

    Si A+B=C, alors A+A=A+B+C=B+B, donc un nombre additionné à lui même donne toujours la même valeur, et comme A+A+B=A+C=B, cette valeur est neutre pour l'opérateur. Ca tombe bien il me reste le zéro dans mon ensemble. Par hypothèse, on posera également qu'il ne fait pas partie de l'ensemble des filles, puisque s'il existait un élément D tel que A+A=D, ça voudrait dire que le jour ou A et D sont ensemble, alors la troisième est... A.

    Je pense que ces propriétés sont suffisantes pour chercher un opérateur qui réponde à ces conditions. Je sors de ma manche le ou exclusif binaire. En prenant les éléments comme je les ai numérotés, ça colle parfaitement, et j'ai un sacré bol que la valeur maximale soit de la forme 2n-1. Et mon élément neutre est le zéro, qui ne correspond donc pas à une des quinze filles.

    D'un petit coup d'excel, je génère les 105 binomes différents, je détermine pour chacun l'élément associé, je trie les triplets obtenus, je supprime les doublons et voilà la liste des 35 triplets que j'obtiens :
    {1;2;3}, {1;4;5}, {1;6;7}, {1;8;9}, {1;10;11}, {1;12;13}, {1;14;15}, {2;4;6}, {2;5;7}, {2;8;10}, {2;9;11}, {2;12;14}, {2;13;15}, {3;4;7}, {3;5;6}, {3;8;11}, {3;9;10}, {3;12;15}, {3;13;14}, {4;8;12}, {4;9;13}, {4;10;14}, {4;11;15}, {5;8;13}, {5;9;12}, {5;10;15}, {5;11;14}, {6;8;14}, {6;9;15}, {6;10;12}, {6;11;13}, {7;8;15}, {7;9;14}, {7;10;13}, {7;11;12}
    (pour le coup s'il y a une erreur ça ne peut pas être une faute de frappe c'est excel qui a fait le sale boulot)

    Nous voilà donc partis dans un problème tout autre... on a 35 triplets, dont certains sont incompatibles (deux triplets contenant un même élément ne peuvent pas apparaitre le même jour), qu'on doit regrouper en 7 ensembles de 5 triplets compatibles.

    Là encore, je ne sais pas si c'est possible avec cet ensemble de triplets... je pourrais le faire à la main, mais je préfère chercher une méthode aussi automatique que la première.

  18. #14
    shokin

    Re : Une énigme.....

    Ou l'on peut procéder successivement par statistiques :

    Je considère le groupe ABC et le groupe CBA comme un même groupe (mais pas comme ACB par exemple), B étant la fille au milieu d'un groupe. [La gauche et la droite n'importent point. ]

    L'ordre des groupes et des jours n'importe pas.



    Combien y a-t-il de possibilités de formation de groupes le premier jour ?

    Je choisis d'abord les filles les mieux entourées. Je dois en choisir 5 parmi 15. (15!/10!)/5!=3003.

    Je choisis ensuite les groupes de 2 filles qui accompagnent. Je dois d'abord les former :

    Pour le premier groupe de 2, j'ai 10*9/2 possibilités.
    Pour le deuxième groupe de 2, j'ai 8*7/2 possibilités.
    Pour le troisième groupe de 2, j'ai 6*5/2 possibilités.
    Pour le quatrième groupe de 2, j'ai 4*3/2 possibilités.
    Pour le cinquième et dernier groupe de 2, j'ai 2*1/2 possibilités.

    J'ai formé mes 5 groupes. 10!/(2^5)

    mais comme l'ordre des groupes n'importe pas, je dois encore diviser par 5!

    J'ai donc (10!/(2^5))/5!=945

    Pour le premier jour, j'ai donc 3003*945=2'837'835 possibilités.



    Combien y a-t-il de possibilités de formation de groupes le deuxième jour ? Là ça commence à devenir difficile, terrain peu pratiqué...

    Sachant que le premier jour... et que je ne veux pas que deux filles se retrouvent à côté plus d'un jour...

    Je pense même que ça va être long. Je ne vois pas de raccourci.

    Il faut considérer plusieurs cas : (et pour n jours, ça va être long)

    - Les cinq filles du milieu restent au milieu.
    - 4 filles restent au milieu, celle qui se décentre laisse la place à une de ses voisines et change de groupe.
    - 4 filles restent au milieu, celle qui se décentre laisse la place à une "bordeuse" d'un autre groupe.
    - ...

    Mouah ! possible, mais trop long ! je vais essayer de trouver autre chose.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  19. #15
    shokin

    Re : Une énigme.....

    Oubliez mon post précédent, une botte de foin ! auquel l'on est facilement allergique.

    Pour ne pas perdre la boule à cause de ces filles, je vais parler en terme de boules.

    J'ai 105 boules, 15 de chaque couleur.

    J'ai 7 boîtes de 15 places pour les boules. Chaque boîte comporte 5 compartiments de 3 boules.

    Je dois placer ces boules selon les conditions suivantes :

    - chaque boîte contient une et une seule boule de chaque couleur.
    - deux couleurs de boules peuvent être côte à côte ET dans le même compartiment dans une boîte au plus.

    Combien ai-je donc de possibilités ? je considère toutes les boîtes comme identiques, donc pouvant changer de place dans ma valise.



    Mince, je dois y aller !

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  20. #16
    yat

    Re : Une énigme.....

    Faut que je précise que moi j'ai considéré que j'avais interprété marcher cote à cote comme faire partie du même groupe de trois. Dans mon raisonnement à moi la fille de gauche ne peut donc pas se trouver deux fois dans le groupe du milieu, même si elle n'est directement à coté qu'une fois.

  21. #17
    Talisac

    Re : Une énigme.....

    Salut,

    Je suis certain qu'on peut résoudre ce problème grâce à la combinatoire (bien que je n'ai que de vagues souvenirs de cela )

    Je vais essayer de ressortir mes cours.

    Je pense qu'une voie à suivre serait de calculer le nombre de façon d'arranger 3 filles parmis 15 sans répétition, mais je vais essayer de résoudre ça avant d'avancer des théories foireuses

    Si je repost pas, c'est que j'ai pas trouvé (ou que j'ai été trop fainéant pour chercher ca m'arrive aussi)

  22. #18
    yat

    Re : Une énigme.....

    Citation Envoyé par Talisac
    Je pense qu'une voie à suivre serait de calculer le nombre de façon d'arranger 3 filles parmis 15 sans répétition, mais je vais essayer de résoudre ça avant d'avancer des théories foireuses
    ça fait 455... parmi lesquels on doit en choisir 35 pour avoir les 105 binomes possibles, en sachant que chaque binome est contenu dans 13 triplets différents.
    Tout colle bien, mais comment ça peut prouver qu'il existe une solution ?

  23. Publicité
  24. #19
    Brumaire

    Re : Une énigme.....

    Je pense que on doit pouvoir trouver une solution en appliquant la théorie des graphes...

  25. #20
    shokin

    Re : Une énigme.....

    Qu'est donc la théorie des graphes ?

    et son lien avec le problème ?

    si ça peut nous dépanner efficacément, n'hésite pas.


    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  26. #21
    Apfelstrudel

    Re : Une énigme.....

    Les meeeeeecs ! Pourquoi vous vous compliquez la tâche ? On change juste la fille du milieu à chaque fois et on garde les deux mêmes sur les côtés !!!

  27. #22
    shokin

    Re : Une énigme.....

    Citation Envoyé par Apfelstrudel
    Les meeeeeecs ! Pourquoi vous vous compliquez la tâche ? On change juste la fille du milieu à chaque fois et on garde les deux mêmes sur les côtés !!!
    Durant 7 jours ?

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

Sur le même thème :

Discussions similaires

  1. une énigme facile ^^
    Par matmika dans le forum Science ludique : la science en s'amusant
    Réponses: 13
    Dernier message: 06/07/2008, 21h00
  2. Help me, une énigme
    Par emeline_ dans le forum Science ludique : la science en s'amusant
    Réponses: 8
    Dernier message: 23/10/2007, 16h39
  3. Une énigme
    Par emeline_ dans le forum Science ludique : la science en s'amusant
    Réponses: 12
    Dernier message: 18/02/2007, 14h35
  4. et une énigme de plus ^^
    Par integrity_13 dans le forum Science ludique : la science en s'amusant
    Réponses: 17
    Dernier message: 19/03/2006, 10h30
  5. Une enigme !
    Par Lord dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 20/02/2005, 11h47