Question badine...[tous niveaux]

[doryphore]

31 vacanciers se trouvent sur le même bateau durant le mois de Juillet. Le capitaine (qui n'est pas en vacances) peut inviter chaque soir 6 personnes à sa table. Peut-il faire ses invitations chaque soir du mois de Juillet de sorte que chaque vacancier se soit rencontré une fois et une seule ?

Je n'ai pas la réponse...
-----

[g_h]

Qu'entends tu par "rencontrer" ? Ils ne doivent pas être assis en même temps à la table, ou simplement assis côte à côte ?
Le capitaine doit-il obligatoirement inviter 6 personnes chaque soir ?

[doryphore]

S'être rencontré, c'est avoir été assis à la même table.

Et c'est 6 convives (en plus du capitaine) chaque soir...

On ne demande pas l'age du capitaine...

[doryphore]

Indication: s'intéresser au groupe des automorphimes de corps de

[A voir en vidéo sur Futura]

[Brikkhe]

Indication: s'intéresser au groupe des automorphimes de corps de

Lol!! je ne parle pas chinois... je ne pourrai pas prendre en compte ton indication. merci qd meme!

@pluche!

[doryphore]

Pas grave, il existe sans doute des procédures personnelles qui ne font pas appel à la théorie des corps mais je ne la connais pas non plus...
Pourtant elle m'intéresse autant que la procédure experte...

[GuYem]

Oh ça fait mal à la tête ton truc! Les 31 convives et le mois de juillet qui fait 31 jours, c'est sans doute pas anodin.

Tu n'as pas la réponse, mais est-ce que tu sais si c'est oui ou non, sans avoir le détail? Ca aiderait bien.

[doryphore]

Des questions préliminaires me font penser que c'est probablement oui!!

Etant donné le niveau théorique utilisé dans la procédure experte, je peux te garantir que trouver la réponse à cette question doit être assez hallucinant , même dans une solution qui n'utiliserait pas ces outils théoriques...

[GuYem]

Ca m'a l'air assez intéressant en tous cas. Je dois avouer que j'aime bien ces exemples où on voit que ce qu'on manipule abstraitement en algèbre ça peut, des fois, représenter des vrais trucs (Claude, si tu me regardes )
Tu pourrais donner les questions préliminaires, ici ou MP.

[shokin]

31 vacanciers se trouvent sur le même bateau durant le mois de Juillet. Le capitaine (qui n'est pas en vacances) peut inviter chaque soir 6 personnes à sa table. Peut-il faire ses invitations chaque soir du mois de Juillet de sorte que chaque vacancier se soit rencontré une fois et une seule ?

Je n'ai pas la réponse...

Si chaque vacancier rencontre exactement une et une seule fois chacun des 31 autres vacanciers sur les 31 jours... ben s'ils sont par groupes de 6, ç'a l'air possible de rencontrer 6 fois 5 autres.

Il faut former des groupes de 6 de façon à ce qu'il n'y ait pas deux fois deux éléments distincts qui se rencontrent.

Mais comment trouver à coup sûr une combinaison possible ?

Shokin

[matthias]

J'ai essayé d'aborder le problème avec une approche différente des automorphismes de corps (qui sont un lointain souvenir pour moi ...)

On construit une matrice A 31x31 (eh oui, je sais ...) où les lignes représentent les repas, et les colonnes les vacanciers.
Ai,j = 1 si le vacancier j assiste au repas i (0 sinon)
Pour que le problème soit possible il faut qu'il existe une matrice avec exactement six 1 par colonne, exactement six 1 par ligne, et telle que deux lignes quelconques aient exactement un 1 placé en même position.

Ce qui est intéressant, c'est qu'échanger deux lignes revient à changer l'ordre des repas, et échanger deux colonnes revient à renuméroter les vacanciers, ce qui ne change rien au problème.
Ca permet de donner une forme particulière aux 11 premières lignes et 11 premières colonnes sans perte de généralité, et de réduire le problème en donnant de conditions assez restrictives sur les coefficients restants.

Je ne vais exposer les détails vu que je n'ai pas conclu pour l'instant et qu'expliquer avec LaTeX des bidouilles sur des matrices 31x31, ça me fatigue rien que de l'évoquer.
J'ai quand même l'impression que si c'est possible ça doit vraiment être d'extrème justesse (mais bon ça ne serait pas une surprise).

Sinon pour l'approche par les automorphismes de corps, le fait que 31 soit premier ne doit pas être étranger au problème (et je n'arrive pas à voir en quoi ça peut jouer dans mon approche pour l'instant ...)

[matthias]

J'ai oublié de préciser qu'un découpage de la matrice 31x31 en blocs 5x5 (+ une ligne et une colonne), rend quand même le problème moins horrible, chaque bloc étant de nécessairement (après un peu de travail) de forme très simple. Il me reste en fait 16 blocs 5x5 ayant chacun exactement un 1 par ligne et par colonne, ces blocs devant respecter certaines propriétés simples entre eux.

[shokin]

Je me disais qu'il allait y avoir des matrices !

Un peu comme pour les appariements où chaque équipe d'un groupe joue contre chacune des autres équipes du groupe, en plus compliqué.

Shokin

[matthias]

Je me disais qu'il allait y avoir des matrices !

Un peu comme pour les appariements où chaque équipe d'un groupe joue contre chacune des autres équipes du groupe, en plus compliqué.

Oui, c'est une modélisation assez naturelle, même si ça n'est clairement pas la plus subtile, ni la plus efficace.

[shokin]

Ah ! quelle méthode est plus efficace ? ça m'intéresse, ça pourrait m'être utile.

Shokin

[martini_bird]

Salut,

dans un premier temps, je vous soumets un argument combinatoire qui appuie le fait que le problème doit avoir une solution (en général, il vaut mieux s'en assurer avant! ).

En effet chaque vacancier doit rencontrer 30 personnes. Mais comme la relation est symétrique (si A rencontre B, B rencontre A) celà fait 31x30/2=465 poignées de main.
Or chaque soir il y a 15 poignées de main (sans bien sûr compter le capitaine): au bout de 31 jours, il y aura donc eu 31x15=465 poignées de main.

Le problème devrait donc être résoluble.

Cordialement.

[matthias]

C'est bien le problème. On a pas a priori d'argument combinatoire simple pour dire qu'il n'y a pas de solution. En même temps si le problème admet une solution c'est plutôt normal ...

[martini_bird]

On voit néanmoins que le problème n'a pas de solution si le séjour est plus court ou plus long que 31 jours. C'est déjà ça!

[martini_bird]

En même temps si le problème admet une solution c'est plutôt normal ...

Il vaut mieux être prudent...

Et ça permet de formuler cette conjecture (hautement spéculative, on verra quand on aura résolu le problème): si n vacanciers se voient par groupe de k personnes chaque jour, ils se seront rencontrés une fois et une seule au bout de n jours s'il existe un m tel que:

[martini_bird]

Oubliez mon dernier post!

[invite69b7411e]

Pour le fun, j'ai ce qui semble être une solution:
1 2 3 4 5 6
1 7 8 9 10 11
1 12 13 14 15 16
1 17 18 19 20 21
1 22 23 24 25 26
1 27 28 29 30 31
2 7 12 17 22 27
2 8 13 18 23 28
2 9 14 19 24 29
2 10 15 20 25 30
2 11 16 21 26 31
3 7 13 19 25 31
3 12 18 24 30 11
3 17 23 29 10 16
3 22 28 9 15 21
3 27 8 14 20 26
4 7 18 29 15 26
4 13 24 10 21 27
4 19 30 16 22 8
4 25 11 17 28 14
4 31 12 23 9 20
5 7 24 16 28 20
5 18 10 22 14 31
5 29 21 8 25 12
5 15 27 19 11 23
5 26 13 30 17 9
6 7 14 21 23 30
6 18 9 16 25 27
6 29 11 13 20 22
6 15 8 17 24 31
6 26 10 12 19 28
Bon, c'est fait avec un papier et un crayon... cela demanderait verification avec un ordi... mais il est tard, euh.. non tôt.

[matthias]

Pour moi c'est bon.

[doryphore]

Et bien, c'est un vrai tour de force...
En tout cas ça prouve que la dernière question d'un sujet destiné à réviser la théorie des corps pour préparer l'agrégation peut être résolue avec beaucoup de rigueur et relativement peu de moyens mathématiques.

Je pense qu'il peut être intéressant d'examiner la structure d'une telle solution du point de vue algébrique. Et puis le fait que 31 est premier n'est pas innocent compte tenu des objets étudiés dans une preuve experte.

[Brikkhe]

Pour le fun, j'ai ce qui semble être une solution:
1 2 3 4 5 6
1 7 8 9 10 11
1 12 13 14 15 16
1 17 18 19 20 21
1 22 23 24 25 26
1 27 28 29 30 31
...
6 7 14 21 23 30
6 18 9 16 25 27
6 29 11 13 20 22
6 15 8 17 24 31
6 26 10 12 19 28
Bon, c'est fait avec un papier et un crayon... cela demanderait verification avec un ordi... mais il est tard, euh.. non tôt.

J'avais commencé mais par flemme et car il etait tard, j'ai renoncé!
lol
bravo!

[invite19415392]

Pareil, je m'étais arrêté en commençant les 5 ...

Cela dit, j'aimerais bien avoir une démo 'jolie'.

[matthias]

Pareil, je m'étais arrêté en commençant les 5 ...

Cela dit, j'aimerais bien avoir une démo 'jolie'.

Pareil.
Avec la solution, on peut aussi changer les chiffres de manière à rendre la résolution manuelle impossible.

[martini_bird]

Salut,

je fais remonter ce post pour demander à doryphore s'il voulait bien nous communiquer le sujet original. Merci.

Cordialement.

[G13]

Salut,
On considere l'anneau Z/31.Z
Si on prend l'ensemble E de nombres modulo 31,
{0,0+1,0+1+2, ...,0+1+2+3+4+5}
l'ecart entre deux de ces nombres est different de l'ecart entre deux autres.
Donc les ensembles E, E+1,E+2, ... , E+30 n'ont jamais deux elements en commun.

[martini_bird]

Salut,
On considere l'anneau Z/31.Z
Si on prend l'ensemble E de nombres modulo 31,
{0,0+1,0+1+2, ...,0+1+2+3+4+5}
l'ecart entre deux de ces nombres est different de l'ecart entre deux autres.
Donc les ensembles E, E+1,E+2, ... , E+30 n'ont jamais deux elements en commun.

Merci beaucoup G13!

[G13]

Zut, je me suis trompe.1+2=3 donc mon ensemble de 6 chiffres ne convient pas.
Il faut trouver un ensemble de 6 nombre modulo 31 tel que la difference entre deux de ces nombres est differente de celle entre deux autres.
On procede par recurrence.
Si on peut construire un tel ensemble a n nombres n<6, il y a n*(n-1) ecarts entre ces n nombres donc si x est un nombre de l'ensemble, d un ecart , on ne peut rajouter n+d donc cela nous interdit les n nombres plus n+n*(n-1) nombres .
Comme n<=5, il ya moins de 30 nombres interdit donc il en reste au moins un a disposition que l'on rajoute.