Le problème E632 de Diophante.fr

A l'Auberge du Chapeau, 24 convives sont assis autour d'une grande table circulaire. Chacun d'eux porte un chapeau, noir ou blanc, dont il ignore la couleur mais peut voir la couleur des chapeaux portés par les autres commensaux
L'aubergiste leur demande de déclarer, tous en même temps, à haute voix, la couleur de leur propre chapeau.
Si au moins la moitié d'entre eux font des déclarations correctes, le repas est offert à toute la tablée.
Sinon, ce sera pour tout le monde le repas au prix fort.
Q1 Démontrer que les convives peuvent s'assurer la gratuité du repas.
Q2 Le scénario est le même que précédemment avec 24 convives, 4 couleurs de chapeau: noir ou blanc ou bleu ou rouge et l'aubergiste offre le repas si au moins six convives font des déclarations correctes.
La gratuité est-elle assurée ?


Dans l'animation ci-dessous,
- choisir la question, c'est- à-dire le nombre de couleurs : deux, trois, quatre ou six ;
- effectuer le TIRAGE au sort des couleurs des chapeaux ;
- réfléchir à une stratégie ;
- contrôler et essayer de comprendre la stratégie utilisée par l'ordinateur. Elle fait gagner un repas à tous les coups.

CLIQUER

SOLUTION

Pour la question n°2, les quatre couleurs des chapeaux sont numérotés 0,1,2,3.
Les vingt-quatre convives sont répartis en quatre groupes de six personnes chacun (autant de groupes que de couleurs)
Chaque membre m(i,j) du groupe n°i (avec i = 0,1,2,3 et j=1,2,..,6) calcule la somme s(i,j) modulo 4 des numéros des vingt-trois chapeaux qu’il voit.
Les membres du groupe n°i font l’hypothèse que la somme totale des vingt-quatre chapeaux est égale à i modulo 4.
Le membre m(i,j) désigne alors la couleur k telle que s(i,j) + k = i modulo 4.
Sur les quatre groupes il y en a un et un seul dont les six déclarations sont correctes.

Pour la question n°1, la stratégie est identique avec un modulo 2. et des couleurs simplement numérotées de 0 à 1.
On fera simplement deux groupes de 12 personnes.
De la même façon, sur les deux groupes il y en a un et un seul dont les douze déclarations sont correctes.

Cette stratégie fonctionne aussi avec 8 couleurs et 12 couleurs.

C'est celle qui est utilisée ci-dessus dans l'animation.
Les chapeaux sont numérotés à partir de l’horizontale à droite : angle 0°, dans le sens des aiguilles d’une montre de 0 à 24.