L’incroyable problème de Freudenthal

Nous sommes souvent conduits à raisonner sur l’information dont disposent ou ne disposent pas les gens avec qui nous interagissons. Nous nous disons par exemple : puisque X dit ceci, c’est qu’il ne sait pas que je l’ai vu hier à son insu, mais Y qui m’observe ouvertement sait que je fais ce raisonnement et donc Y sait que je sais que X ne sait pas que je l’ai vu hier, et moi je sais que Y sait cela, etc.

Raisonner sur les informations dont chacun dispose et sur les raisonnements faits avec ces informations peut être délicat. Bien sûr, les mathématiciens et les logiciens y ont vu la source de problèmes, certains d’une étonnante subtilité. Un casse-tête ancien de ce type, celui des cocus de Bagdad, est exemplaire : un raisonnement nous permet de tirer d’une information banale une conclusion d’une précision inattendue.

La vengeance simultanée des cocus de Bagdad

Mort de Sardanapale par Eugène Delacroix (Musée du Louvre, Paris).
Photo RMN / © Hervé Lewandowski.

Cette énigme classique est un exemple de raisonnement sur la connaissance insoupçonnée. Le calife de Bagdad, ici représenté par le Sardanapale de Delacroix, est informé de ce qui se passe dans sa ville. Un jour, il fait un discours auquel tous les hommes de la ville assistent et il dit : « Il y a au moins une femme adultère dans la ville. »

À Bagdad, les hommes sont de parfaits logiciens. Chaque homme sait quels sont les cocus, sauf bien sûr quand il s’agit de lui. La règle cruelle veut qu’un mari qui apprend qu’il est trompé tue sa femme devant le calife dans la nuit qui suit ; cette loi est appliquée avec rigueur et personne ne dénonce une femme adultère à son époux. Les cocus ne peuvent apprendre leur infortune que par le raisonnement.

Pendant les 49 nuits qui suivent le discours du calife rien ne se passe. La cinquantième nuit, 50 femmes sont assassinées et le lendemain le calife proclame qu’il n’y a plus aucune femme adultère. Que s’est-il passé ?

À la suite d’une magnifique énigme inventée par Hans Freudenthal où sont exploités ces raisonnements sur l’information et les déductions résultant des échanges, des exercices mathématiques redoutables ont été mis au point et ont fini par engendrer des questions dont certaines restent non résolues. Nous allons présenter ce domaine où l’inventivité des amateurs atteint des sommets de finesse.

Pour comprendre le principe de ces énigmes, voici trois énoncés dont la résolution ne prend que quelques minutes.

1. Sommes des diviseurs

On choisit un nombre entier N entre 1 et 12. On indique à Jacques la somme de tous les diviseurs de N. Jacques dit alors « Je ne sais pas quel est le nombre N ». Trouver le reste de la division de N par 5.

Rappelons que, parmi les diviseurs d’un nombre, il y a toujours 1 et lui-même. Par exemple, les diviseurs de 8 sont 1, 2, 4 et 8 et la somme des diviseurs de 8 est 15.

Précisons un point : dans les énigmes de cette catégorie, nous supposons toujours que les personnages (et donc Jacques) sont de parfaits logiciens. Si un raisonnement est possible pour répondre aux questions qu’on leur pose, ils le font, et quand ils répondent « Je ne sais pas », cela signifie qu’aucun raisonnement correct ne donne la solution à la question posée.

2. Plus grand premier

Là encore, on choisit un nombre entier N entre 1 et 12. On indique à Jacques la somme de tous les diviseurs de N. On indique à Jules le plus grand diviseur premier de N. Jacques et Jules réfléchissent un moment et disent en même temps : « Je ne peux pas savoir quel est N. » Quel est N ?

3. Réponses décalées

On choisit un nombre entier N entre 1 et 20. On indique à Jacques la somme de tous les diviseurs de N. On indique à Jules le plus grand diviseur premier de N. Jacques dit « Je ne sais pas quel est N ».
Dans un second temps, donc après avoir pris en compte la réponse de Jacques, Jules dit « Je ne sais pas moi non plus ». Combien N a-t-il de diviseurs ?

Ces trois premiers problèmes montrent comment l’étude détaillée des cas possibles et des étapes successives d’un échange d’informations apparemment anodin dévoile petit à petit une information d’une précision parfois inattendue.

Hans Freudenthal dans les années 1930.
Photo DR.

