L’énigme de Paul et Sam

Sur le site Mathix, Arnaud Durand présentait en 2015 une énigme mathématique dans laquelle deux protagonistes, Paul et Sam, essaient de deviner deux entiers entre 2 et 100 dont ils ne connaissent que le produit pour l’un et la somme pour l’autre (d’où le choix des prénoms dont l’initiale est celle de l’information dont ils disposent). Je retranscris le dialogue dans le respect de la licence Creative Commons BY-NC-SA.

Paul — Non, je ne peux pas trouver ces deux nombres.

Sam — Je le savais.

Paul — Dans ce cas, je connais les deux nombres.

Sam — Alors moi aussi.

À partir de ces seules informations, pouvez-vous déterminer les deux entiers ?

Résolution

L’énoncé ne précise pas clairement que les deux entiers sont distincts, donc on étudiera successivement les deux cas. On commence par l’hypothèse que les des deux entiers peuvent être éventuellement égaux

Les deux entiers étant choisis entre 2 et 100, le produit est nécessairement un entier entre 4 et 10 000, tandis que la somme est comprise entre 4 et 200.

Détermination à partir du produit

Il y a plusieurs situations où la connaissance du produit P permet de trouver les deux nombres, notamment :

• lorsque P est un produit de deux facteurs premiers ;
• lorsque P est le cube d’un nombre premier ;
• lorsque P est le produit d’un nombre premier supérieur à 10 et de son double ;
• lorsque P admet un facteur premier supérieur à 50, et plus généralement, lorsque le produit du plus petit facteur premier et du plus grand facteur premier de P est (strictement) supérieur à 100 ;
• lorsque P n’admet qu’un seul facteur compris entre √P et 100, en particulier s’il s’écrit 100d mais ne possède aucun facteur strictement compris entre d et 100…

Détermination des sommes possibles

Le fait que Sam sache que Paul ne se trouve dans aucune situation de détermination implique que la somme S ne puisse s’écrire de l’une des façons suivantes :

1. la somme de deux nombres premiers ;
2. la somme d’un nombre premier et de son carré ;
3. le triple d’un nombre premier supérieur à 10 ;
4. la somme d’un nombre premier entre 50 et 100 avec un nombre entier entre 2 et 100 ;
5. une somme de la forme 100+d si le produit 100d n’admet aucun facteur entre d+1 et 99.

Le quatrième critère élimine toutes les valeurs comprises entre 53+2 et 97+100. Le cinquième critère permet d’éliminer 100+98, 100+99 et 100+100. La vérification de la conjecture de Goldbach jusque 100 nous assure que S ne peut pas non plus s’écrire comme un nombre pair inférieur à 100.

Il reste à éliminer dans les nombres impairs restants ceux qui suivent un premier impair, ainsi que le triple de nombre premier supérieur à 10 restant (51 = 3 × 17), ce qui nous laisse donc un ensemble de valeurs possibles E = {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}.

Réciproquement, toute décomposition de l’une de ces valeurs en somme de deux entiers donnera deux nombres de parité différente et tous deux entre 2 et 50 (à l’exception de 53 = 2 + 51 que l’on traitera ensuite), et on note 2a le terme pair et b le terme impair.

• Si a = 1, alors b ne peut pas être premier donc il se factorise sous la forme b = uv avec des facteurs stricts et 2a × b = 2u × v.
• Si 1 < a ≠ b, alors on obtient deux factorisations différentes 2a × b = 2b × a.
• Si a = b > 10 alors il s’agit d’un nombre impair entre 3 et 23, et par hypothèse il n’est pas premier donc il est divisible par 3. Il s’écrit donc 3k avec k ∈ {3, 5, 7}. Alors on obtient deux factorisations différentes 2a × b = 2k × 9k.
• Si a = b ≤ 10 alors il s’agit d’un nombre impair entre 3 et 9, donc on obtient deux factorisations différentes 2a × b = 2 × a².

Il ne reste plus qu’à traiter la décomposition 53 = 2 + 51 mais 2 × 51 = 6 × 17 donc là encore on trouve deux factorisations différentes.

Détermination des ambiguïtés

Par exemple, si S = 11, Paul pourrait avoir le produit 2 × 9 = 18 = 3 × 6, et l’affirmation de Sam lui permettrait d’éliminer la deuxième décomposition. Mais Paul pourrait avoir aussi le produit 3 × 8 = 24 = 2 × 12 = 4 × 6, et là encore l’affirmation de Sam lui permettrait de conclure. Comme Sam arrive à en déduire lui aussi les deux nombres, c’est que S ≠ 11.

On constate que si S = 17, Paul ne peut déduire de l’affirmation de Sam les valeurs des deux nombres que si le produit vaut 52, et dans ce cas les deux nombres sont 4 et 13.

Les autres lignes du tableau présentent des ambiguïtés, que l’on peut formaliser en disant qu’un couple (a, b) d’entiers (entre 2 et 100) présente une ambiguïté (c, d) (d’entiers entre 2 et 100) si c + d ∈ E ∖ {a + b} et ab = cd.

