Combinatoire

[invite98d93111]

Salut,

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.

J`ai du mal a circonscrire le probleme.
J`ai fait des tests et je trouve r=5
Merci de m`eclaircir.
-----

[invitedf478b73]

Bonsoir,
Je n'ai pas bien tout compris, tu peux répondre à mes deux questions:
combien de sièges dans cette table?
Est-ce-que le rayon r à gauche doit toujours être égal au rayon à droite?

[invite98d93111]

Il y a 252 sieges autour de la table.

Un rayon egal a 6 signifie 6 sieges a gauche et 6 sieges a droite.
Quand je dis 6 c`est 6 ou plus (pas exactement 6).
Aucun frere assis sur les 6 sieges a gauche et sur les 6 sieges a droite .
Si le rayon maximal est de 6 cela veut dire que si l`on prend n`importe quel siege des 252 le quintuplet doit n`avoir aucun frere assis sur les 6 sieges a sa droite et aucun sur les 6 sieges a sa gauche.
Il suffisait de bien lire pour le comprendre.
D`autres eclaircissements?

Merci

[invitedf478b73]

d'après ce que je comprends, Il y'a deux façons pour calculer r
On considère un quintuplet ABCDF , Ce quintuplet sera assis dans un siège S, comme le présente mon schéma

siège(r) ◄........◄ siège(2) ◄ siège(1) ◄ ABCDF ►siège(1)►siège(2)►...... ..► siège(r)

Les siège de 1 à r sont assis par des quintuplets non-frères à ABCDF
donc pour résoudre ton problème, il suffit de dénombrer les quintuplets non-frères et diviser par deux.



essaye de trouver r maintenant, il sera plus grand que tu as conçu

[A voir en vidéo sur Futura]

[invitedf478b73]

j'ai pas fait trop attention à cette phrase

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

tu me tiens au courant a+

[invite98d93111]

La question n`est pas de calculer r maximal mais de realiser cette contrainte.
Un quintuplet assis a la place S doit repondre a une contrainte unique : ne pas avoir de freres assis dans un rayon maximal r.
Sur les 25 freres seuls 2 ne doivent pas etre assis dans un rayon r maximal.
La relation de fraternite n`est pas triangulaire.

A=1-2-3-4-5
B=1-2-3-4-6
C=2-3-4-6-7

A a comme frere B
B a comme frere C
mais A n`est pas le frere de C et peut donc s`asseoir a cote (et vice-versa). A et C n`ont que 3 elements en commun.

Le probleme est bien plus complique qu`une simple "regle de trois".
Merci pour ton intervention.
Ps : je pense avoir trouve la solution, je la posterai plus tard.

[invite98d93111]

Desole, je suis alle trop vite.
Pas encore de solution publiable.
Je retourne a mon boulot.

[Médiat]

Bonjour,

Il est facile de majorer n par (Nombre de N° - Nombre de N° choisis), ici (10 - 5);

[invite98d93111]

Bonjour,

Il est facile de majorer n par (Nombre de N° - Nombre de N° choisis), ici (10 - 5);

Salut,

je n`ai rien compris ton commentaire.

Majorer n?

[Médiat]

Majorer le rayon

[invite98d93111]

Majorer le rayon c`est ce que l`on cherche.
Trouver le rayon maximal tel que .....

[invitedf478b73]

Peut-être cela va éclairer le problème, on peut générer 25 frère de chaque quintuplet, le total sera 26 frères
Exemple, prenons le quintuplet 12345, ça va donner les frères suivants:

12345 ___ 12356 ............. 134510
12346 ___ 12357 ............. 23456 ______ Tous ces quintuplets sont frères
12347 ___ 12358 ............. 23457 ______ car ils ont 4 chiffre en commun
12348 ___ 12359 ............. 23458
12349 ___ 123510 ............. 23459
123410___12456 ............. 234510


Il y'a 252 sièges disponibles donc faut distribuer chaque 26 frères de façons qu'ils aient le même rayon, cela revient à partitionner 256 ensembles en 26 ensembles équilibrés.



C'est à dire chaque frère doit être éloigné de son frère d'un rayon 9 ou 10( il se peut que le rayon à gauche ne vaut pas le rayon à droite)
il reste un autre point, on a mis juste 26 quintuplets dans leurs sièges, il reste à mettre 252-26 quintuplets dans les autres sièges vacants de façons qui'ils gardent le même rayon r.

[invite98d93111]

Il faut tenir compte du fait que la relation de fraternite n`est pas triangulaire.
Relire plus haut.
Cela donnerait un rayon bien plus grand (>=9).
Je cherche un moyen bien plus simple.
On peut demarrer le cercle des 252 quibtuplets avec une distribution aleatoire des sieges.
Quitte a la "purifier" au fur et a mesure par substitution des sieges. Ceux qui sont bien places on les garde a leur place, les autres on intervertit leurs places pour voir (swapping).
En partant bien sur d`un rayon determine (9 par exemple).
Si c`est bon pour 9 on pousse a 10 etc....
Faut trouver le meilleur algorithme je pense.

