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

Voir la réponse

À 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.

Voir la réponse

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 ?

Voir la réponse

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 ?

Voir la réponse

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.

Pour voir la solution du problème de Freudenthal, allez à la page suivante.