Solution dans le premier cas (valeur maximum connue, égale à $100$).

Pierre: Non, je ne peux pas trouver ces deux nombres.

Ceci signifie que le produit $P$ peut se décomposer d'au moins deux manières différentes en produit de deux nombres compris entre $2$ et $100$. Par exemple, on pourrait avoir $P = 75$, car ce produit se décompose en $3\times25$ ou $5\times15$, mais on ne peut pas avoir $P = 77$ car alors la décomposition serait unique: $7\times11$.

Voici une liste de valeurs que nous pouvons d'ores et déjà éliminer:

• toute valeur inférieure à $4$ ou supérieure à $10000$
• le produit de deux nombres premiers (par exemple $77 = 7\times11$)
• le cube d'un nombre premier (par exemple $125 = 5\times25$)
• le double du carré d'un premier plus grand que 10 (par exemple, $242 = 2\times11\times11 = 11\times22$: la décomposition en $2\times121$ est impossible)
• un multiple strict d'un nombre premier plus grand que $50$ (par exemple $318 = 6\times53$)
• le produit du carré d'un premier plus grand que $10$ par un nombre premier (par exemple $242 = 2\times11\times11 = 11\times22$ ; la décomposition en $2\times121$ est impossible)
• et bien d'autres...

Sophie: Je le savais.

Ceci signifie que la somme $S$ ne peut pas s'écrire comme somme de deux nombres dont le produit aurait été éliminé dans l'étape précédente.

Par exemple, la somme $11$ convient car tous les produits possibles sont non uniques:

En revanche, la somme $13$ ne convient pas car: $13 = 2+11$ ; $2\times11 = 22$ (pas d'autre décomposition)

Par conséquent, on peut commencer par éliminer toutes les sommes de deux nombres premiers. Vous pouvez vérifier que cela élimine déjà toutes les sommes paires (ceci a été conjecturé par Goldbach dans le cas général, et vérifié par ordinateur sur beaucoup plus de nombres que ce dont on a besoin pour résoudre ce problème). Pour ce qui est des sommes impaires, on élimine celles qui sont égales à un nombre premier plus 2: $5=3+2$, $7=5+2$, $9=7+2=$, $13=11+2$, etc.

Après ce premier débroussaillage, il nous reste les sommes qui sont égales à un nombre composé impair plus $2$: $11$ ($3\times3 + 2$), $17$ ($3\times5 + 2$), $23$ ($3\times7 + 2$), $27$ ($5\times5 + 2$), $29$, $35$, $37$, $41$, $47$, $51$, $53$, $57$, $59$, etc.

Nous pouvons aussi supprimer toutes les sommes S à partir de $57$, puisque si $57 \leq S \leq 153$, on peut écrire $S = 53 + n$, avec $4 \leq n \leq 100$, si $155 \leq S \leq 197$, on peut écrire $S = 97 + n$, avec $58 \leq n \leq 100$, si $S = 199$, on peut écrire $S = 100 + 99$. Dans chacun de ces trois cas, le produit $P$ correspondant (soit $53n$, soit $97n$, soit $100 \times 99$) a une décomposition unique.

On peut enfin supprimer la somme $S = 51 = 17 + 34$, car le produit $P = 17 \times 34$ n'a pas d'autre décomposition.

Voici donc la liste exhaustive des sommes possibles à cette étape du raisonnement, avec pour chaque somme la liste des produits possibles.

Pierre: Dans ce cas, je connais les deux nombres.

Pour que Pierre puisse faire cette affirmation, il faut que le produit $P$ se trouve une fois et une seule dans la liste que nous venons d'écrire. Cela élimine donc les produits $P = 30$ ($S = 11$ ou $17$), $P = 42$ ($S = 17$ ou $23$), etc. Il reste:

Sophie: Alors moi aussi.

Pour que Sophie puisse dire cela, il faut qu'il ne reste plus qu'un seul produit correspondant à la somme qu'elle connaît. Ceci n'est réalisé que si la somme est $17$, auquel cas le produit est $52$. Les nombres de départ sont donc $4$ et $13$.