Pamphile et Salwa sont dans un bateau

Aussi appelée "énigme de Pierre et Serge", "énigme de Patricia et Sylvie", "énigme de Paul et Sophie", "énigme de Pierrot et Sandrine" voire même énigme de "Pamphile et Salwa", l'énigme de Freudenthal, c'est l'énigme qui tchue !
En voici une formulation :

On choisit deux nombres X et Y différents (avec 1<X<Y≤98) tels que X+Y≤100. Pamphile connaît le produit XY et Salwa connaît la somme X+Y. De plus, Pamphile et Salwa, malgré leur nom, dispose d'une intelligence supérieur à la normale. Voici leur discussion :
Pamphile : Je ne connais pas les deux nombres X et Y...
Salwa : Je le savais déjà !
Pamphile : Ah ? Et bien, maintenant, je connais X et Y !
Salwa : Et ben, du coup, moi aussi !

Quels sont les deux nombres X et Y ?

Le temps que vous résolviez ce problème (Avec un papier, un crayon et un ordinateur), le blog Choux Romanesco, Vache qui rit et Intégrales curvilignes vous propose un petit intermède sur l'origine de ce problème, avant la solution du problème.

Ce problème nous vient de Hans Freudenthal, mathématicien qui a occupé pendant 70 ans (de 1946 à 1975) la chaire de mathématiques appliquées à l'Université d'Utrecht (au Pays-Bas). Il écrivait des problèmes dans le journal Nouvelles Archives de mathématiques ( en VO Nieuw Archief voor Wiskunde), et c'est en 1969 que paraît (en hollandais) pour la première fois ce problème à placer dans la catégorie "Je sais que tu ne sais pas, donc je sais".

Maintenant que l'historique est terminé, voici la solution du problème, pas à pas !

1 - Pamphile : Je ne connais pas les deux nombres X et Y...
Pamphile connaît le produit P=XY, mais ne peut pas en déduire X et Y. C'est donc que ce produit P admet au moins deux décompositions P=XY différentes. On peut commencer par chercher quels sont ces nombres P qui admettent au moins deux décompositions différentes P=XY de telles façon que X+Y≤100. On appelle V₁ l'ensemble de ces nombres (Le nombre P que connaît Pamphile est dans cet ensemble)
Dans cet ensemble, on a par exemple 18, car 18=9×2=3×6, avec 9+2≤100 et 3+6≤100.
En menant une recherche minutieuse sur papier, ou à l'aide d'un ordinateur, on trouve :
V₁ = {12, 18, 20, 24, 28, 30, 32, 36, 40, 42, 44, 45, 48, 50, 52, 54, 56, 60, 63, 64, 66, 68, 70, 72, 75, 76, 78, 80, 84, 88, 90, 92, 96, 98, 99, 100, 102, 104, 105, 108, 110, 112, 114, 116, 117, 120, 124, 126, 128, 130, 132, 135, 136, 138, 140, 144, 147, 148, 150, 152, 153, 154, 156, 160, 162, 164, 165, 168, 170, 171, 172, 174, 175, 176, 180, 182, 184, 186, 188, 189, 190, 192, 195, 196, 198, 200, 204, 207, 208, 210, 216, 220, 222, 224, 225, 228, 230, 231, 232, 234, 238, 240, 243, 245, 246, 248, 250, 252, 255, 256, 258, 260, 261, 264, 266, 270, 272, 273, 275, 276, 279, 280, 282, 285, 286, 288, 290, 294, 296, 297, 300, 304, 306, 308, 310, 312, 315, 320, 322, 324, 325, 328, 330, 336, 340, 342, 344, 345, 348, 350, 351, 352, 357, 360, 364, 368, 370, 372, 374, 375, 376, 378, 380, 384, 385, 390, 392, 396, 399, 400, 405, 406, 408, 410, 414, 416, 418, 420, 425, 429, 430, 432, 434, 435, 440, 441, 442, 444, 448, 450, 455, 456, 459, 460, 462, 464, 465, 468, 470, 475, 476, 480, 483, 486, 490, 492, 494, 495, 496, 500, 504, 506, 510, 512, 513, 516, 518, 520, 522, 525, 528, 532, 539, 540, 544, 546, 550, 552, 558, 560, 561, 564, 567, 570, 572, 574, 576, 580, 585, 588, 592, 594, 595, 598, 600, 602, 608, 609, 612, 616, 620, 621, 624, 627, 630, 637, 638, 640, 644, 646, 648, 650, 651, 656, 660, 663, 666, 672, 675, 680, 682, 684, 688, 690, 693, 696, 700, 702, 704, 714, 715, 720, 726, 728, 735, 736, 738, 740, 741, 744, 748, 750, 754, 756, 759, 760, 765, 768, 770, 774, 780, 782, 783, 784, 792, 798, 800, 806, 810, 812, 814, 816, 819, 820, 825, 828, 832, 836, 840, 850, 855, 858, 860, 864, 868, 870, 874, 880, 882, 884, 888, 891, 896, 897, 900, 902, 910, 912, 918, 920, 924, 928, 930, 935, 936, 945, 946, 950, 952, 957, 960, 962, 966, 968, 969, 972, 975, 980, 984, 986, 988, 990, 992, 1000, 1008, 1012, 1014, 1020, 1026, 1032, 1035, 1036, 1040, 1044, 1050, 1053, 1054, 1056, 1064, 1066, 1071, 1078, 1080, 1088, 1092, 1100, 1102, 1104, 1105, 1110, 1116, 1118, 1120, 1122, 1125, 1131, 1134, 1140, 1144, 1148, 1150, 1152, 1155, 1160, 1170, 1173, 1176, 1178, 1184, 1188, 1190, 1196, 1197, 1200, 1204, 1215, 1216, 1218, 1224, 1230, 1232, 1240, 1242, 1248, 1254, 1258, 1260, 1275, 1276, 1280, 1288, 1292, 1296, 1300, 1302, 1311, 1312, 1320, 1323, 1326, 1330, 1332, 1334, 1344, 1350, 1360, 1364, 1365, 1368, 1377, 1380, 1386, 1392, 1394, 1400, 1404, 1406, 1408, 1425, 1426, 1428, 1430, 1440, 1449, 1450, 1452, 1456, 1458, 1470, 1472, 1476, 1480, 1482, 1485, 1488, 1496, 1500, 1508, 1512, 1518, 1520, 1530, 1536, 1539, 1540, 1550, 1554, 1560, 1564, 1566, 1568, 1575, 1584, 1596, 1600, 1610, 1612, 1617, 1620, 1624, 1628, 1632, 1638, 1650, 1656, 1664, 1672, 1674, 1680, 1700, 1702, 1710, 1716, 1725, 1728, 1736, 1740, 1748, 1750, 1755, 1760, 1764, 1768, 1776, 1782, 1792, 1794, 1798, 1800, 1820, 1824, 1836, 1848, 1850, 1856, 1860, 1872, 1890, 1904, 1914, 1920, 1924, 1932, 1938, 1944, 1950, 1960, 1972, 1980, 1984, 2016, 2030, 2040, 2046, 2052, 2070, 2080, 2100, 2108, 2112, 2142, 2145, 2160, 2176, 2184, 2200, 2205, 2240, 2244, 2268, 2280, 2340, 2352, 2400}

2 - Salwa : Je le savais déjà !
Salwa connait la somme S=X+Y. Si elle savait déjà que Pamphile ne pouvait trouver X et Y par rapport à son produit, c'est parce que peu importe la décomposition S=X+Y qu'elle prend, elle a XY dans l'ensemble V₁. (En effet, s'il existe une décomposition S=X+Y telle que XY n'est pas dans V₁, elle n'aurait pas pu dire qu'elle le savait déjà)
On appelle V₂ l'ensemble de tous les S possible (dont toutes les décompositions S=X+Y sont telles que XY est dans V₁).
Dans cet ensemble V₂, on a par exemple S=11, car
11=9+2, et 9×2=18 ∈ V₁
  =8+3, et 8×3=24 ∈ V₁
  =7+4, et 7×4=28 ∈ V₁
  =6+5, et 6×5=30 ∈ V₁

En procédant une nouvelle fois à une recherche minutieuse, en étudiant toutes les sommes possibles entre 4 et 100, pour trouver V₂. Il y a des cas rapides à exclure, comme les nombres pairs : puisque tous les nombres pairs sont une somme de deux nombres premiers (c'est la conjecture de Goldbach, vraie au moins pour les petits nombres), la décomposition S=p+q avec p et q premiers amènera au produit pq, qui ne peut pas être dans V₁ (car n'admettant qu'une seule décomposition en produit). On trouve alors :
V₂ = {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}

3 - Pamphile : Ah ? Et bien, maintenant, je connais X et Y !
Pamphile a lui aussi pu déduire cet ensemble V₂ des sommes probables (il a raisonné comme nous). Il connait également le produit P=XY, et prétend qu'il peut déduire X et Y de ce que Salwa vient de dire. En fait, il déduit d'abord sa somme S, puis déduit X et Y (il est facile de trouver deux nombres quand on connaît leur produit et leur somme).

On construit (et Pamphile le fait aussi) d'abord les listes K(S) des produits XY issu des décompositions S=X+Y des éléments de V₂ :
K(11) = {18, 24, 28, 30}
K(17) = {30, 42, 52, 60, 66, 70, 72}
K(23) = {42, 60, 76, 90, 102, 112, 120, 126, 130, 132}
K(27) = {50, 72, 92, 110, 126, 140, 152, 162, 170, 176, 180, 182}
K(29) = {54, 78, 100, 120, 138, 154, 168, 180, 190, 198, 204, 208, 210}
K(35) = {66, 96, 124, 150, 174, 196, 216, 234, 250, 264, 276, 286, 294, 300, 304, 306}
K(37) = {70, 102, 132, 160, 186, 210, 232, 252, 270, 286, 300, 312, 322, 330, 336, 340, 342}
K(41) = {78, 114, 148, 180, 210, 238, 264, 288, 310, 330, 348, 364, 378, 390, 400, 408, 414, 418, 420}
K(47) = {90, 132, 172, 210, 246, 280, 312, 342, 370, 396, 420, 442, 462, 480, 496, 510, 522, 532, 540, 546, 550, 552}
K(53) = {102, 150, 196, 240, 282, 322, 360, 396, 430, 462, 492, 520, 546, 570, 592, 612, 630, 646, 660, 672, 682, 690, 696, 700, 702}

Si Pamphile peut déduire la somme de X et Y (en sachant que cette somme est dans V2) en connaissant le produit XY, c'est que le produit XY n'apparaît pas dans deux K(S) différents. En apparaissant dans un seul K(S), Pamphile connaît la valeur de S, et trouve alors X et Y. Si P apparaissait dans plusieurs K(S), il ne pourrait en déduire S.
Par exemple, si son nombre P était 18, il en déduirait automatiquement que S=11, et donc que (X,Y)=(2,9).
Si son nombre P est 30, il ne pourrait pas conclure, car il hésiterait entre S=11 et S=17.

4 - Salwa : Et ben, du coup, moi aussi !
Salwa se fait la même réflexion, mais elle arrive à en déduire la valeur de P, car elle connaît S.
Salwa a calculé également K(S), et a pu en déduire P, ce qui signifie que de tous les éléments de K(S), le seul qui n'apparaît pas dans un autre K(S') (pour S' dans l'ensemble V₁) est le produit P connu de Pamphile.

