Combinatoire nouveau defi

[Mario2015]

On a 252 quintuplets formes a partir de 10 numeros (1 a 10).
C(10,5)=252

On definit une relation "fraternite" entre 2 quintuplets de la maniere suivante : si 2 quintuplets ont 4 numeros en commun on les designe comme freres.
Exemple :
1-2-3-4-5 et 1-2-3-4-7 sont "freres".
Chaque quintuplet a exactement 25 "freres" (C(5,4)*5=25).
On cherche a placer les 252 quintuplets autour d`une table circulaire de telle sorte que chaque quintuplet soit aussi eloigne que possible de ses 2 freres (celui a sa droite et celui a sa gauche).
On definit un rayon uniforme r comme etant le nombre de places a gauche du quintuplet et a droite du quintuplet.
Exemple :
Un quintuplet assis quelque part sur un siege autour de la table n`a aucun frere assis dans un rayon r=4 veut dire que sur les 4 sieges a sa gauche et sur les 4 sieges a sa droite aucun de ses freres n`y est assis.

Quel est le rayon maximal que l`on peut se permettre si on vise a ce qu`un quintuplet pris au hasard soit aussi loin que possible de ses 2 freres (a gauche et a droite)?

On ne cherche qu`une seule solution abstraction faite des permutations.

[zygomatique]

salut

252 quintuplets
tout quintuplet a 25 frères

r < 252/26 ... est une borne largement supérieure à la valeur théorique ...


soient a et b les quintuplets (1, 2, 3, 4, 5) et (6, 7, 8, 9, 10) non frères

chacun d'eux a 25 frères qui ne seront jamais frère de l'autre

donc r < 252/52

je subodore même fortement qu'au moins deux frères sont cote à cote ....

[Mario2015]

Quelques precisions sur la notion de "fraternite" :

A=1-2-3-4-5

B=1-2-3-4-6

C=2-3-4-6-7

A a un frere B
B a un frere C

cela n`implique pas que A et C sont freres vu que A et C ont 3 numeros en commun.
Donc C peut s`asseoir a cote de A et vice versa

[zygomatique]

je l'avais compris ainsi ...

le frère d'un frère n'est pas forcément frère ...

[Mario2015]

Pas de probleme donc.
L`enonce semble clair.
De meme le rayon r = r places a gauche, r places a droite partant de la place assise du quintuplet concerne.

[Mario2015]

La par contre il y a un algo rapide pour trouver la solution.

[Mario2015]

Enfin, resolu!
Je posterai la solution tres prochainement sur le site.

[Mario2015]

Erreur dans ma solution.
Donc toujours rien! Meme si je comprends mieux comment solutionner ce probleme.
il y a une symetrie interessante a exploiter.

[Mario2015]

En eclatant les 252 quintuplets en 2 sous-ensembles : 126+126, il suffirait de solutionner l`un de 2 pour que par symetrie on ait la solution globale.
J`attaque des demain.