Freudenthal's problem

Imaginez deux nombres cachés. Prosper reçoit seulement leur produit, Sophie seulement leur somme. Aucun ne voit le nombre donné à l’autre. Pourtant, lorsqu’un élève avoue son ignorance, il révèle que plusieurs couples restent possibles pour lui. L’autre peut alors supprimer les couples incompatibles avec cet aveu.

Le dialogue devient ainsi une suite de tamis. À chaque réplique, chacun raisonne aussi sur ce que l’autre pouvait savoir auparavant. C’est cette connaissance de la connaissance qui fait du problème une énigme de logique épistémique.

Le problème de Freudenthal est une énigme de logique épistémique publiée en 1969 par Hans Freudenthal. Un professeur choisit deux entiers, notés x et y, tels que 1 < x < y et x + y ≤ 100. Prosper connaît uniquement leur produit x × y. Sophie connaît uniquement leur somme x + y. Les bornes et la manière dont l’information est distribuée sont connues de tous.

Une paire est possible pour un participant lorsqu’elle produit la valeur qu’il a reçue et respecte les contraintes communes. La première déclaration de Prosper élimine les produits qui n’admettent qu’une seule paire possible. Sophie affirme ensuite que, pour toutes les paires donnant sa somme, Prosper devait hésiter dès le départ. Prosper réexamine alors les factorisations de son produit parmi les seules sommes compatibles avec cette certitude. Sa nouvelle connaissance élimine encore des paires, puis Sophie applique le même raisonnement à sa somme.

La solution est x = 4 et y = 13 : leur somme vaut 17 et leur produit vaut 52. Le raisonnement porte sur des ensembles de possibilités successifs, pas seulement sur deux équations numériques. Il suppose aussi que les participants raisonnent correctement, disent vrai et connaissent les règles ainsi que les facultés de raisonnement de l’autre.

Le couple conducteur est (4, 13). Les données communes sont 1 < x < y et x + y ≤ 100. Sophie reçoit 17. Prosper reçoit 52. L’univers initial contient 2 352 couples admissibles.

1. Après « je ne sais pas », on conserve les 1 747 couples dont le produit possède plusieurs factorisations admissibles.
2. Sophie savait cet échec : sa somme doit appartenir à {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}. Il reste 145 couples.
3. Pour le produit 52, les possibilités initiales sont (2, 26) et (4, 13). La somme 28 du premier couple n’appartient pas à la liste précédente. Prosper déduit donc (4, 13). Au total, 86 couples rendent ainsi son produit unique à cette étape.
4. Parmi ces 86 couples, un seul a pour somme 17. Sophie déduit à son tour (4, 13).

Le contrôle est direct : 4 + 13 = 17 et 4 × 13 = 52. En rejouant les quatre filtres sur tous les couples admissibles, (4, 13) est l’unique couple qui survit à la dernière déclaration.

Sur papier, on peut dresser les couples admissibles par somme et par produit. Cette méthode convient pour contrôler quelques valeurs ; une énumération informatique devient préférable lorsque la borne 100 rend les listes longues.

Dans un programme, chaque réplique devient un filtre. On regroupe d’abord les couples par produit et par somme, puis on ne conserve que ceux compatibles avec ce que le locuteur affirme savoir ou ignorer. Le nombre de candidats doit diminuer après chaque information utile.

Pour vérifier une solution annoncée, il ne suffit pas de retrouver sa somme et son produit. Il faut rejouer le dialogue dans l’ordre et contrôler que chaque déclaration est vraie au moment précis où elle est prononcée.

Un système somme-produit. Connaître simultanément une somme et un produit permet de chercher directement deux nombres. Ici, personne ne possède les deux valeurs : si l’on utilise 17 et 52 dès le départ, on résout une autre question.

Une simple élimination arithmétique. Factoriser 52 donne bien (2, 26) et (4, 13), mais ne suffit pas initialement à Prosper. Le critère distinctif est l’usage des déclarations sur le savoir de l’autre, qui transforme l’ensemble des cas possibles.

Changer les bornes change l’énigme. Les filtres reposent sur 1 < x < y et x + y ≤ 100. Autoriser x = y, inclure 1 ou choisir une autre borne modifie les factorisations admissibles ; il faut alors reconstruire tous les ensembles de possibilités.

Filtrer trop tôt avec une information future. Le symptôme est une déduction de Prosper avant la certitude annoncée par Sophie. Chaque phrase doit être évaluée sur l’ensemble disponible à cet instant, puis seulement servir à construire l’ensemble suivant.

Oublier la connaissance commune. Si les bornes, la sincérité ou la capacité de raisonnement ne sont pas supposées connues de tous, « je savais que vous ne saviez pas » ne justifie plus le même filtre. Il faut expliciter ces hypothèses avant de conclure.

arithmétique — Revoir les propriétés des entiers, des sommes, des produits et des factorisations mobilisées pour construire les couples possibles.