[invite9dc7b526]

Il faut tenir compte du fait que la relation de fraternite n`est pas triangulaire.

c'est transitive qu'on dit dans ce bizness.

[invite98d93111]

c'est transitive qu'on dit dans ce bizness.

Si tu veux. L`essentiel est que mon exemple parle de lui-meme.
Cela dit, le probleme pose est complexe. Pas facile a resoudre mais j`y bosse.
Sa solution me permettrait de resoudre un autre probleme...
On verra bien.

[invite98d93111]

Peut-être cela va éclairer le problème, on peut générer 25 frère de chaque quintuplet, le total sera 26 frères
Exemple, prenons le quintuplet 12345, ça va donner les frères suivants:

12345 ___ 12356 ............. 134510
12346 ___ 12357 ............. 23456 ______ Tous ces quintuplets sont frères
12347 ___ 12358 ............. 23457 ______ car ils ont 4 chiffre en commun
12348 ___ 12359 ............. 23458
12349 ___ 123510 ............. 23459
123410___12456 ............. 234510


Il y'a 252 sièges disponibles donc faut distribuer chaque 26 frères de façons qu'ils aient le même rayon, cela revient à partitionner 256 ensembles en 26 ensembles équilibrés.



C'est à dire chaque frère doit être éloigné de son frère d'un rayon 9 ou 10( il se peut que le rayon à gauche ne vaut pas le rayon à droite)
il reste un autre point, on a mis juste 26 quintuplets dans leurs sièges, il reste à mettre 252-26 quintuplets dans les autres sièges vacants de façons qui'ils gardent le même rayon r.

Par exemple sur ta liste :
1-2-3-4-7 peut se placer a cote de 1-2-3-5-8 car ils n`ont que 3 numeros en commun 1-2-3
Donc cela augmente le rayon maximal puisqu`en placant les l`un a cote de l`autre on a moins de 26 quintuplets a placer. D`autres peuvent etre places cote a cote meme si ces 25 combinaisons sont les freres de 1-2-3-4-5
Il y a d`autres interactions a prendre en ligne de compte....
Un vrai casse-tete!
Seul un genie peut nous sortir de la!
Oh! genie montre-toi!
(Aladin frotte sa lampe).

[invitedf478b73]

Oui tu as raison, le problème est encore compliqué, mais je vais consacrer un peu du temps pour le résoudre.

[invitedf478b73]

Mais est-ce que tu peux me dire où tu as trouvé ce problème , ou tu l'as créé toi même

[invite98d93111]

Mais est-ce que tu peux me dire où tu as trouvé ce problème , ou tu l'as créé toi même

Le probleme a surgi lorsque j`ai voulu solutionner un autre probleme.
Je l`ai poste sur d`autres forums.
Je ne suis pas programmeur mais j`ai deja 3 algorithmes pour le solutionner.
La j`utilise Excel + mes neurones.
J`ai des solutions mais fastidieuses. Comme je suis paresseux, je cherche la moins fatigante.
On peut toujours imprimer les 252 quintuplets, les numeroter de 1 a 252. Les decouper avec une paire de ciseaux et les classer sur une table jusqu`a trouver la solution. Sauf que cela demande du boulot et surtout il ne faut pas se gourrer.
Un bon programmeur dans la salle?

[azizovsky]

Bonjour, puisque la relation r(max) doit s'appliquer sur tous les frères, on prend une seule ensemble de frère et on applique une 'rotation de la loi' sur les autres frères, r(max)=252/25=10.08~10.
d'après tes calculs, il y'a 25 frères, d'où sort 26 frères?

[invite98d93111]

Bonjour, puisque la relation r(max) doit s'appliquer sur tous les frères, on prend une seule ensemble de frère et on applique une 'rotation de la loi' sur les autres frères, r(max)=252/25=10.08~10.
d'après tes calculs, il y'a 25 frères, d'où sort 26 frères?

