L’incroyable problème de Freudenthal
Nous sommes souvent conduits à raisonner sur l’information dont disposent ou ne disposent pas les gens avec qui nous interagissons. Nous nous disons par exemple : puisque X dit ceci, c’est qu’il ne sait pas que je l’ai vu hier à son insu, mais Y qui m’observe ouvertement sait que je fais ce raisonnement et donc Y sait que je sais que X ne sait pas que je l’ai vu hier, et moi je sais que Y sait cela, etc.
Raisonner sur les informations dont chacun dispose et sur les raisonnements faits avec ces informations peut être délicat. Bien sûr, les mathématiciens et les logiciens y ont vu la source de problèmes, certains d’une étonnante subtilité. Un casse-tête ancien de ce type, celui des cocus de Bagdad, est exemplaire : un raisonnement nous permet de tirer d’une information banale une conclusion d’une précision inattendue.
La vengeance simultanée des cocus de Bagdad
Mort de Sardanapale par Eugène Delacroix (Musée du Louvre, Paris).
Photo RMN / © Hervé Lewandowski.
Cette énigme classique est un exemple de raisonnement sur la connaissance insoupçonnée. Le calife de Bagdad, ici représenté par le Sardanapale de Delacroix, est informé de ce qui se passe dans sa ville. Un jour, il fait un discours auquel tous les hommes de la ville assistent et il dit : « Il y a au moins une femme adultère dans la ville. »
À Bagdad, les hommes sont de parfaits logiciens. Chaque homme sait quels sont les cocus, sauf bien sûr quand il s’agit de lui. La règle cruelle veut qu’un mari qui apprend qu’il est trompé tue sa femme devant le calife dans la nuit qui suit ; cette loi est appliquée avec rigueur et personne ne dénonce une femme adultère à son époux. Les cocus ne peuvent apprendre leur infortune que par le raisonnement.
Pendant les 49 nuits qui suivent le discours du calife rien ne se passe. La cinquantième nuit, 50 femmes sont assassinées et le lendemain le calife proclame qu’il n’y a plus aucune femme adultère. Que s’est-il passé ?
Le lendemain de la première nuit, les hommes de Bagdad ont tous fait le raisonnement suivant : « D’après le discours du calife, il y a au moins un cocu dans la ville (en fait, ils savent qu’il y en a 49 ou 50, mais nous raisonnerons par récurrence à partir de 1). S’il n’y avait qu’un seul cocu, celui-ci n’en connaîtrait aucun, et serait le seul dans ce cas. Il déduirait du discours du calife qu’il est cocu et donc, dès la première nuit, il tuerait sa femme devant le calife. S’il ne s’est rien passé pendant la première nuit, c’est qu’il y a au moins deux cocus dans la ville. » Après la deuxième nuit, chaque homme de Bagdad a fait le raisonnement suivant : « S’il n’y avait que deux cocus dans la ville, alors chacun d’eux n’en connaissant qu’un et sachant par le raisonnement fait à l’issue de la première nuit qu’il y a au moins deux cocus, saurait avec certitude qu’il est le second. Il y aurait donc eu deux femmes assassinées durant la seconde nuit. Puisqu’il ne s’est rien passé, c’est qu’il y a au moins trois cocus à Bagdad. »
Un tel raisonnement permet de savoir après la troisième nuit qu’il y a au moins quatre cocus à Bagdad, qu’il y en a au moins cinq après la quatrième nuit, etc. Après la 49e nuit, comme il n’y a pas eu d’exécution, chaque homme déduit qu’il y a au moins 50 cocus dans la ville. Chacun des cocus n’en connaissant que 49 en a conclu qu’il était le cinquantième et toutes les femmes adultères sont assassinées simultanément devant le calife lors de la cinquantième nuit : le calife peut annoncer le lendemain qu’il n’y a plus de cocus. En fait, nous pouvons dire qu’un homme de Bagdad qui connaît N femmes infidèles, si elles n’ont pas été exécutées la nuit N, sait que la sienne est infidèle et l’exécute la nuit N + 1. L’information a été distillée lentement, mais sûrement.
À la suite d’une magnifique énigme inventée par Hans Freudenthal où sont exploités ces raisonnements sur l’information et les déductions résultant des échanges, des exercices mathématiques redoutables ont été mis au point et ont fini par engendrer des questions dont certaines restent non résolues. Nous allons présenter ce domaine où l’inventivité des amateurs atteint des sommets de finesse.
Pour comprendre le principe de ces énigmes, voici trois énoncés dont la résolution ne prend que quelques minutes.
1. Sommes des diviseurs
On choisit un nombre entier N entre 1 et 12. On indique à Jacques la somme de tous les diviseurs de N. Jacques dit alors « Je ne sais pas quel est le nombre N ». Trouver le reste de la division de N par 5.
Rappelons que, parmi les diviseurs d’un nombre, il y a toujours 1 et lui-même. Par exemple, les diviseurs de 8 sont 1, 2, 4 et 8 et la somme des diviseurs de 8 est 15.
Précisons un point : dans les énigmes de cette catégorie, nous supposons toujours que les personnages (et donc Jacques) sont de parfaits logiciens. Si un raisonnement est possible pour répondre aux questions qu’on leur pose, ils le font, et quand ils répondent « Je ne sais pas », cela signifie qu’aucun raisonnement correct ne donne la solution à la question posée.
|
Toutes les sommes de diviseurs des nombres de 1 à 12 sont différentes, comme on le voit sur le tableau, sauf celles de 6 et 11 qui valent 12, car les diviseurs de 6 sont 1, 2, 3 et 6 et ceux de 11 sont 1 et 11 : si Jacques ne peut pas répondre, c’est qu’on lui a indiqué la somme 12. Le nombre N est donc soit 6, soit 11. Le reste de la division de 6 par 5 est 1 ; le reste de la division de 11 par 5 est 1, et donc le reste de la division de N par 5 est 1. Même sans connaître N, nous pouvons répondre à la question posée : le reste de la division de N par 5 vaut 1. |
2. Plus grand premier
Là encore, on choisit un nombre entier N entre 1 et 12. On indique à Jacques la somme de tous les diviseurs de N. On indique à Jules le plus grand diviseur premier de N. Jacques et Jules réfléchissent un moment et disent en même temps : « Je ne peux pas savoir quel est N. » Quel est N ?
| N | Diviseurs | Somme des diviseurs | Plus grand diviseur premier |
| 1 | 1 | 1 | |
| 2 | 1-2 | 3 | 2 |
| 3 | 1-3 | 4 | 3 |
| 4 | 1-2-4 | 7 | 2 |
| 5 | 1-5 | 6 | 5 |
| 6 | 1-2-3-6 | 12 | 3 |
| 7 | 1-7 | 8 | 7 |
| 8 | 1-2-4-8 | 15 | 2 |
| 9 | 1-3-9 | 13 | 3 |
| 10 | 1-2-5-10 | 18 | 5 |
| 11 | 1-11 | 12 | 11 |
| 12 | 1-2-3-4-6-12 | 28 | 3 |
Si Jacques dit « Je ne sais pas », c’est qu’il y a au moins deux solutions pour la somme qu’il connaît, c’est donc que cette somme est 12, car toutes les autres sommes n’apparaissent qu’une fois. Donc N vaut 11 ou 6 (comme dans le premier problème).
Si Jules dit « Je ne sais pas », c’est qu’il y a au moins deux solutions, donc N n’est ni 7 ni 11 (car 7 est le seul nombre à avoir 7 comme plus grand diviseur premier et 11 est le seul nombre à avoir 11 comme plus grand diviseur premier). Donc N est égal à 6.
3. Réponses décalées
On choisit un nombre entier N entre 1 et 20. On indique à Jacques la somme de tous les diviseurs de N. On indique à Jules le plus grand diviseur premier de N. Jacques dit « Je ne sais pas quel est N ».
Dans un second temps, donc après avoir pris en compte la réponse de Jacques, Jules dit « Je ne sais pas moi non plus ». Combien N a-t-il de diviseurs ?
| N | Diviseurs | Nombre de diviseurs | Somme des diviseurs | Plus grand diviseur premier |
| 1 | 1 | 1 | 1 | |
| 2 | 1-2 | 2 | 3 | 2 |
| 3 | 1-3 | 2 | 4 | 3 |
| 4 | 1-2-4 | 3 | 7 | 2 |
| 5 | 1-5 | 2 | 6 | 5 |
| 6 | 1-2-3-6 | 4 | 12 | 3 |
| 7 | 1-7 | 2 | 8 | 7 |
| 8 | 1-2-4-8 | 4 | 15 | 2 |
| 9 | 1-3-9 | 3 | 13 | 3 |
| 10 | 1-2-5-10 | 4 | 18 | 5 |
| 11 | 1-11 | 2 | 12 | 11 |
| 12 | 1-2-3-4-6-12 | 6 | 28 | 3 |
| 13 | 1-13 | 2 | 14 | 13 |
| 14 | 1-2-7-14 | 4 | 24 | 7 |
| 15 | 1-3-5-15 | 4 | 24 | 5 |
| 16 | 1-2-4-8-16 | 5 | 31 | 2 |
| 17 | 1-17 | 2 | 18 | 17 |
| 18 | 1-2-3-6-9-18 | 6 | 39 | 3 |
| 19 | 1-19 | 2 | 20 | 19 |
| 20 | 1-2-4-5-10-20 | 6 | 42 | 5 |
Si Jacques ne sait pas, c’est que N n’est pas parmi 1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 16, 18, 19, 20 qui sont caractérisés par la somme de leurs diviseurs.
Jules sait alors que la somme des diviseurs de N est 12 ( N = 6 ou 11), 18 ( N = 10 ou 17) ou 24 (N = 14 ou 15).
Si Jules, après avoir pris connaissance de la réponse de Jacques, ne sait pas conclure, c’est que la connaissance du plus grand diviseur premier de N lui est insuffisante et on en déduit que le plus grand diviseur est 5 (sinon il pourrait conclure). Ainsi, N = 15 ou N = 10 et donc N possède quatre diviseurs puisque chacun de ces deux nombres possède quatre diviseurs.
Ces trois premiers problèmes montrent comment l’étude détaillée des cas possibles et des étapes successives d’un échange d’informations apparemment anodin dévoile petit à petit une information d’une précision parfois inattendue.
Hans Freudenthal dans les années 1930.
Photo DR.
Ils indiquent aussi comment il faut s’y prendre pour traiter la magnifique énigme inventée par Hans Freudenthal (1905-1990) en 1969. Celle-ci est d’un niveau de difficulté supérieure. Je vous invite à y réfléchir en vous aidant éventuellement d’une feuille de papier et, pourquoi pas, d’un ordinateur.
Le problème de Freudenthal
On choisit deux entiers X et Y, avec 1 < X <Y et X + Y ≤ 100. On indique à Patricia le produit P de X et Y. On indique à Sylvie la somme S de X et Y. Le dialogue est alors le suivant :
1. Patricia : « Je ne sais pas quels sont les nombres X et Y. »
2. Sylvie : « Je savais que vous ne connaissiez pas X et Y. »
3. Patricia : « Eh bien alors, maintenant, je connais X et Y. »
4. Sylvie : « Eh bien, moi aussi je les connais maintenant. »
À vous de trouver X et Y.
Après avoir soutenu une thèse sous la direction de Heinz Hopf en 1930, Freudenthal occupa la chaire de mathématiques appliquées de l’Université d’Utrecht de 1946 à 1975 (jusqu’à 70 ans…). Ses contributions de chercheur portent sur la topologie, la géométrie et la théorie des groupes de Lie. Un Institut de mathématiques porte aujourd’hui son nom à Utrecht. Il s’intéressa aussi à la didactique des mathématiques et fut en particulier le rédacteur de la rubrique des problèmes du journal Nieuw Archief voor Wiskunde (Nouvelles Archives de Mathématiques). C’est dans cette rubrique que parut, pour la première fois et en néerlandais, le célèbre problème qui nous occupe aujourd’hui.
L’énigme de Freudenthal se résout en quatre étapes.
1) Notons V1 l’ensemble des nombres entiers P qui peuvent être factorisés de deux façons différentes au moins : P = XY avec 1 < X < Y et X + Y ≤ 100.
L’ensemble V1, qui est l’ensemble {12, 18, 20,…, 2280, 2340, 2352, 2400}, possède 574 éléments.
| Ensemble V1 des nombres P qui sont, de deux façons différentes au moins, égaux au produit de deux facteurs X et Y |
| {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} |
D’après le point 1 du dialogue, le produit P = XY des deux nombres recherchés est un nombre de V1.
Notons V2 l’ensemble des nombres entiers S ≤ 100 qui ont la propriété que pour toute décomposition en somme S = X + Y avec 1 < X < Y, le produit XY est dans V1.
2) D’après le point 2 du dialogue de Sylvie et Patricia, les nombres X et Y cherchés sont tels que S est dans V2. Étudions V2, l’ensemble des nombres dont toute somme en deux nombres X et Y donne un produit XY ambigu (notons que V1 et V2 sont calculables par les deux protagonistes).
a) Il est immédiat que V2 ne contient que des nombres-sommes S tels que 5 ≤ S ≤ 100.
b) V2 ne contient pas de nombres ≥ 55. En effet, si S ≥ 55, il s’écrit S = 53 + (S – 53), X = 53, Y = S – 53 ; or nous allons démontrer que le produit correspondant P = XY = 53 x (S – 53) n’est pas dans V1. En effet, puisque 53 est premier, une autre factorisation de P comporte nécessairement un facteur ≥ 2 x 53 et donc ne satisfait pas le critère X + Y ≤ 100 ; cela interdit à P d’avoir deux factorisations satisfaisant P = XY avec 1 < X < Y et X + Y ≤ 100.
c) V2 ne contient pas de nombre-somme S pair. En effet, si S est paire, elle peut s’écrire comme somme de deux nombres premiers (c’est la conjecture de Goldbach qui, pour les entiers ≤ 100, se démontre facilement) S = P1 + P2 et donc le nombre P = P1 x P2 n’est pas dans V1 à cause de l’unicité de la décomposition d’un nombre en facteurs premiers.
d) V2 ne contient pas de nombre S de la forme Q + 2 avec Q premier. En effet si S = Q + 2, le produit P = 2 x Q n’est pas dans V1 (là aussi à cause de l’unicité de la décomposition d’un nombre en facteurs premiers).
e)Le nombre 51 n’est pas dans V2, car 51 = 17 + 34 et 17 x 34 n’est pas dans V1.
En se fondant sur ces remarques et en faisant défiler tous les entiers entre 5 et 55, on en déduit que l’ensemble des nombres de V2 est {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}.
Si vous trouvez cette partie du raisonnement trop compliquée, vous pouvez envisager chaque nombre-somme S entre 1 et 100 et tester si ce nombre est dans V2 en étudiant individuellement chaque décomposition S = X + Y et voir si le produit XY est bien ambigu. Vous retrouverez bien sûr le même ensemble V2.
| Ensemble V2 des S ≤100 dont toute décomposition S = X + Y avec X < Y est telle que XY est dans V1 |
| {11, 17, 23, 27, 29, 35, 37, 41, 47, 53} |
3) Considérons maintenant, pour chaque nombre-somme S de V2, l’ensemble des décompositions S = X + Y avec 1 < X< Y et les produits qui en résultent, que nous notons K (S). Pour 11 par exemple, on a 11 = 2 + 9 qui donne 18, 11 = 3 + 8 qui donne 24, 11 = 4 + 7 qui donne 28, 11 = 5 + 6 qui donne 30, et donc : K (11) = {18, 24, 28, 30}.
On a aussi (ce calcul est faisable à la main, mais bien sûr un ordinateur aidera) :
K (17) = {30, 42, 52, 60, 66, 70, 72}, K (23) = {42, 60, 76, 90, 102, 112, 120, 126, 130, 132}, … , 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}.
| Pour chaque valeur de S dans V2 formation des listes K(S) des produits P correspondant à S |
| 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} |
D’après le point 3 du dialogue de Sylvie et Patricia, le produit P des deux nombres cherchés appartient à un seul des ensembles K (11), K (17), K (23), … , K (53). En effet, s’il appartenait à deux ensembles K (S1) et K (S2), Patricia qui connaît P et qui sait que S est dans V2 (elle a mené le même raisonnement que vous) ne pourrait savoir quel est le bon nombre S. Donc elle vérifie que son produit P est dans un seul K et détermine ainsi S. Connaissant le produit et la somme de deux nombres, il est facile de déterminer ces nombres : comme Patricia connaît P et S, elle connaît X et Y.
4) Sachant cela, Sylvie élimine de chaque K (S) tous les nombres qui apparaissent dans d’autres pour former l’ensemble des K’ (S). Par exemple 60 qui est dans K (17) et K (23) est éliminé deK’ (17) et K’ (23).
On obtient alors de nouvelles versions K’ des ensembles K :
K’ (11) = {18, 24, 28}, K’ (17) = {52} … 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}.
| Ensemble des valeurs de K’(S) où les doublons de K(S) ont été éliminés |
| 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, 264, 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} |
On remarque que K’ (17) n’a qu’un seul élément et que tous les autres en ont au moins deux. D’après le point 4 du dialogue, nous savons que disposant de ces valeurs possibles de S, Sylvie a pu trouver X et Y, c’est donc que le S dont elle dispose lui permet de connaître P, et donc c’est que S = 17 et que P = 52. Il en résulte que X = 4 et Y = 13. Notons que nous avons conduit ce raisonnement sans connaître ni S ni P, et que la solution X et Y est unique.
Attention aux modifications de l’énoncé
Un algorithme assez simple à programmer permet de faire raisonner l’ordinateur à votre place. Il permet aussi d’étudier ce qui se passe quand on fait varier les données du problème de Freudenthal.
Notons en particulier qu’il faut être très prudent dans la construction d’énigmes de ce type, car les inégalités fixées au départ 1 < X < Yet X + Y ≤ 100 sont utilisées dans le cours du raisonnement et le changement d’une seule peut tout bouleverser. Une mésaventure désagréable est ainsi arrivée à Martin Gardner qui, en voulant simplifier le problème initial, avait repris l’énoncé en précisant que les inconnues X et Y vérifiaient : 2 ≤ X ≤ Y ≤ 20. Cela correspond bien à une zone plus petite (l’énigme peut donc être abordée à la main plus facilement) et dans la zone retenue par Martin Gardner il y a bien les deux nombres X = 4 et Y = 13 de la solution. Pourtant, l’énigme de Martin Gardner n’a pas de solution, car le traitement des listes, quand on prend en compte les deux derniers échanges entre Patricia et Sylvie, est maintenant différent et ne donne plus rien.
Si on remplace 100, dans le problème de Freudenthal, par un nombre M différent, on obtient une suite infinie de problèmes qui peuvent avoir 0, 1 ou plusieurs solutions selon le nombre M retenu. La solution X = 4, Y = 13 du problème initial reste valide pour tous les M à partir de 65 et donc reste une solution quand M tend vers l’infini : on dit que c’est une solution stable.
Ce n’est pas le cas de la solution X = 67, Y = 82 qui n’est une solution que si M appartient à l’intervalle des entiers entre M = 4721 et M = 5485 : on dit que c’est une solution fantôme.
La solution X = 4, Y = 13 est l’unique solution pour toutes les valeurs de M entre 65 et 1684. Vous pouvez donc modifier l’énoncé initial de Freudenthal en précisant 1 < X < Y et X + Y ≤ 1684, il n’aura toujours qu’une seule solution (et le problème sera devenu plus difficile bien sûr).
Une question envisagée par John Kiltinen et Peter Young est celle du nombre de solutions au problème lorsque M tend vers l’infini. On conjecture qu’on trouvera une infinité de couples solutions et même qu’on trouvera une infinité de solutions stables. On n’a pour l’instant réussi à démontrer aucune de ces deux conjectures.
Voici les dix premières solutions stables avec le nombre M à partir duquel elles apparaissent : [M = 65, X = 4, Y = 13], [M = 1685, X = 4, Y = 61], [M = 9413, X = 32, Y = 131], [M 1970, X = 16, Y = 73], [M = 2522, X = 16, Y = 111], [M = 6245, X = 32, Y = 311], [M = 6245, X = 64, Y = 73], [M = 6893, X = 4, Y = 229], [M = 72365, X = 8, Y = 239], [M 237173, X = 4, Y = 181]. À la vue de ce début, on pourrait croire que le premier élément X d’une solution stable est toujours une puissance de 2. C’est faux : plus loin, on trouve la solution stable X = 201 et Y = 556, qui est active à partir de M = 966293.
Au lieu de faire varier la quantité M qui majore la somme X + Y, on peut dans les données du départ faire varier le 1 des inégalités 1 < X < Y en le remplaçant par m (ce qui donne m < X < Y). L’étude de ces problèmes est assez étonnante, car on constate qu’il n’y a aucune solution dès que m ≥ 3 (et cela quel que soit M) ; on aimerait bien démontrer que c’est vrai, mais on n’y arrive pas. On conjecture donc que : pour m ≥ 3, le problème de Freudenthal défini à partir de m < X < Y n’a jamais de solution.
De nombreuses variantes ont été imaginées à partir du problème initial. Pour en voir quelques-unes, passez à la suite.
Toujours plus fort
Voici une variante en sept étapes qui est l’œuvre de Clive Tooth.
On choisit deux nombres X et Y avec 2 ≤ X ≤ Y et X + Y ≤ 5000. On indique leur somme S à Sylvie et leur produit P à Patricia.
On assiste alors au dialogue suivant.
1. Patricia : « Je ne sais pas quels sont les nombres X et Y. »
2. Sylvie : « Je savais déjà que vous ne connaissiez pas X et Y. »
3. Patricia répond : « Ah bon, eh bien alors maintenant je connais X et Y. »
4. Sylvie dit alors : « Eh bien, moi aussi je les connais maintenant. »
On aimerait bien pouvoir en déduire X et Y,mais comme X et Y peuvent atteindre 5000, cela n’est pas possible pour celui qui assiste à l’échange. Heureusement un troisième personnage, Julien, qui a assisté à l’échange, intervient.
5. Julien : « Pour l’instant, je ne peux pas connaître X et Y. »
6. Sylvie lui répond : « Pourtant, si je t’indique la valeur de X tu pourras connaître Y. »
7. Julien s’exclame alors : « Maintenant je connais X et Y. »
Et vous ?
Cette fois l’usage d’un ordinateur semble inévitable. Après les quatre premières étapes du dialogue, on découvre qu’il reste dix solutions compatibles :
| Solutions | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| X | 4 | 4 | 4 | 16 | 16 | 32 | 32 | 64 | 64 | 67 |
| Y | 13 | 61 | 229 | 73 | 111 | 131 | 311 | 73 | 309 | 82 |
| S | 17 | 65 | 233 | 89 | 127 | 163 | 343 | 137 | 373 | 149 |
| P | 52 | 244 | 916 | 1168 | 1776 | 4192 | 10976 | 4672 | 19776 | 5494 |
On en déduit alors facilement la solution. La connaissance de X ne suffit pas à connaître Y lorsque X vaut 4, 16, 32 ou 64, car il y a trois solutions avec X = 4, deux solutions avec X = 16, deux avec X = 32 et deux avec X = 64. Le point 6 du dialogue indique donc que X = 67.
Le reste vient immédiatement : Y = 82, S = 149 et P = 5494.
Une journée de réflexion !
Il est temps de vous présenter le problème de cette catégorie que je trouve le plus étonnant. Mis au point tout récemment par Axel Born, Kor Hurkens et Gerhard Woeginger, trois universitaires qui ont pris la peine d’étudier soigneusement cette catégorie d’énigmes mathématiques, il est à la fois simple et difficile : 23 affirmations simultanées consistant en d’élémentaires « Je ne sais pas » proférés par quatre personnages – supposés excellents logiciens – les conduisent en même temps que vous à trouver une solution unique à un problème à cinq inconnues. Bien sûr, là encore l’ordinateur vous aidera. Résoudre à la main cette énigme extrême est envisageable… si vous avez une journée devant vous et si vous êtes certain de ne pas vous tromper dans les petits calculs qu’elle nécessite.
Voici donc la variante du problème de Freudenthal due à Axel Born, Kor Hurkens et Gerhard Woeginger. C’est la plus difficile et la plus belle de toutes les énigmes de ce type. Nous l’intitulerons : Une journée de réflexion !
On choisit cinq nombres a b c d e vérifiant :
1 ≤ a < b < c < d < e ≤ 10
On indique à Patricia leur produit P = abcde,
à Sylvie, leur somme S = a + b + c + d + e,
à Christian, la somme de leurs carrés C = a2 + b2 + c2 + d2 +e2,
et à Vincent, la valeur V = (a + b + c) (d + e).
1. Une heure après qu’on leur a posé le problème, les quatre personnages qu’on interroge simultanément répondent tous ensemble : « Je ne connais pas les nombres a b c d e. »
2. Une heure après, les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
3. Une heure après, les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
4. Une heure après, les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
Etc.
23. Une heure après (soit 23 heures après la formulation de l’énoncé !), les quatre personnages qu’on interroge à nouveau répondent encore tous ensemble : « Je ne connais pas les nombres a b c d e. »
Mais après cette 23e réponse, les visages des quatre personnages s’éclairent et tous s’exclament : « C’est bon maintenant, je connais a b c d e. »
Quels sont les cinq nombres a b c d e ?
Il y a au départ 252 quintuplets a b c d e possibles. Certains d’entre eux donnent une somme S qui permettrait de retrouver a b c d e, telle la somme 15 = 1 + 2 + 3 + 4 + 5, car c’est la plus petite somme possible. Le fait que Sylvie ait indiqué au point 1 qu’elle ignorait a b c d e signifie que le quintuplet 1 2 3 4 5 n’est pas le bon. De même, certains produits ne peuvent être obtenus qu’une fois et peuvent être éliminés après l’étape 1. De même pour C et V.
L’élimination de ces quintuplets fait passer les 252 possibilités à 140. Bien évidemment, on fait l’hypothèse que les quatre personnages mènent ce raisonnement d’élimination pendant l’heure qui suit l’énoncé du problème : ce n’est pas tout à fait immédiat, c’est pourquoi un délai d’une heure leur a été accordé.
À partir de ces 140 possibilités pour a b c d e,chaque personnage peut à nouveau raisonner comme précédemment. Si Sylvie indique qu’elle ne peut pas trouver a b c d e lors de l’étape 2, c’est que les S n’apparaissant qu’une fois dans la liste des 140 possibilités peuvent être éliminées. De même pour les P, C et V. On arrive alors à 100 quintuplets possibles.
Petit à petit, la réduction des solutions donne des quintuplets candidats de moins en moins nombreux : on en obtient successivement 85, 73, 64, 62, 60, 57, 54, 50, 47, 44, 40, 36, 33, 31, 28, 24, 19, 13, 8, 4.
La prise en compte de l’étape 23 conduit à une solution unique. À ce moment, tout le monde (et en particulier vous) sait que : S = 28, P = 3360, C = 178, V = 195 et donc que a = 2, b = 5, c = 6, d = 7, e = 8.
(L’étape précédente conduit à quatre possibilités : S = 26, P = 1680, C = 178, V = 153 ou S = 30, P = 3360, C = 226, V = 216 ou S = 28, P = 3360, C = 178, V = 195 ou S = 28, P = 4032, C = 174, V = 195.)
Ces exercices ne sont pas aussi futiles qu’ils le paraissent : Hans Freudenthal s’est intéressé à la communication avec des extraterrestres dont il était persuadé de l’existence (il a même écrit un livre à ce sujet en 1960). Cette communication imposait l’étude de signaux non ambiguë. Mais cela est une autre histoire…
- H. FREUDENTHAL, Problem No. 223. Nieuw Archief voor Wiskunde 17, 152, 1969 ; Solution to Problem No. 223. Nieuw Archief voor Wiskunde 18, 102–106, 1970.
- M. GARDNER, Mathematical Games, in Scientific American 241 (6), 20–24, 1979.
- L. SALLOWS, The Impossible Problem, in The Mathematical Intelligencer, 17, 27–33, 1995.
- Axel BORN, Kor HURKENS et Gerhard WOEGINGER, The Freudenthal Problems and its ramifications, in Bulletin of the European Theoretical Computer Science Society, Part I : octobre 2006, 175-191 ; Part II : 2007.
- John BURKARDT, The Impossible Puzzle, 2006.
Une première version de ce document est parue dans la rubrique « Logique et calcul » de la revue Pour la Science n° 356 de juin 2007.
Newsletter
Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité
Niveau de lecture
Aidez-nous à évaluer le niveau de lecture de ce document.
Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !
Jean-Paul Delahaye
Professeur émérite d'informatique à l'Université des Sciences et Technologies de Lille (Lille 1) et chercheur au Centre de recherche en informatique, signal et automatique de Lille (CRIStAL).