On peut donc calculer les listes K'(S) qui correspondent aux listes K(S) auquel on a retiré tous les doubles.
(On a par exemple K'(11)={18, 24, 28}, car 30 apparait dans K(17)). Les listes sont les suivantes :
K'(11) = {18, 24, 28}
K'(17) = {52}
K'(23) = {76, 112, 130}
K'(27) = {50, 92, 110, 140, 152, 162, 170, 176, 182}
K'(29) = {54, 100, 138, 154, 168, 190, 198, 204, 208}
K'(35) = {96, 124, 174, 216, 234, 250, 276, 294, 304, 306}
K'(37) = {160, 186, 232, 252, 270, 336, 340}
K'(41) = {114, 148, 238, 288, 310, 348, 364, 378, 390, 400, 408, 414, 418}
K'(47) = {172, 246, 280, 370, 442, 480, 496, 510, 522, 532, 540, 550, 552}
K'(53) = {240, 282, 360, 430, 492, 520, 570, 592, 612, 630, 646, 660, 672, 682, 690, 696, 700, 702}

Parmi tous les cas possibles, il n'y a que le cas où S=17 dans lequel Salwa peut conclure. Salwa conclut, c'est donc que S=17 !

On a donc S=17, P=52
On en déduit alors X=4 et Y=13 !
CQFD !

Et si on simplifie ? Et si on complique ?
Tout ça vous semble trop difficile ? Trop facile ? On peut fabriquer autant d'énoncé qu'il y a d'entier plus grand que 4, en remplaçant le nombre 100 dans l'énoncé par un autre nombre M.

Par exemple, Martin Gardner a proposé, pour simplifier le problème, de remplacer 100 par 20... Grosse erreur, puisque le problème n'a alors plus aucune solution (En fait, le dialogue entre Pamphile et Salwa)!

Par contre, en prenant n'importe quel nombre M supérieur à 65, le problème aura au moins la solution (4,13). Ca sera d'ailleurs la seule solution pour M entre 65 et 1684. Au delà, le problème peut avoir plusieurs solutions...
Par contre, on ne sait toujours pas si le nombre de solutions tend vers l'infini quand M tend vers l'infini ! Avis aux casseurs de conjectures !

---

Sources :
L'incroyable problème de Freudenthal - Pour la science n°356, juin 2007

Comments

[Dr. Goulu]

J'aime bien la version "grand public" de ce problème qui s'énonce ainsi :

Un facteur fait la causette à un prof de maths : “Au fait, quels âges ont vos filles ?”

- “Le produit de leurs âges fait 36, et leur somme est le numéro de la maison d’en face.” répond le papa taquin.

- Le facteur réfléchit, puis dit “vous n’oubliez pas quelque chose ?“

- Ah si, dit le prof, vous avez raison j’ai oublié de préciser que l’ainée est blonde.

- C’est bon, dit le facteur, je sais leurs âges alors!

[rom1]

Très bel article, il y a plusieurs moi de celà, j'avais essayé de participer à ce topic sur Prise2Tete :
http://www.prise2tete.fr/forum/viewtopic.php?id=301
Deux solutions très détaillées sont proposées, qui rejoignent ce qui est marqué ci dessus.

Je ne savais pas que ce problème avait un nom, j'aurais appris quelque chose !