Combinatoire nouveau defi

Olympiades mathématiques, énigmes et défis
Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

Combinatoire nouveau defi

par Mario2015 » 28 Aoû 2015, 17:36

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.



Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 14:31

par zygomatique » 28 Aoû 2015, 19:18

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 ....
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 28 Aoû 2015, 19:32

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

Avatar de l’utilisateur
zygomatique
Habitué(e)
Messages: 6928
Enregistré le: 20 Mar 2014, 14:31

par zygomatique » 28 Aoû 2015, 21:24

je l'avais compris ainsi ...

le frère d'un frère n'est pas forcément frère ...
Ce qui est affirmé sans preuve peut être nié sans preuve. EUCLIDE

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 28 Aoû 2015, 21:50

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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 28 Aoû 2015, 23:32

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

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 30 Aoû 2015, 23:04

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

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 31 Aoû 2015, 18:09

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
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 09 Sep 2015, 03:22

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.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite