C’est évident ou pas ?

Le 21 octobre 2013  - Ecrit par  Sylvain Barré Voir les commentaires (2)

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\leq n-2$. Quand il en reste deux à faire, il n’y en a pas non plus, c’est aussi assez facile à voir, donc $p\leq n-3$ mais PAS ÉVIDENT...

Partager cet article

Pour citer cet article :

Sylvain Barré — «C’est évident ou pas ?» — Images des Mathématiques, CNRS, 2013

Commentaire sur l'article

  • C’est évident ou pas ?

    le 21 octobre 2013 à 17:28, par Aline Parreau

    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

    Répondre à ce message
    • C’est évident ou pas ?

      le 21 octobre 2013 à 23:50, par Sylvain Barré

      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 !

      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é ?

Suivre IDM