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

[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