Casse-tête de la somme et du produit

Le casse-tête de la somme et du produit, aussi appelé paradoxe impossible car il semble manquer d'information pour être résolu, est un casse-tête logique. Il a été publié pour la première fois en 1969 par Hans Freudenthal, et l'appellation paradoxe impossible est due à Martin Gardner. Ce paradoxe a une solution, mais qui passe par un méta-raisonnement (c'est-à-dire basé sur des métaconnaissances). Il existe de nombreux casse-têtes similaires.

L'énoncé On suppose que X et Y sont deux nombres entiers supérieurs à 1, et . Leur somme ne dépasse pas 100. S et P sont deux mathématiciens (et par conséquent des logiciens infaillibles) ; S connaît la somme et P connaît le produit . S et P connaissent tous deux l’ensemble des informations contenues dans ce paragraphe.

Dans les échanges qui suivent, les agents sont supposés toujours dire la vérité :

S dit « P ne peut deviner ni X ni Y ». P dit : « c'est vrai, mais maintenant, je connais X et Y. » S dit : « Moi aussi, maintenant, je connais X et Y. »

Quels sont les entiers X et Y ?

Explication La solution apparait plus facilement une fois posés les concepts et les perspectives. Trois agents sont impliqués dans ce problème : S, P et O. L'agent S connaît la somme , P connaît le produit , et l’observateur O (c'est-à-dire vous, lecteur) ne possède que l’énoncé initial du problème, mais observe les deux autres. Les trois agents disposent donc presque des mêmes informations, mais les interprètent différemment. Le casse-tête porte donc sur l'analyse de ces informations.

Appelons « 2-décomposition » la décomposition d'un entier A en deux entiers B et C tels que . Il n'est pas nécessaire de faire appel à des connaissances avancées telles que la conjecture de Goldbach (qui n'est qu'une conjecture, non démontrée à ce jour), ou le fait que le produit d'une telle 2-décomposition soit unique (c'est-à-dire qu'il n'existe pas d'autres paires de nombres dont le produit soit identique). Cependant, il est clair que P connaîtrait immédiatement X et Y si leur produit était un nombre semi-premier, comme ce sera illustré par la suite.

Les étapes suivantes permetttent de trouver la solution :

S (Simone), P (Patrick) et O (Odette) dressent des tableaux de tous les produits des termes des 2-décompositions des sommes comprises entre 5 et 100 ( et impliquent de commencer à 5). Par exemple, 11 peut être décomposé en , , et . Les produits correspondants sont 18, 24, 28 et 30. Les joueurs cochent la case correspondante dans leur tableau (Tableau 1). À la fin, certains nombres n'ont aucune coche, d'autres en ont une, et d'autres encore en ont plusieurs. Simone examine maintenant sa somme et toutes ses 2-décompositions. Elle constate que les produits de ces décompositions ne sont pas uniques, c'est-à-dire qu'il existe une autre factorisation qui est une décomposition en 2 d'une autre somme possible. Elle le voit dans le Tableau 1, où tous ses produits sont cochés plus d'une fois. Elle comprend que, de ce fait, Patrick ne pourra pas déterminer de manière unique les facteurs X et Y en regardant simplement le produit (cela aurait nécessité qu'au moins un des produits candidats n'ait qu'une seule coche). Elle s'exclame alors : « P ne peut pas connaître X et Y ! » En entendant cela, Patrick et Odette comprennent qu'aucun des produits associés à la somme de Simone n'est unique. En examinant les sommes possibles une par une, Simone, Patrick et Odette peuvent maintenant, chacun de leur côté, dresser la liste de toutes les sommes admissibles (tableau 2). Le tableau contient les sommes dont toutes les 2-décompositions ont des produits non uniques, c'est-à-dire qui sont cochés plus d'une fois dans le Tableau 1. Simone, Patrick et Odette ont créé le Tableau 2 des sommes candidates (Simone connaît bien sûr déjà sa somme mais a besoin de retracer le raisonnement de Patrick). Compte tenu des nouvelles informations du Tableau 2, Patrick examine à nouveau son produit. Les sommes de tous les dédoublements possibles de son produit, à une exception près, ont disparu du Tableau 2. Seule la somme des deux nombres cachés X et Y, dont il connaît le produit , reste présente. À partir de cette somme et de ce produit, il peut facilement déduire les nombres individuels et annonce donc à Simone : « Maintenant, je connais X et Y. » Patrick a terminé et quitte le jeu. Simone et Odette recalculent le Tableau 1, en ne comptant cette fois que les produits des 2-décompositions des sommes figurant dans le Tableau 2, au lieu de tous les nombres de 5 à 100 comme dans le Tableau 1 original. Ce tableau mis à jour est appelé Tableau 1B. Simone examine tous les produits des 2-décompositions de sa somme et constate qu'un seul d'entre eux apparaît une seule fois dans le Tableau 1B. Il s'agit donc du produit de Patrick, et elle peut déduire les deux nombres de leur somme et de leur produit aussi facilement que Patrick. Elle annonce alors à Odette (Patrick est déjà parti) : « Maintenant, je connais aussi X et Y. » Simone a terminé et quitte la partie ; seule Odette reste. À partir des informations de l'étape 4, Odette examine toutes les sommes du tableau 2 afin d'en trouver une dont une seule 2-décomposition n'apparaît qu'une seule fois dans le Tableau 1B. La somme recherchée ne peut apparaitre qu'une seule fois, sinon Simone n'aurait pas pu déterminer X et Y avec certitude. Finalement, Odette trouve la somme recherchée, qui se trouve être la seule à posséder ces propriétés, ce qui permet de résoudre le problème initial avec une solution unique. La tâche d'Odette est ainsi terminée.

