Défis du calendrier mathématique Retour à la rubrique

Un défi par semaine

Décembre 2020, 2e défi

Le 11 décembre 2020 - Ecrit par Ana Rechtman Voir les commentaires (7)
Lire l'article en

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

Le calendrier 2021 est en vente ! Il s’intitule : « Le ciel dans tous ses états ».
De janvier à décembre, à travers 12 textes superbement illustrés, découvrez l’histoire des équations cachées dans les trajectoires des planètes et des étoiles ainsi que le développement des grandes théories qui ont accompagné cette aventure.

Semaine 50
Un groupe de personnes assiste à une fête. Chacune connaît au plus trois personnes et si deux personnes ne se connaissent pas, elles ont au moins une connaissance commune. Combien y a-t-il de personnes au maximum ?

Solution du 1er défi de décembre :

Enoncé

La réponse est : $\dfrac{5}{36}$

Si on note $j, k$ et $l$ les probabilités de victoire respectives de Jeanne, Karim et Laura à chaque manche, on a $j=\frac 12, k=2l$ et $j+k+l=1$ (car il y a un et un seul vainqueur à chaque manche).
La dernière équation se réécrit $3l=1-j=\frac 12$ et donc $l=\frac16$. On a alors $k=\frac13$.

Maintenant si Jeanne gagne trois manches, Karim deux et Laura une, le résultat dans l’ordre des manches est une permutation de $JJJKKL$, où la $i$-ème lettre du mot correspond à la victoire de la manche correspondante.

Il y a en tout $6!=6\times5\times4\times3\times2\times1$ permutations possibles d’un mot à six lettres, mais, parmi celles-ci, permuter les lettres $J$ entre elles ou les lettres $K$ ne change pas le mot obtenu.

Comme il y a $3!$ façons de permuter les $J$ et $2!$ façons de
permuter les $K$, le nombre total de permutations du mot $JJJKKL$ est
\[\frac{6!}{3!2!1!}=\frac{6\times5\times4\times3\times2\times1}{3\times2\times1\times2\times1\times1}=60\].

Enfin la probabilité que le résultat des manches soit, dans l’ordre, $JJJKKL$ est
\[\frac 12\times \frac 12\times \frac 12\times \frac 13\times\frac13\times\frac16=\frac1{2^3\times 3^2\times 6}\].
En multipliant par le nombre de permutations possibles du résultat des manches, on a donc une probabilité de
\[\frac{60}{2^3\times 3^2\times 6}=\frac5{36}\]
pour trois victoires de Jeanne, deux victoires de Karim et une victoire de Laura.

Post-scriptum :

Calendrier mathématique 2020 - Sous la direction d’Ana Rechtman, avec la contribution de Nicolas Hussenot - Textes : Serge Abiteboul, Charlotte Truchet. 2019, Presses universitaires de Grenoble. Tous droits réservés.

Disponible en librairie et sur www.pug.fr

Commentaire sur l'article

Décembre 2020, 2e défi

le 11 décembre 2020 à 08:14, par Christophe Boilley

Il y a une majoration facile à obtenir en partant d’un individu et en comptant les contacts de ses contacts. Reste à trouver un exemple de réalisation, et il se construit facilement avec un algorithme glouton. Du coup, je me demande même si tous les graphes solutions (maximisant le nombre de participants) sont isomorphes.
Répondre à ce message

Décembre 2020, 2e défi

le 12 décembre 2020 à 10:17, par Al_louarn

Oui, chaque personne en connaît au plus $3$ qui en connaissent au plus $2$ autres, ce qui fait $1 + 3 + 2 \times 3 = 10$ fêtards au maximum. Mais pour atteindre ce maximum de $10$ sommets il faut que tous les sommets du graphe soient de degré $3$, autrement dit le graphe doit être cubique. L’autre contrainte impose un graphe de diamètre $2$. Or le graphe de Petersen est le plus grand graphe cubique de diamètre $2$, et il a bien les $10$ sommets requis : pour le construire, prenez par exemple pour sommets les $10$ paires d’un ensemble à $5$ éléments et reliez entre elles les paires disjointes. La solution est donc effectivement unique à isomorphisme près.
Répondre à ce message

Décembre 2020, 2e défi

le 11 décembre 2020 à 14:41, par pogarreau

La contrainte d’avoir une connaissance commune limite sacrément le nombre de fétards à la soirée. Elle respecte par ailleurs la consigne gouvernementale :-)
Répondre à ce message
Décembre 2020, 2e défi

le 11 décembre 2020 à 14:42, par pogarreau

La contrainte d’avoir une connaissance commune limite sacrément le nombre de fétards à la soirée. Elle respecte par ailleurs la consigne gouvernementale du moment pour la Covid-19 :-)
Répondre à ce message

Décembre 2020, 2e défi

le 12 décembre 2020 à 10:10, par orion8
Chacun peut se convaincre avec des schémas que jusqu’à $6$ personnes, il n’y a pas de problème (les graphes complets d’ordre inférieurs à $5$ conviennent, car les degrés doivent être inférieurs à $4$)
A partir de $7$ personnes, chacun a au moins $3$ inconnus autour de lui (s’il en avait moins, il connaîtrait au moins $4$ personnes).
- La 1ère personne va utiliser l’intermédiaire n°1 pour la relier à $2$ inconnus, pas plus, sinon cet intermédiaire connaîtrait plus de $3$ personnes, et l’intermédiaire n°2 pour la relier à un 3ème inconnu.
- La 2ème personne va réutiliser l’intermédiaire n°2 pour la relier à $1$ inconnu, pas plus, sinon cet intermédiaire connaîtrait plus de $3$ personnes, et l’intermédiaire n°3 pour la relier à $2$ autres inconnus.
- La 3ème personne va utiliser l’intermédiaire n°4 pour la relier à $2$ inconnus, et l’intermédiaire n°5 pour la relier à un 3ème inconnu.
- La 4ème personne va réutiliser l’intermédiaire n°5 pour la relier à $1$ inconnu, et l’intermédiaire n°6 pour la relier à $2$ autres inconnus.
A partir de là, on voit qu’il manque un intermédiaire pour la 5ème. Donc $6$ serait le nombre maximum, soit bien la consigne gouvernementale !

Mon raisonnement admet peut-être des failles. En tout cas, il s’agit d’un graphe quasi fortement connexe, qui admet donc une racine. Une autre piste à suivre ?
Répondre à ce message

Décembre 2020, 2e défi

le 17 décembre 2020 à 19:34, par Al_louarn

Il y a forcément des failles dans votre raisonnement, puisque la réponse est $10$ : comme indiqué dans mon message précédent, le graphe de $\href{https://fr.wikipedia.org/wiki/Graphe_de_Petersen}{Petersen}$ satisfait les deux contraintes, et on ne peut pas faire mieux.
Répondre à ce message

Décembre 2020, 2e défi

le 18 décembre 2020 à 09:39, par orion8

Bonjour, à la minute où je postais mon commentaire, je vois le vôtre apparaître ! Et je m’aperçois de mon erreur : j’ai utilisé $3$ au lieu de « au plus $3$ »...
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.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Ana Rechtman

Un défi par semaine

Décembre 2020, 2e défi

Solution du 1er défi de décembre :

Commentaire sur l'article