Solution des énigmes de E31 à E35

E31: Cette énigme est une simple question de logique. Le voyant et le borgne peuvent voir les autres boules se trouvant sur la tête de ses camarades. Si l’un d’entre eux avait vu la boule noire au-dessus de la tête d’un de ses camarades, il aurait immédiatement déduit qu’il avait une boule blanche puisqu’il n’y a qu’une seule boule noire. L’aveugle n’entendant aucune manifestation, il en déduira qu’il n’a pas de boule noire. Il a donc une boule blanche.

E32: Commençons par voir ce qui se passerait à la fin du jeu : si les 3 premiers votes sont refusés, il ne reste que les deux plus jeunes pirates. À ce moment là, quel que soit le partage proposé par le plus âgé des deux, le plus jeune vote contre, le partage est alors refusé et le plus jeune obtient la totalité du magot.

Donc, lorsqu’il y a trois pirates en lice pour le magot, le plus âgé des trois peut aisément faire accepter le partage suivant : 11 lingots pour lui, 1 pour le deuxième et aucun pour le plus jeune. Le deuxième votera pour ce partage puisque sinon il n’obtiendrait rien. Le partage est donc accepté à deux voix contre une (celle du plus jeune qui n’obtient rien).

Lorsqu’il y a quatre pirates, la situation est la suivante : si le partage proposé par le plus âgé est refusé, alors le partage effectif sera le précédent, à savoir 11 lingots pour le deuxième, 1 pour le troisième et aucun pour le dernier.

Le plus âgé des quatre doit se trouver deux alliés, c’est-à-dire faire une proposition qui attribue plus de lingot que la précédente à deux autres pirates. Pour en obtenir lui-même le plus possible, il va donc proposer 1 lingot au dernier pirate et 2 à l’avant-dernier (pour s’allier le deuxième, il faudrait lui proposer 12 lingots, ce qui n’est clairement pas optimal pour lui). Lui-même en obtient donc 9.

Nous pouvons désormais conclure : si le partage proposé par le plus âgé des cinq pirates est refusé, le partage effectif sera : 9 lingots pour le deuxième, 2 pour le quatième et 1 pour le dernier. Les alliés les moins coûteux pour le doyen des cinq pirates sont donc le troisième et le cinquième, à qui il proposera respectivement 1 et 2 lingots. Ajouté à sa propre voix, cela fait trois voix contre deux et ce partage sera entériné. C’est par ailleurs le partage le plus profitable possible pour le doyen.

La solution de l’énigme est donc que le doyen peut obtenir 9 lingots.

E33: Sur celle là je l’admets Remue Méninges a été un peu dur…

Soient n, m et l les entiers tels que notre joueur de casino a posé des tas de n², m² et l² jetons au départ. On appelle T le nombre total de jetons, qui vérifie :

T = 3 n² + 3 m² + 3 l²

Le problème est donc de savoir si l’on peut écrire T comme somme de quatre carrés d’entier non nuls. Nous allons voir qu’un grand nombre de cas se résolvent sans trop de problème.

Si tout d’abord n, m et l sont deux à deux distincts, il suffit de remarquer que:

T = 3 n² + 3 m² + 3 l² = (m-n)² + (l-n)² + (l-m)² + (n+m+l)²

Ensuite, si deux des trois nombres sont égaux, par exemple n=m, et le troisième distinct, alors on a :

T = 6 n² + 3 l² = (2 n)² + (n+l)² + (n-l)² + l²

Enfin, reste le cas n=m=l. Si n est pair, on peut écrire n = 2a, et alors :

T= 9 (2a)² = 36 a² = (25 + 9 + 1 + 1) a² = (5a)² + (3a)² + a² + a²

Si par contre n est impair, c’est plus compliqué. Si n=1, alors on a T=9, et l’on vérifie que 9 ne se décompose pas comme une somme de quatres carrés d’entiers non nuls. Nous allons voir que c’est la seule exception. Si n est différent de 1, quitte à factoriser n sous la forme d’un produit p q, avec p premier, on peut supposer n premier. En effet, si l’on décompose en somme de quatre carrés non nuls la quantité :

9 p² = a² + b² + c² + d²

alors on a immédiatement :

T = 9 p² q² = a² q² + b² q² + c² q² + d² q² = (aq)² + (bq)² + (cq)² + (dq)²

On suppose donc désormais que p est un nombre premier, et l’on veut décomposer le nombre T = 9 p² en une somme de quatre carrés non nuls. Nous allons pour cela utiliser le théorème des 4 carrés : tout entier s’écrit comme somme de quatre carrés, dont certains peuvent être nuls (il s’agit ici d’un théorème qui n’a rien d’immédiat. Voir par exemple le Cours d’arithmétique de Jean-Pierre Serre).

Soit donc p un nombre premier. On sait que

p = a² + b² + c² + d²