Ils indiquent aussi comment il faut s’y prendre pour traiter la magnifique énigme inventée par Hans Freudenthal (1905-1990) en 1969. Celle-ci est d’un niveau de difficulté supérieure. Je vous invite à y réfléchir en vous aidant éventuellement d’une feuille de papier et, pourquoi pas, d’un ordinateur.

Le problème de Freudenthal

On choisit deux entiers X et Y, avec 1 < X <Y et X + Y ≤ 100. On indique à Patricia le produit P de X et Y. On indique à Sylvie la somme S de X et Y. Le dialogue est alors le suivant :
1. Patricia : « Je ne sais pas quels sont les nombres X et Y. »
2. Sylvie : « Je savais que vous ne connaissiez pas X et Y. »
3. Patricia : « Eh bien alors, maintenant, je connais X et Y. »
4. Sylvie : « Eh bien, moi aussi je les connais maintenant. »
À vous de trouver X et Y.

Après avoir soutenu une thèse sous la direction de Heinz Hopf en 1930, Freudenthal occupa la chaire de mathématiques appliquées de l’Université d’Utrecht de 1946 à 1975 (jusqu’à 70 ans…). Ses contributions de chercheur portent sur la topologie, la géométrie et la théorie des groupes de Lie. Un Institut de mathématiques porte aujourd’hui son nom à Utrecht. Il s’intéressa aussi à la didactique des mathématiques et fut en particulier le rédacteur de la rubrique des problèmes du journal Nieuw Archief voor Wiskunde (Nouvelles Archives de Mathématiques). C’est dans cette rubrique que parut, pour la première fois et en néerlandais, le célèbre problème qui nous occupe aujourd’hui.

Attention aux modifications de l’énoncé

Un algorithme assez simple à programmer permet de faire raisonner l’ordinateur à votre place. Il permet aussi d’étudier ce qui se passe quand on fait varier les données du problème de Freudenthal.

Notons en particulier qu’il faut être très prudent dans la construction d’énigmes de ce type, car les inégalités fixées au départ 1 < X < Yet X + Y ≤ 100 sont utilisées dans le cours du raisonnement et le changement d’une seule peut tout bouleverser. Une mésaventure désagréable est ainsi arrivée à Martin Gardner qui, en voulant simplifier le problème initial, avait repris l’énoncé en précisant que les inconnues X et Y vérifiaient : 2 ≤ X ≤ Y ≤ 20. Cela correspond bien à une zone plus petite (l’énigme peut donc être abordée à la main plus facilement) et dans la zone retenue par Martin Gardner il y a bien les deux nombres X = 4 et Y = 13 de la solution. Pourtant, l’énigme de Martin Gardner n’a pas de solution, car le traitement des listes, quand on prend en compte les deux derniers échanges entre Patricia et Sylvie, est maintenant différent et ne donne plus rien.

Si on remplace 100, dans le problème de Freudenthal, par un nombre M différent, on obtient une suite infinie de problèmes qui peuvent avoir 0, 1 ou plusieurs solutions selon le nombre M retenu. La solution X = 4, Y = 13 du problème initial reste valide pour tous les M à partir de 65 et donc reste une solution quand M tend vers l’infini : on dit que c’est une solution stable.

Ce n’est pas le cas de la solution X = 67, Y = 82 qui n’est une solution que si M appartient à l’intervalle des entiers entre M = 4721 et M = 5485 : on dit que c’est une solution fantôme.

La solution X = 4, Y = 13 est l’unique solution pour toutes les valeurs de M entre 65 et 1684. Vous pouvez donc modifier l’énoncé initial de Freudenthal en précisant 1 < X < Y et X + Y ≤ 1684, il n’aura toujours qu’une seule solution (et le problème sera devenu plus difficile bien sûr).

Une question envisagée par John Kiltinen et Peter Young est celle du nombre de solutions au problème lorsque M tend vers l’infini. On conjecture qu’on trouvera une infinité de couples solutions et même qu’on trouvera une infinité de solutions stables. On n’a pour l’instant réussi à démontrer aucune de ces deux conjectures.

Voici les dix premières solutions stables avec le nombre M à partir duquel elles apparaissent : [M = 65, X = 4, Y = 13], [M = 1685, X = 4, Y = 61], [M = 9413, X = 32, Y = 131], [M 1970, X = 16, Y = 73], [M = 2522, X = 16, Y = 111], [M = 6245, X = 32, Y = 311], [M = 6245, X = 64, Y = 73], [M = 6893, X = 4, Y = 229], [M = 72365, X = 8, Y = 239], [M 237173, X = 4, Y = 181]. À la vue de ce début, on pourrait croire que le premier élément X d’une solution stable est toujours une puissance de 2. C’est faux : plus loin, on trouve la solution stable X = 201 et Y = 556, qui est active à partir de M = 966293.

