Un défi par semaine

Novembre 2022, 2e défi

Le 11 novembre 2022  - Ecrit par  Ana Rechtman Voir les commentaires (4)
Lire l'article en  

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante.

Le calendrier 2022 s’intitule : « Les maths, une aventure humaine ».

Toute une année pour partir à la découverte  de femmes et d’hommes qui, à  travers leur travail, leurs échanges, leur  génie  mais aussi leurs contradictions, ont  construit les mathématiques.

Semaine 45

Six musiciens participent à un festival. Pour chaque concert, quelques-uns d’entre eux jouent et les autres sont spectateurs. Quel est le nombre minimal de concerts qu’ils doivent faire pour que chaque musicien ait écouté tous les autres ?

Solution du 1er défi de novembre 2022 :

Enoncé

En factorisant l’expression $n^3-n$, nous obtenons :
\[n^3-n=n(n^2-1)=n(n+1)(n-1)=(n-1)n(n+1),\]
qui est le produit de trois nombres entiers consécutifs,
ce qui implique qu’au moins l’un d’entre eux est multiple de 2 et que l’un de ces nombres est multiple de 3.

On peut donc affirmer que $n^3-n$ est toujours un multiple de $2\times3=6$.

De plus, pour $n=2$, on obtient $n^3-n=6$, donc il ne peut pas exister d’entier plus grand que $6$ qui divise $n^3-n$.

La réponse est 6.

Post-scriptum :

Calendrier mathématique 2022 - Sous la direction d’Ana Rechtman Bulajich.

Partager cet article

Pour citer cet article :

Ana Rechtman — «Novembre 2022, 2e défi» — Images des Mathématiques, CNRS, 2022

Commentaire sur l'article

  • Novembre 2022, 2e défi

    le 11 novembre à 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 à 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 à 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 à 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

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?