avec a, b, c et d des entiers naturels. On suppose, quitte à réordonner ces entiers que l’on a aussi :

a>b>c>d (supérieur ou égal)

Nous allons maintenant distinguer les cas, selon le nombre de termes non nuls dans cette somme.

Il ne peut y en avoir un seul : le cas p=a² est absurde puisque par hypothèse p est premier.
S’il n’y en a que deux : c’est le cas où c = d = 0, alors on a immédiatement :

T=9p²=(3a²)²+(3b²)²+(3ab)²+(3ab)²

S’il n’y en a que trois : c’est le cas d = 0 et a, b, c non nuls. p est alors la norme au carré des quaternions a + b i + c j, et a + b i + c k (entre pas mal d’autres). p² est donc la norme au carré de leur produit, soit le quaternion :

(a+bi+cj) (a+bi+ck)=a²-b²+(2ab+c²)i+(ac-bc)j+(ac-bc)k

Si a > b, alors les quatre termes a² – b², (2 a b + c²), (a c – b c) et (a c – b c) sont non nuls, et l’on obtient la solution :

p² = (a² – b²)² + (2 a b + c²)² + (a c – b c)² + (a c – b c)²

soit:

9 p² = (3 a² – 3 b²)² + (6 a b + 3 c²)² + (3 a c – 3 b c)² + (3 a c – 3 b c)²

Si maintenant a = b, alors b > c. En effet, le cas a = b = c entraîne que p = 3 a², soit p divisible par 3. C’est impossible sachant que p est premier, sauf si p = 3, et l’on traite aisément ce cas à la main: 9×3²=81=36+25+16+4

On considère cette fois les quaternions b i + c j + a k et a + b i + c j (par exemple), dont le produit est :

(- b² – c²) + (a b – a c) i + (a c + a b) j + a² k

Et cette fois-ci, les quatres composantes sont non nulles, on obtient donc :

9 p² = (- 3 b² – 3 c²)² + (3 a b – 3 a c)² + (3 a c + 3 a b)² + (3 a²)²

Passons maintenant au dernier cas, c’est-à-dire a, b, c et d non nuls. Toujours selon le même principe, p² est alors la norme au carré du quaternion :

(a + b i + c j + d k)² = (a² – b² – c² – d²) + 2 a b i + 2 a c j + 2 a d k

Lorsque a = b, on a en particulier a² – b² – c² – d² = – c² – d² < 0, et les quatre composantes sont alors non nulles. On obtient:

9 p² = (3 a² – 3 b² – 3 c² – 3 d²)² + (6 a b)² + (6 a c)² + (6 a d)²

Sinon, on a a > b, et l’on écrit alors p² comme la norme au carré du quaternion :

(d+bi+cj+ak)(a+bi+cj+dk)=(-b²-c²)+(ab+db+cd-ac)i+(ac+dc+ab-db)j+(a²+d²)k

Et l’on constate que cette fois-ci, toutes les composantes sont non nulles, d’où:

9 p² = (- 3 b² – 3 c²)² + (3 a b + 3 d b + 3 c d – 3 a c)² + (3 a c + 3 d c + 3 a b – 3 d b)² + (3 a² + 3 d²)²

Sauf dans le cas où le nombre de jetons est 9, l’ami a une solution pour remporter la mise! E34: Nous allons voir que l’on dispose en fait de tous les renseignements nécessaires pour décrire la situation, à permutation près entre les couples (et à l’intérieur de chaque couple). Tout d’abord, le maître de maison à interrogé exactement 2n+1 personnes (n couples, plus sa femme), qui lui ont tous donné une réponse différente. Or un personne donnée ne peut serrer au maximum que 2n mains (celle des personnes qui ne sont pas son conjoint…). Les 2n+1 réponses sont donc les entiers de 0 à 2n.On représente les 2n+2 personnes comme les sommets d’un graphe dont les arrêtes sont les poignées demain échangées. Une des personnes, que nous appellerons A, a serré exactement 2n, soit toutes celles des autres couples. La personne qui n’a serré aucune main est alors nécessairement son conjoint : toutes autre personne a serré la main de A. Par élimination, le conjoint de A est la seule personne possible qui n’en a serré aucune.

On peut alors conclure presque immédiatement : parmis les 2n personnes restantes, toutes ont déjà serré exactement une main. La personne qui a serré 2n-1 mains a donc serré toutes les mains possibles en dehors de la personne qui en a serré zéro. Par le même raisonnement, c’est son conjoint qui en a serré une seule, toutes les autres personnes ayant serré au moins deux mains.

De proche en proche, on a ainsi la propriété suivante : le conjoint de la personne ayant serré 2n-i mains en a serré exactement i (où, si l’on préfère, le total des mains serrées par un couple fait exactement 2n). De proche en proche, on va ainsi épuiser tous les entiers de 0 à 2n, jusqu’à arriver au dernier couple, dont les deux conjoints ont donc serré n mains chacun.