Au lieu de faire varier la quantité M qui majore la somme X + Y, on peut dans les données du départ faire varier le 1 des inégalités 1 < X < Y en le remplaçant par m (ce qui donne m < X < Y). L’étude de ces problèmes est assez étonnante, car on constate qu’il n’y a aucune solution dès que m ≥ 3 (et cela quel que soit M) ; on aimerait bien démontrer que c’est vrai, mais on n’y arrive pas. On conjecture donc que : pour m ≥ 3, le problème de Freudenthal défini à partir de m < X < Y n’a jamais de solution.

De nombreuses variantes ont été imaginées à partir du problème initial. Pour en voir quelques-unes, passez à la suite.

Toujours plus fort

Voici une variante en sept étapes qui est l’œuvre de Clive Tooth.
On choisit deux nombres X et Y avec 2 ≤ X ≤ Y et X + Y ≤ 5000. On indique leur somme S à Sylvie et leur produit P à Patricia.

On assiste alors au dialogue suivant.
1. Patricia : « Je ne sais pas quels sont les nombres X et Y. »
2. Sylvie : « Je savais déjà que vous ne connaissiez pas X et Y. »
3. Patricia répond : « Ah bon, eh bien alors maintenant je connais X et Y. »
4. Sylvie dit alors : « Eh bien, moi aussi je les connais maintenant. »

On aimerait bien pouvoir en déduire X et Y,mais comme X et Y peuvent atteindre 5000, cela n’est pas possible pour celui qui assiste à l’échange. Heureusement un troisième personnage, Julien, qui a assisté à l’échange, intervient.

5. Julien : « Pour l’instant, je ne peux pas connaître X et Y. »
6. Sylvie lui répond : « Pourtant, si je t’indique la valeur de X tu pourras connaître Y. »
7. Julien s’exclame alors : « Maintenant je connais X et Y. »
Et vous ?

Une journée de réflexion !

Il est temps de vous présenter le problème de cette catégorie que je trouve le plus étonnant. Mis au point tout récemment par Axel Born, Kor Hurkens et Gerhard Woeginger, trois universitaires qui ont pris la peine d’étudier soigneusement cette catégorie d’énigmes mathématiques, il est à la fois simple et difficile : 23 affirmations simultanées consistant en d’élémentaires « Je ne sais pas » proférés par quatre personnages – supposés excellents logiciens – les conduisent en même temps que vous à trouver une solution unique à un problème à cinq inconnues. Bien sûr, là encore l’ordinateur vous aidera. Résoudre à la main cette énigme extrême est envisageable… si vous avez une journée devant vous et si vous êtes certain de ne pas vous tromper dans les petits calculs qu’elle nécessite.

Voici donc la variante du problème de Freudenthal due à Axel Born, Kor Hurkens et Gerhard Woeginger. C’est la plus difficile et la plus belle de toutes les énigmes de ce type. Nous l’intitulerons : Une journée de réflexion !

On choisit cinq nombres a b c d e vérifiant :
1 ≤ a < b < c < d < e ≤ 10
On indique à Patricia leur produit P = abcde,
à Sylvie, leur somme S = a + b + c + d + e,
à Christian, la somme de leurs carrés C = a² + b² + c² + d² +e²,
et à Vincent, la valeur V = (a + b + c) (d + e).

1. Une heure après qu’on leur a posé le problème, les quatre personnages qu’on interroge simultanément répondent tous ensemble : « Je ne connais pas les nombres a b c d e. »
2. Une heure après, les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
3. Une heure après, les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
4. Une heure après, les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
Etc.
23. Une heure après (soit 23 heures après la formulation de l’énoncé !), les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
Mais après cette 23^e réponse, les visages des quatre personnages s’éclairent et tous s’exclament : « C’est bon maintenant, je connais a b c d e. »

Quels sont les cinq nombres a b c d e ?

Ces exercices ne sont pas aussi futiles qu’ils le paraissent : Hans Freudenthal s’est intéressé à la communication avec des extraterrestres dont il était persuadé de l’existence (il a même écrit un livre à ce sujet en 1960). Cette communication imposait l’étude de signaux non ambiguë. Mais cela est une autre histoire…

Une première version de ce document est parue dans la rubrique « Logique et calcul » de la revue Pour la Science n° 356 de juin 2007.