Rien que le fait de se poser la question devrait faire pencher la balance d’un côté, non ? Peut-être pas, car se poser cette question signifie qu’il faut absolument trouver le bon regard pour que cela devienne simple, évident. Voilà, en fait la réponse est probablement : « Oui, c’est évident mais je ne vois pas pourquoi… »
Tiens, voici un petit problème, c’est à y perdre son latin !
Marie-Jeanne anime l’entraînement des jeunes basketteurs. Elle partage la classe en 6 et prépare 6 ateliers à thème. Toutes les 10 minutes, on tourne, chaque petit groupe doit aller faire un nouvel atelier. Après une heure, tout le monde doit avoir goûté à tous les ateliers. Classique comme méthode.
Cette fois, les enfants étaient un peu plus joueurs, ou plus impatients pour certains ateliers. Les deux premières permutations se sont bien déroulées, mais pour la troisième, les enfants sont tombés sur un os. Même en discutant globalement, ils n’ont pas trouvé de permutation qui satisfasse chacun !
Bien sûr, si quelques groupes avaient forcé des choix, on imagine bien les autres puissent tomber sur une impossibilité, prenez l’exemple de 3 groupes pour 3 ateliers : deux groupes qui échangeraient leurs postes ne laisseraient pas de choix au troisième !
Mais ce n’est pas là la question, il semblait impossible de trouver une solution globale !
J’entends encore Marie-Jeanne :
« Je vous avais demandé de permuter dans le sens des aiguilles d’une montre sur ces 6 ateliers. Après 2 permutations désordonnées, nous voilà arrivés à une situation impossible ! C’est malin. »
Marie-Jeanne avait l’habitude de travailler ainsi, avec des permutations cycliques. J’ai moi aussi cru qu’il pouvait y avoir un blocage…. Et des enfants ont refait le même atelier. Puis j’ai pris une feuille et… il y avait une solution !
Ce problème est amusant. Il est facile à résoudre pour les petites valeurs, 3 ou 4 ateliers. Pour 5 groupes, ce n’est déjà pas si simple, pour 6, il faut bien réfléchir.
Mais y a-t-il vraiment un problème qui puisse arriver pour une certaine valeur \(n>6\) du nombre de groupes après un certain nombre \(p\) d’ateliers déjà faits ? Si oui, donnez-moi un exemple ! Sinon, donnez-moi une preuve ! C’est évident ou pas ?
Pour toute valeur de \(n\), s’il ne reste plus qu’un atelier à faire chacun, il n’y a pas de blocage, c’est sûr ! Cela se dit \(p≤n−2\). Quand il en reste deux à faire, il n’y en a pas non plus, c’est aussi assez facile à voir, donc \(p≤n−3\) mais PAS ÉVIDENT…
ÉCRIT PAR
Sylvain Barré
Maître de conférences - Laboratoire de Mathématiques de Bretagne Atlantique -Université de Bretagne-Sud
17h28
Bonjour,
Si je ne me trompe pas, c’est bien vrai (mais pas évident) et c’est une application du théorème des mariages (ou théorème de Hall).
En effet, considérons qu’il y a p tours qui ont été faits.
Pour chaque atelier, il y a encore n-p équipes qui ne l’ont pas fait, et chaque équipe a encore n-p ateliers à faire.
Notons Ai l’ensemble des équipes n’ayant pas fait l’atelier i. Alors les ensembles Ai vérifient la propriété de Hall : pour m quelconques d’entre eux il y a au moins m équipes qui apparaissent.
On peut donc trouver une équipe différente pour chaque atelier en utilisant le théorème de Hall, et faire un (p+1)ème tour.
Ce problème se traduit aussi en terme de carrés latins partiels à remplir, la preuve ci-dessus a été tirée de l’article disponible ici .
Aline
23h50
Oui mais, qu’est qu’on va dire à Marie-Jeanne ? Qu’elle a raison de permuter cycliquement quand même ? Ou on lui dit comment s’en sortir face à des enfants agités, en ne formant que 5 ou 6 groupes ? Ou… pas évident de parler latin !