Ce problème m'a été posé initialement par mon père. J'ai appris récemment que ce problème s'appelle le problème de Freudenthal, et je vous invite à aller voir l'article de Jean-Paul Delahaye sur ce sujet.
La somme et le produit (***)
Alice tient le discours suivant : J’ai choisi deux nombres entiers X et Y tel que 2 ≤ X ≤ Y ≤ 100. À toi Pauline, je vais te donner le produit des deux nombres P = X Y, et à toi Sophie, je vais te donner la somme des nombres S = X+Y.
Voici la conversation qu’ont Pauline et Sophie.
Pauline : "Je ne peux pas déduire les deux nombres." Sophie : "Je le savais !" Pauline : "Dans ce cas, je connais les deux nombres." Sophie : "Alors moi aussi."
Quels sont les deux nombres choisis par Alice ?
Si vous voulez chercher par vous-mêmes la solution de ce problème, ne lisez pas la suite du poste tout de suite. Vous pouvez vérifier votre réponse ici.
Les nombres sont X = 4 et Y = 13.
Je pense qu'on peut donner plusieurs interprétations pour mathématiser ce genre de problèmes, et je vais en donner une, qui est la mienne, et qui est peut-être discutable.
On note dans la suite N = 100. On va supposer que la conversation qu'ont Pauline et Sophie contient seulement des phrases de type
1. Je ne peux pas deviner les nombres.
2. Je le savais.
3. Je peux deviner les nombres.
Une conversation est une suite de phrases (P1, S2, ... ), où P1 signifie que Pauline dit la phrase 1,S2 signifie que Sophie dit ensuite la phrase 2, etc.
Par exemple, la conversation du problème est (P1, S2, P3, S3).
Nous allons diviser la conversation en étape (une étape par phrase). On introduit l'ensemble \(C_k\) qui contient tous les couples \((X,Y)\) possibles après \(k\) étapes (i.e. l'ensemble des couples qu'aurait pu choisir Alice, et donnant le même dialogue jusqu'à l'étape \(k\)). On introduit de plus, pour \(4 \le S \le 2N\) (resp. \(4 \le P \le N^2\)) l'ensemble \(S_k(S)\) (resp. \(P_k(P)\)) contenant tous les couples \((X,Y) \in C_k\) tel que \(X+Y = S\) (resp. \(X\times Y = P\)). Autrement dit,
$$
S_k(S) = \left\{ (X,Y) \in C_k, \ X+Y = S \right\}, \quad P_k(P) = \left\{ (X,Y) \in C_k, \ X\times Y = P \right\}.
$$
Au début, avant la première phrase, Alice a pu choisir n’importe quel couple \((X,Y)\) avec \(2 \le X \le Y \le N\). On a donc
$$
C_0 = \left\{ (X,Y) \in \mathbb{N}^2, \ 2 \le X \le Y \le N \right\}.
$$
Nous allons construire les ensembles \(C_k\) par récurrence en suivant la conversation. Supposons qu’on a déjà construit \(C_0, \ldots, C_k\), et regardons ce qui se passe à l’étape \(k+1\). On suppose pour commencer qu’à cette étape, c’est Pauline qui parle, et qu’elle dise : je ne peux pas deviner les nombres. Cela signifie que le produit \(P\) qu’Alice lui a donné a au moins deux décompositions possibles, de type \(P = X_1\times Y_1 = X_2 \times Y_2\), avec \((X_1, Y_1) \in C_k\) et \((X_2, Y_2) \in C_k\). On a donc
$$
C_{k+1} = \left\{ (X, Y) \in C_k, \ \left| P_k(X \times Y) \right| \ge 2 \right\}.
$$
Un raisonnement similaire permet de traiter le cas où c'est Sophie qui dit : je ne peux pas deviner les nombres.
Supposons maintenant que ce soit Sophie qui parle à l’étape \(k+1\), et qu’elle dise : je le savais. Cela signifie que Sophie connait une somme \(S\) telle que, pour tout couple \((X,Y) \in C_k\) satisfaisant \(X+Y = S\), on avait déjà \((X,Y) \in C_{k-1}\). Autrement dit, Sophie n’a pas gagné d’informations entre l’étape \(k-1\) et l’étape \(k\). On en déduit
$$
C_{k+1} = \left\{ (X,Y) \in C_k, \ S_k(X+Y) = S_{k-1}(X+Y) \right\}.
$$
De nouveau, on peut faire le même raisonnement dans le cas où c’est Pauline qui dit : je le savais.
Enfin, supposons qu’à l’étape \(k+1\), Pauline dise : je peux deviner les nombres. Cela signifie qu’à cette étape, le produit qu’Alice lui a donné ne contient plus qu’une seule décomposition possible. On a donc
$$
C_{k+1} = \left\{ (X,Y) \in C_k, \ \left| P_k (X \times Y) \right| = 1 \right\},
$$
et un même raisonnement permet de traiter le cas où c'est Sophie qui dit : je peux deviner les nombres.
On dira que la conversation est valide si, à la fin de la conversation, on a \(\left| C_M \right| = 1\), où \(M\) est le nombre d'étapes. Notez que pour une conversation générale, ce n'est pas parce que Pauline et/ou Sophie connaissent les nombres que nous les connaissons aussi (par exemple, les choix \((2,2)\) ou \((2,3)\) donnent la même conversation \(\left\{ P3, S3\right\}\)). Ici, la conversation est dite valide si un spectateur extérieur peut aussi trouver les nombres !
On peut alors écrire un programme informatique qui permet de vérifier si une conversation donnée est valide, et donne la solution dans ce cas. Avec ce programme, on peut vérifier que la conversation dans le problème de Freudenthal est valide, et que la solution est \((4, 13)\).
On peut s'amuser à chercher d'autres conversations valides avec ce programme. J'ai par exemple trouvé cette autre conversation.
Problème de Freudenthal (bis)
Alice tient le discours suivant : J’ai choisi deux nombres entiers X et Y tel que 2 ≤ X ≤ Y ≤ 100. À toi Pauline, je vais te donner le produit des deux nombres P = X Y, et à toi Sophie, je vais te donner la somme des nombres S = X+Y.
Voici la conversation qu’ont Pauline et Sophie.
Pauline : "Je ne peux pas deviner les deux nombres." Sophie : "Moi non plus." Pauline : "Je le savais." Sophie : "Je savais que tu savais." Pauline : "Dans ce cas, je connais les deux nombres."
Quels sont les deux nombres choisis par Alice ?
Je vous laisse trouver la solution. Si vous ne la trouvez pas, voici un code qui permet de résoudre le problème. N'hésitez pas à jouer avec, et à m'envoyer d'autres conversations que vous trouvez.
