Une énigme.....

[invite5cfe9b8f]

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

[shokin]

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

[invite14ea0d5b]

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 ?

[invite5cfe9b8f]

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

[A voir en vidéo sur Futura]

[shokin]

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

Mais alors ! c'est encore plus possible !

Je vais y réfléchir mieux.

Shokin

[invite00411460]

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.

[invitedebe236f]

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

[shokin]

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

[invite5cfe9b8f]

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

[invite00411460]

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}

[yat]

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)

[invite5cfe9b8f]

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

[yat]

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 2ⁿ-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.

[shokin]

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

[shokin]

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

[yat]

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.

[invite4270dbf1]

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)

[yat]

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 ?

[invite56460777]

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

[shokin]

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

[inviteb3bf6193]

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 !!!

[shokin]

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