$n$ parmi $\binom {2n}{n}$
Bonsoir
Soit $n\in \mathbb N_{\geq 2}$.
Comment choisir $n$ parties de cardinal ${\color{red}{n}}$ de $1,2n$ de façon que déjà la somme des cardinaux de leurs $\binom {n}{2}$ intersections deux à deux soit minimale et que, de plus, la différence entre le maximum et le minimum de ces cardinaux soit minimale ?
Edit
Merci d'avance pour votre aide.
Cordialement
Paul
Soit $n\in \mathbb N_{\geq 2}$.
Comment choisir $n$ parties de cardinal ${\color{red}{n}}$ de $1,2n$ de façon que déjà la somme des cardinaux de leurs $\binom {n}{2}$ intersections deux à deux soit minimale et que, de plus, la différence entre le maximum et le minimum de ces cardinaux soit minimale ?
Edit
Merci d'avance pour votre aide.
Cordialement
Paul
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Merci pour ta réponse.
Paul
j'espère avoir répondu à ma propre question mais je ne donne pas encore ma solution.
Je tente de vous motiver via l'origine de ma question:
Ca se passe dans un pays barbare, mais moins qu'un autre, vu qu'il faut déjà avoir volé pour se faire couper la main. Et pas si barbare en fait puisqu'aux $n$ voleurs on offre une chance de sauver leur main:
On les prévient qu'après avoir déjeûné tous ensemble, ils passeront un par un dans un isoloir (avec un maton incorruptible) où sont alignées $2n$ boites fermées. Chaque boîte non vide contient le matricule d'un voleur. Chaque voleur a son matricule dans une et une seule des $2n$ boîtes. Chaque voleur a le droit d'ouvrir $n$ boîtes de son choix. Si l'un d'entre eux ne trouve pas son matricule dans les boîtes qu'il ouvre, tous sont amputés; sinon tous sauvent leur main.
Quelle est la probabilité que tous sauvent leur main?
Si vous trouvez vite, veuillez bien donner votre solution à l'encre sympathique.Merci
Cordialement
Paul
Pas une réponse! Or vous n'êtes point tous fervents défenseurs de la barbarie.
L'heure est venue de me battre les coulpes. J'en ai deux:
$\bullet$ La première est d'avoir cru répondre à ma propre question alors que ma réponse (voir plus bas) est au mieux une conjecture.
$\bullet$ $\bullet$ La seconde est d'avoir mal compris l'énoncé du problème des voleurs donné par un ami. Je le rectifie (voir encore plus bas).
$\bullet$ Ma conjecture est que les colonnes des matrices suivantes sont solutions de mon problème dans les cas $n=1,2,3,4,5,6$. Par suite de crasse en Latex, pour préserver l'alignement vertical, j'ai écrit $d,o,e$ au lieu de $10,11,12$
1
12
43
112
233
456
1124
2335
4566
8787
11122
23334
44555
68d79
7968d
111226
233347
445558
68d799
7968dd
eoeoeo
Heuristique: les $2n$ nombres de $1,2n$ doivent apparaître dans la matrice si possible avec la même fréquence, soit $\frac{n}{2}$. Ce n'est réalisable que si $n$ est pair! Si donc $n$ est impair, $n$ des $2n$ nombres de $1,2n$ (SPDG $1,2,...n$) apparaîtront chacun une fois de plus que chacun des $n$ autres (SPDG $n+1,....2n$). Les premiers apparaissent chacun $\frac{n+1}{2}$ fois , les seconds $\frac{n-1}{2}$ fois.
La matrice si $n$ est impair:
J'écris comme d'habitude (de gauche à droite, puis de haut en bas) tous mes $1$, puis tous mes $2$, ...puis tous mes $n$. J'ai ainsi rempli les $\frac{n+1}{2}$ premières lignes de la matrice.
Puis je n'écris plus comme d'habitude les $\frac{n-1}{2}$ lignes suivantes: je les écris de haut en bas, puis de gauche à droite ("façon verticale" des mots-croisés). J'écris $n+1, n+2, ..2n$ et je recommence $n+1, n+2, ..2n$ ... Je termlne donc en écrivant $2n$ dans la "case $n,n$"
J'espère que mes trois exemples aident à comprendre ce fumeux propos!
La matrice si $n$ est pair:
On prend la matrice $n-1$ et on la borde par la colonne $n$ et la ligne $n$ ainsi construites:
Dans la colonne $n$ j'écris de haut en bas $n,n+1,...2n-1$.
Dans la ligne $n$, j'alterne les $2n$ et les $2n-1$ (sachant que j'ai dit que$"a_{n,n}"=2n-1$).
Il va sans dire que je préfère un contre-exemple au silence ;-)
$\bullet$ $\bullet$ J'avais compris, à tort, qu'il y avait $n $ voleurs et $2n$ boîtes dont $n$ vides. En vérité, il y a $2n$ voleurs et $2n$ boîtes. Chaque boîte contient un seul matricule et tout matricule est contenu par une boîte. Chaque voleur peut ouvrir $n$ boîtes de son choix.
Je ne sais pas si ma solution du problème des voleurs (dans sa nouvelle version ci-dessus) est la meilleure, mais j'ai trouvé qu'il y avait plus de $30$% de chances que les voleurs s'en sortent. Quant à ma question primitive, je ne lui vois plus le moindre rapport avec le problème des voleurs dans sa nouvelle version!
N'empêche, toute réponse à l'une ou l'autre question me ferait plaisir.
Amicalement
Paul
Les voleurs se sauvent tous si chacun trouve son numéro en moins de n essais, ce qui revient à demander que la permutation de [1;2n] donnée par la correspondance entre les matricules et les boîtes n'ait pas d'orbite à plus de n éléments.
Or on sait que pour n grand, la limite de la proportion de ce type de permutations est 1/e, soit entre 36 et 37%.
Merci Frédéric pour ta réponse. Tu as bien décodé ce que je voulais dire! Nous avons bien pensé à la même stratégie.
En revanche, la limite est selon toi $1/e$ tandis que je trouve $1-\ln 2$. A suivre...
Cordialement
Paul
$c_n$ est le nombre de permutations de $1,2n$ divisibles par un cycle de longueur strictement supérieure à $n$.
Pour tout $k\in 1,n$, $c_{n,k}$ est le nombre de permutations de $1,2n$ divisibles par un cycle de longueur $n+k$.
$\bullet$ Une permutation de $1,2n$ ne pouvant être divisée par deux cycles de longueur strictement supérieure à $n$, $$c_n=\sum_{k=1}^n c_{n,k}.
$$ $\bullet\! \bullet$ Pour tout $k\in 1,n$, tout cycle de longueur $n+k$ divise exactement $(n-k)!$ permutations de $1,2n$.
$\bullet\! \bullet\! \bullet$Toute partie de $n+k$ éléments de $1,2n$ est "mère" de $(n+k-1)!$ cycles de longueur $n+k$ (et deux mères distinctes ne partagent aucun fils). Le nombre de cycles de longueur $n+k$ est donc $\dbinom {2n}{n+k} (n+k-1)!$, soit $\dfrac {1}{n+k} \dfrac {(2n)!}{(n-k)!}$
$\bullet\! \bullet\! \bullet\! \bullet$ $c_{n,k}$, le nombre de permutations divisibles par un cycle de longueur $n+k$ est donc (via $\bullet\!\bullet$ et $\bullet\!\bullet\!\bullet$) $\dfrac {1}{n+k} \dfrac {(2n)!}{(n-k)!}$ $(n-k)!$, soit $\dfrac {1}{n+k} (2n)!$
Donc $$c_n=\sum_{k=1}^n c_{n,k}=(2n)!\sum_{k=1}^n {\frac {1}{n+k}}=(2n)! (H_{2n}-H_n).
$$ La probabilité que les $2n$ voleurs sauvent leur main est donc, avec notre stratégie, exactement $1-(H_{2n}-H_n)$; elle décroît vers $1-\ln 2$ quand $n$ croît indéfiniment.
En hommage aux amputés qui n'ont même pas volé et à qui les chiens de notre président n'ont laissé aucune chance.
Cordialement
Paul