Exercice 4 — Menteurs mais pas tous — Olympiades 2014 Toulouse

Sujet

Des personnes font une ronde circulaire en se tenant par la main.
Chacun déclare: « Mon voisin de droite et mon voisin de gauche sont des menteurs. »
Chacun peut être menteur (il dit toujours un mensonge) ou bien vérace (il dit toujours la vérité).

S'ils sont trois à faire la ronde, expliquer pourquoi il y a deux menteurs.
Et s'ils sont quatre, combien peut-il y avoir de menteurs?
Ils sont six à faire la ronde.
a) Est-il possible qu'il y ait trois véraces? Plus de trois véraces?
b) Quel est le nombre maximal de menteurs dans la ronde?
Ils sont maintenant 2014 à faire la ronde en se tenant par la main.
a) Quel est le nombre minimal de menteurs dans la ronde ?
b) Quel est le nombre maximal de menteurs dans la ronde ?
On considère maintenant une ronde de personnes où il y a exactement 2014 menteurs.
a) Quel est le nombre minimal de personnes de cette ronde ?
b) Quel est le nombre maximal de personnes de cette ronde ?

Partie A :

Ronde de trois

Trois menteurs ne se peuvent : un menteur entouré de deux menteurs ne peut être menteur.
Il y a donc un vérace, un autre vérace ne se peut : un vérace est nécessairement entouré de deux véraces.

2. Ronde de quatre

Quatre menteurs ne se peuvent...
Il y a un vérace; il est entouré par deux menteurs. Le quatrième ne peut qu'être vérace. Donc deux menteurs et deux véraces composent la ronde de quatre.

3. Ronde de six

a) La disposition où alternent menteurs et véraces satisfait aux conditions. Elle comporte trois menteurs.
Cette disposition est nécessaire. Il ne peut pas y avoir d'autre vérace.
b) Un menteur étant donné, il est entouré par un menteur et un vérace ou bien deux véraces. S'agissant d'augmenter le nombre de menteurs, on opte pour menteur et vérace. On complète semblablement les trois autres places. La ronde peut comporter jusqu'à quatre menteurs (et deux véraces).

4. Ronde de 2014 personnes

Pas de menteurs ne se peut.