Solution La solution est et , P sachant initialement que le produit est 52 et S sachant que la somme est 17.

Initialement, P ne connaît pas la solution, car

S sait que P ignore la solution, car toutes les 2-décompositions de 17, compte tenu des contraintes, donnent plusieurs produits (cochés plusieurs fois dans le Tableau 1). Cependant, P sait, après ce qu'a dit S, que la somme est parmi celles dont toutes les 2-décompositions ont des produits apparaissant au moins deux fois. P peut donc éliminer , car la somme est alors égale à 28, qui est la somme des deux nombres premiers 11 et 17, dont le produit 187 n'apparaitra qu'une fois dans le tableau 1 (ce cas illustre la conjecture de Goldbach).

P sait maintenant que les nombres sont 4 et 13 et dit à S qu'il connait la solution. S en déduit que parmi les 2-décompositions de la somme (à savoir , , , , , , ), une seule est associée à un seul produit, permettant à P de déduire la réponse : . S connait donc maintenant la solution et le dit.

L'observateur O peut alors déduire l’unique solution possible puisque S a pu la déterminer : et , qui est tel que S n'a qu'un seul produit n'apparaissant qu'une fois parmi les produits des 2-décompositions des sommes sélectionnées dans le tableau 2.

Par exemple, si l’on avait dit à S que 97 () et à P que 2352 (), P aurait pu déduire l’unique solution possible, mais pas S, car 44 et 53 resteraient une alternative logique.

Autres solutions Le problème peut être généralisé. La borne est choisie délibérément. Si cette limite est modifiée, le nombre de solutions peut varier. Pour , il n'y a pas de solution. Cela peut paraître contre-intuitif au premier abord, puisque la solution , se situe dans cette borne. Cependant, en excluant les produits dont la somme des facteurs est comprise entre ces bornes, on élimine les multiples façons de factoriser les solutions inexistantes, ce qui conduit à l'absence totale de solution. Par exemple, si l'on exclut , , et , il ne reste qu'un seul produit de 124, à savoir , dont la somme est 35. Cette valeur de 35 est ensuite éliminée lorsque S déclare que P ne peut pas connaître les facteurs du produit, ce qui n'aurait pas été le cas si la somme de 64 avait été autorisée.

En revanche, lorsque la limite est ou plus, une seconde solution apparaît : , . Dès lors, le problème n'admet plus de solution unique. De même, si ou plus, une troisième solution apparaît (, ). Ces trois solutions contiennent toutes un nombre premier. La première solution ne contenant aucun nombre premier est la quatrième, qui apparaît pour ou plus, avec les valeurs et .

Si la condition est remplacée par , il existe une solution unique pour les seuils pour , au-delà desquels il existe plusieurs solutions. Pour t inférieur ou égal à 124, il n'y a pas de solution. L'augmentation du seuil de solution n'est pas surprenante. Intuitivement, l'espace du problème devient plus « clairsemé » lorsque le nombre premier 2 n'est plus disponible comme facteur de X, réduisant ainsi le nombre de produits possibles pour une somme A donnée. Lorsqu'il existe de nombreuses solutions, c'est-à-dire pour des valeurs de t plus élevées, certaines solutions coïncident avec celles du problème initial avec , par exemple et .

Si la condition pour un certain seuil t est remplacée par , le problème se transforme. Il devient plus facile à résoudre et nécessite moins de calculs. Une valeur raisonnable pour u pourrait être , le t correspondant étant le plus grand produit de deux facteurs dont la somme est t, soit . Le problème admet alors une solution unique dans les intervalles , , et , et aucune solution en dessous de ce seuil. Les résultats de cette formulation alternative diffèrent de ceux de la formulation originale, tant en nombre de solutions qu'en contenu.

Voir aussi Puzzle des enfants de trois ans Anniversaire de Cheryl

Références

Catégorie:Casse-tête Catégorie:Casse-tête mathématique Catégorie:Pages avec des traductions non relues