Comme seulement une personne a déclaré avoir serré n mains, c’est que le maître de maison a lui-même serré n mains, tout comme sa femme…

E35: Essayons de voir ce qui se passe pour un nombre restreint de récipients.

Pour un seul récipient, aucun problème : le récipient contient alors un litre, donc en partant de l’endroit où il se trouve, on a de quoi faire le tour du circuit.
S’il y a deux récipients, c’est un peu plus compliqué. Partir du récipient le plus rempli ne marche pas forcément : si le premier récipient contient 2/3 de litre, mais qu’il faut faire 3/4 de tour avant d’arriver au second, alors on tombera forcément en panne sèche.
En fait, il faut alors partir de celui des deux récipients dont la quantité d’essence permet d’atteindre l’autre. L’un des deux au moins remplit forcément cette condition, car si l’on note q(X) la quantité d’essence d’un réservoir X donné et d(X) la distance (exprimée en fraction de tour de circuit) jusqu’au réservoir suivant, la condition demandée est qu’il existe un réservoir X tel que q(X) soit supérieur ou égal à d(X). Et, si l’on appelle A et B nos deux réservoirs, on a q(A) + q(B) = 1 et d(A) + d(B) = 1 (*), on ne peut donc avoir q(A) < d(A) et simultannément q(B) < d(B). Une fois arrivé au second réservoir, aucun problème : on a alors récupéré toute l’essence, donc on est en mesure de terminer le tour.
Pour trois récipients, c’est un peu plus compliqué : si l’on appelle A, B et C nos trois réservoirs, il ne suffit pas de trouver un réservoir X tel que q(X) soit supérieur ou égal à d(X). Cette condition suffit en effet à atteindre le deuxième réservoir, mais il se peut alors que l’on tombe en panne sèche entre le deuxième et le troisième.
En réalité, il suffit d’avoir q(X) supérieur ou égal à d(X) et q(X) + q(Y) supérieur ou égal à d(X) + d(Y), où Y est le réservoir suivant. Mais comme on a toujours la contrainte q(A) + q(B) + q(C) = 1 et d(A) + d(B) + d(C) = 1 (**), la deuxième partie de cette condition revient à dire que q(Z) est inférieur ou égal à d(Z), où Z est le troisième réservoir !
Trouver un point de départ qui convient est alors on ne peut plus simple. Par (**), on sait que l’un des trois réservoirs au moins vérifie la condition “q(X) est inférieur ou égal à d(X)”. Quitte à changer les noms des réservoirs, on peut supposer que le réservoir A vérifie cette propriété.
On compare alors q(B) et d(B). Si q(B) est supérieur ou égal à d(B), alors B convient comme point de départ. Sinon, toujours grâce à (**), q(C) est forcément supérieur à d(C), et alors C convient comme point de départ.

On pourrait continuer avec quatre récipients, etc. Mais visiblement, la situation se complique à chaque fois un peu plus. Nous allons maintenant présenter deux solutions au problème. La première est inspirée par les considérations précédentes : il s’agit de démontrer l’existence d’une position de départ adéquate par récurrence sur le nombre de récipients.

Le résultat est vrai lorsqu’il n’y a qu’un récipient, comme nous l’avons déjà vu.
Supposons donc le résultat vrai pour n récipients, et soit une situation dans laquelle le litre d’essence est divisé en n+1 réserves.
Nous allons voir que l’on peut se ramener à une situation avec seulement n récipients. Par le même raisonnement que précédemment (cas n=2 ou 3), il existe un réservoir X tel que q(X) soit supérieur ou égal à d(X). Nous allons voir que le problème est le même si l’on ajoute à un tel réservoir, à l’endroit où il est, le contenu du réservoir suivant.
En effet, soit A un tel réservoir et B le réservoir suivant. Si l’on arrive au point A, on arrive nécessairement jusqu’à B puisqu’il y a en A une quantité d’essence suffisante pour ce faire. Et, en arrivant en B, on a dépensé la quantité d’essence d(A) depuis le point A. Si q désigne la quantité d’essence dont on dispose en arrivant en A, on a en B la quantité

q + q(A) – d(A)

quantité à laquelle on doit ajouter la quantité q(B) que l’on récupère en B. C’est-à-dire que l’on a en repartant de B la quantité

q + q(A) – d(A) + q(B)

On trouve la même chose s’il y a une quantité q(A) + q(B) au point A, et rien au point B. Comme de toutes façon il est impossible de partir d’un point strictement compris entre A et B (on partirait sinon avec le réservoir vide !), on peut regrouper nos deux réservoirs au point A et ça ne change pas le problème.

Comme par hypothèse de récurrence il y a une position de départ qui convient pour n récipients, il y en a aussi une pour notre situation à n+1 récipients.

On conclue par récurrence qu’il existe toujours une position de départ qui convient.