Si cet énoncé nous permet de savoir quels sont les deux nombres à deviner, c’est qu’il n’y a pas d’autre valeur de S qui donne lieu à au dialogue ci-dessus, soit parce que plusieurs décomposition en somme de deux entiers ne présentent aucune ambiguïté, soit parce toutes les décompositions présentent au moins une ambiguïté. Cependant, je n’ai pas trouvé de méthode simple et rapide de vérifier qu’il n’y a qu’une solution à cette énigme. Je suis donc passé par un programme en Python.

Hypothèse des deux entiers distincts

Le raisonnement est essentiellement le même, mais le calcul de l’ensemble E est un peu plus délicat. D’abord, la somme est comprise entre 5 et 199. Un nouveau cas de détermination apparait à partir du produit : la quatrième puissance d’un nombre premier n’admet qu’une décomposition en facteurs distincts. Ensuite, le deuxième critère n’élimine plus la somme 97+97, on utilise alors le cinquième critère pour éliminer 94+100. Enfin, on élimine les nombres pairs qui sont sommes de deux nombres premiers distincts, ce qui nous laisse encore possible la somme 6. Mais ce dernier ne se décompose que d’une manière en somme de deux entiers distincts dans ⟦2, 100⟧ (6 = 2 + 4), et le produit est un cube.

Finalement, l’ensemble E est le même que dans l’autre hypothèse, et avec des sommes impaires les décompositions se feront toujours sur des termes de parité différentes, ce qui exclut la survenue d’un doublon.

Programmation de la résolution

Le nombre de couples d’entiers entre 2 et 100 étant assez réduit (autour de 5000 à ordre près des termes), on engendre tous ces couples, que l’on rassemble par produit. Puis on liste les sommes de facteurs pour les produits n’admettant qu’une factorisation dans ce contexte, les autres sommes étant considérées alors comme admissibles.

On répertorie ensuite par leur somme les paires d’entiers dont le produit admet une seule factorisation admissible. Une seule somme ne se décompose que d’une seule manière ainsi.

n = 100
factorisations = {}
for i in range(2, n):
    for j in range(i, n):
        P = i*j
        if P in factorisations:
            factorisations[P].append((i,j))
        else:
            factorisations[P]=[(i,j)]
# première affirmation de Paul
evidences = {}
for P in factorisations:
    if len(factorisations[P])==1:
        evidences[factorisations[P][0][0]+factorisations[P][0][1]]=1
# première réponse de Sam
decompositions={}
for P in factorisations:
    if len(factorisations[P])>1:
        l=[(i,j) for (i,j) in factorisations[P] if i+j not in evidences]
        #détermination par Paul
        if len(l)==1:
            i,j=l[0]
            S=i+j
            if S in decompositions:
                decompositions[S].append((i,j))
            else:
                decompositions[S] = [(i,j)]
# détermination par Sam
print([decompositions[S][0] for S in decompositions if len(decompositions[S])==1])

Le remplacement de l’affectation n=100 par d’autres valeurs montre qu’il a une même unique solution à partir de n=63. Aucune solution n’apparait en deçà. Je n’ai pas testé les valeurs de n supérieures à 200.

Le programme donne les mêmes résultats en imposant que les deux entiers soient distincts avec l’instruction de boucle for j in range(i+1, n):

Complexité

Paul peut assez rapidement tester la divisibilité de son produit par 2, 3, 5 et 7. Si ce n’est pas le cas, il a un produit de deux nombres premiers. Dans le cas contraire, il peut avoir à factoriser un entier avec au moins un facteur premier inférieur à 50, puis évaluer l’existence de plusieurs factorisations différentes avec des entiers inférieurs à 100.

Sam peut assez rapidement examiner les critères d’existence d’une double factorisation pour un produit de termes qui décomposent sa somme. Le raisonnement fait intervenir des critères multiples, mais peu de calculs.

Pour que Paul puisse en déduire les nombres à deviner, il faut qu’il ait trouvé des critères comme Sam et élimine toutes les factorisations dont la somme des facteurs ne satisfasse pas les critères. Là encore, la complexité repose sur le raisonnement mais peu sur les calculs.

Sam doit enfin examiner toutes les décompositions possibles de sa somme et toutes les factorisations des produits associés. Les calculs étant faits ci-dessus, il y a une vingtaine de cas à traiter, ce qui est humainement réalisable. Bien entendu, avec une somme autour de 50, les calculs auraient été nettement plus longs.

En l’état, la détermination des nombres à deviner à partir du seul dialogue entre Paul et Sam repose sur le calcul d’environ 5000 produits. On aurait pu réduire ce nombre en n’examinant que les presque 150 décompositions de sommes admissibles, chacune pouvant fournir de deux à une demi-douzaine de factorisations, soit plusieurs centaines de calculs.