Commentaire sur l'article

• Novembre 2022, 2e défi

  le 11 novembre 2022 à 09:40, par Kamakor

  On peut représenter l’ensemble des concerts par un graphe orienté dans lequel six sommets $A$, $B$, $C$, $D$, $E$ et $F$ représentent les musiciens et à chaque concert on ajoute les vecteurs les vecteurs de $X$ vers $Y$ si $X$ écoute $Y$. On remarque alors qu’il faut $2\times\dfrac{6\times 5}{2}=30$ vecteurs pour que chaque musicien ait écouté tous les autres. Or :
  \
  Si, lors d’un concert $1$ musicien écoute les $5$ autres ou que $5$ musiciens écoutent le sixième, cela ajoute (au maximum) $5$ vecteurs au graphe.
  Si, lors d’un concert $2$ musiciens écoutent les $4$ autres ou que $4$ musiciens écoutent les $2$ autres, cela ajoute (au maximum) $8$ vecteurs au graphe.
  Si, lors d’un concert $3$ musicien écoutent les $3$ autres, cela ajoute (au maximum) $9$ vecteurs au graphe.
  Donc, on peut ajouter au maximum $9$ vecteurs à chaque concert. Et puisque $3\times9=27<30$ il est impossible , en $3$ concerts que chacun ait écouté les autres.
  \
  Il suffit alors de 4 concerts. Par exemple :
  $A$, $B$ et $C$ écoutent $D$, $E$ et $F$ au premier
  $C$, $D$ et $E$ écoutent $F$, $A$ et $B$ au deuxième
  $E$, $F$ et $A$ écoutent $B$, $C$ et $D$ au troisième
  $B$, $D$ et $F$ écoutent $A$, $C$ et $E$ au quatrième

  Répondre à ce message
• Novembre 2022, 2e défi

  le 14 novembre 2022 à 11:44, par Niak

  Petite observation, si l’on généralise votre borne inf. à $n$ sommets, on a $m = n\cdot(n-1)$ arcs ($\sim n^2$) et l’on en ajoute au plus $k = \left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil$ ($\sim\frac{n^2}{4}$) par concert. On a besoin d’au moins $\left\lceil\frac{m}{k}\right\rceil$ concerts, ce qui vaut en fait $4$ pour tout $n\geq5$ (pas très utile pour $n$ grand).

  Répondre à ce message

• Novembre 2022, 2e défi

  le 11 novembre 2022 à 12:05, par Al_louarn

  Chaque musicien joue dans un sous-ensemble de l’ensemble $F = \{1,...,n\}$ des concerts du festival. Pour que chacun écoute l’autre au moins une fois, il faut et il suffit qu’aucun sous-ensemble ne soit inclus dans un autre. On cherche donc une famille de $6$ sous-ensembles de $F$, où aucun n’est inclus dans un autre, ce qu’on appelle une antichaîne.

  Notons qu’une antichaîne contenant au moins $2$ sous-ensembles de $F$ ne peut contenir l’ensemble vide ni $F$ lui-même, ce qui limite le choix aux $2^n-2$ sous-ensembles stricts non vides de $F$.

  Si $n=3$, $F$ a exactement $2^3-2=6$ sous-ensembles stricts non vides, mais ils ne forment pas une antichaîne car par exemple $\{1\} \subset \{1,2\}$.

  En revanche pour $n=4$, on a une solution en prenant les $\binom{4}{2}=6$ paires d’éléments de $F$.
  Il faut donc $4$ concerts au minimum.

  Plus généralement il y a un théorème de Sperner affirmant que la taille maximale d’une antichaîne d’un $n$-ensemble est $\binom{n}{\lfloor n/2 \rfloor}$. Donc pour $n \leq 3$, une antichaîne contient au plus $\binom{3}{1}=3$ sous-ensembles, comme par exemple :
  $\{\{1\},\{2\},\{3\}\}$

  Répondre à ce message
• Novembre 2022, 2e défi

  le 14 novembre 2022 à 13:06, par Niak

  Bien vu en effet. La solution pour $m$ musiciens est donc le plus petit $n$ tel que $\binom{n}{\lfloor n/2\rfloor}\geq m$. En passant par Stirling, $\binom{n}{n/2} = O\left(\frac{2^n}{\sqrt{n}}\right)$ donc asymptotiquement $n$ est disons « un peu plus grand » que $\log_2 m$.
  C’est ce à quoi l’on pouvait s’attendre en remarquant qu’un tel ensemble de concerts permet de jouer à « Qui est-ce ? » à base de questions du type « A-t-il participé à tel concert ? ». On sait qu’il faut alors au moins $\lceil\log_2 m\rceil$ questions (dans le pire cas).

  Répondre à ce message