Chaque quintuplet a 25 freres (4 numeros en commun) : C(5,4)*C(5,1).
Lui + 25 = 26
La question n`est pas que de dire le rayon maximal est de 10 point barre.
Encore faut-il le montrer en placant les quintuplets sur leurs sieges.
Ce n`est pas une affaire de 252/25 ou 252/26......
Faut bien lire l`enonce.
Jusqu`a present on se perd dans les details sans aborder le fond du probleme.
Moi, j`arrete ici.
Je reviendrai lorsque j`aurai ma solution en main.

Merci quand meme.

[azizovsky]

ok, désolé si..., moi, j'utilise la méthode d'un nul en math, je prend un doublet pour 4 chiffres, je cherche le rayon, un triplet pour 6 chiffres,.... et je passe à la généralisation.

[invite98d93111]

ok, désolé si..., moi, j'utilise la méthode d'un nul en math, je prend un doublet pour 4 chiffres, je cherche le rayon, un triplet pour 6 chiffres,.... et je passe à la généralisation.

Poste alors tes resultats, j`attends.

[jiherve]

Bonsoir,
Comme çà, au deboté, cela me fait penser au problème de base des codes détecteur/correcteur d'erreur et à la distance de Hamming mais c'est tout.
JR

[invite9dc7b526]

La question n`est pas que de dire le rayon maximal est de 10 point barre.
Encore faut-il le montrer en placant les quintuplets sur leurs sieges.

déterminer le rayon maximum et trouver un algorithme pour placer les quintuplets autour de la table sont des problèmes différents.

[invite98d93111]

déterminer le rayon maximum et trouver un algorithme pour placer les quintuplets autour de la table sont des problèmes différents.

Impossible de dire quel est le rayon maximal si on ne place pas les quintuplets autour de la table.
r=1 est tres facile a resoudre
r maximal est un terrible casse-tete car les quintuplets sont tres lies.
Il y a 252! manieres de placer les 252 autour d`une table.
Il y en a quelques unes qui maximisent le rayon tel que dans ce rayon r aucun frere n`y soit assis. On ne peut pas le savoir d`avance par "une regle de trois". Ce serait trop simple.

Allez-y! Essayez de placer vos quintuplets autour de la table pour comprendre la difficulte du travail.
Cela fait 3 jours qu`a mes heures perdues j`essaie. Sans succes.
Je reussis a en placer certains dans un rayon determine mais il y en a d`autres qui violent la regle.
J`essaie bien sur une solution logique et facile a mettre en oeuvre.
Je ne vais quand meme pas me taper les 252! (la solution existe!)

[invite98d93111]

Au prix d`une procedure longue (plusieurs etapes) il est theoriquement possible d`obtenir r >=11.
L`idee est la suivante :
On a 12 quintuplets tels qu`aucun quintuplet n`est le frere de l`autre :

3-5-7-8-9
1-2-3-4-5
1-2-6-7-8
1-3-6-9-10
2-4-7-9-10
4-5-6-8-10
1-2-4-6-10
6-7-8-9-10
3-4-5-9-10
2-4-5-7-8
1-3-5-6-8
1-2-3-7-9
Ces quintuplets sont construits sur lordre : (1-2-3-4-5)-(6-7-8-9-10)
On peut obtenir par permutation (il y en a 252 possibles) 20 autres sous-ensembles de 12 quintuplets pour couvrir la totalite des 252 quintuplets.

A partir de la il faudrait assembler ces 21 sous-ensembles de 12 (21*12=252) et les classer de maniere a ce que chaque quintuplet soit le plus eloigne de ses 2 freres. On peut le faire de maniere lineaire tout en tenant compte de la circularite (les 12 premiers sont reproduits en italique pour verifier). Cela donne 252+12=264 lignes.
On est quasiment sur d`avoir r>=11.
Pas facile a realiser. Je vous laisse et je posterai les resultats une fois fini mon boulot.
Il se peut que quelqu`un puisse avoir une idee meilleure et plus simple a realiser.
Qu`il s`avance, je le remercie d`avance.

[Resartus]

Il me semble qu'avec votre définition de r qui doit exclure les frères à droite comme à gauche, cela ne donne que r=5

[invite98d93111]

Il me semble qu'avec votre définition de r qui doit exclure les frères à droite comme à gauche, cela ne donne que r=5

Faut le prouver et le montrer.
Je commence a en avoir ras-le-bol des intervenants qui ne prennent pas la peine non seulement de lire ce qui a ete ecrit mais aussi de mettre la main a la pate.
Essayez de realiser votre cinq!!! Faites-le!!!

Je me barre!
Vous pouvez fermer ce fil de discussion.
Je continuerai tout seul.

Merci.

[Médiat]

Bonjour,

A la demande de l'auteur, qui en "ras-le-bol" : on ferme !

Médiat, pour la modération