IV-5. Somme et produit de deux entiers
FOIRE AUX QUESTIONS DE fr.sci.maths CHAPITRE IV: ENIGMES
IV-5. Somme et produit de deux entiers
SUJET PRECEDENT - INDEX - SUJET SUIVANTa) Enoncé. Un prof de maths donne un problème à résoudre à ses deux meilleurs élèves, Pierre et Sophie. Il donne à Pierre le produit de deux nombres entiers compris (au sens large) entre 2 et 100, et à Sophie la somme des deux mêmes nombres, puis il leur demande s'ils peuvent déterminer quels étaient les nombres de départ. Pierre: Non, je ne peux pas trouver ces deux nombres. Sophie: Je le savais. Pierre: Dans ce cas, je connais les deux nombres. Sophie: Alors moi aussi. Sachant que les deux élèves sont d'excellents logiciens et que leurs quatre déclarations étaient rigoureusement exactes, saurez-vous être aussi futés qu'eux, et trouver les deux nombres choisis par le professeur ? b) Commentaires. L'énoncé tel qu'il est présenté ici est le plus proche de ce qui est en général posé dans news:fr.sci.maths. Malheureusement, il lui manque des précisions importantes sur ce que le prof de maths dit effectivement aux élèves. D'abord, il n'est pas précisé que Pierre sait que Sophie a la somme, et que Sophie sait que Pierre a le produit. Bon, d'accord, c'est « évident ». Mais il y a un autre point qui semble « évident » alors qu'il est souvent source d'erreurs de raisonnement. Cet autre point, c'est que l'on ne sait pas si Pierre et Sophie connaissent la valeur minimum (2) et la valeur maximum (100) des nombres de départ. Pour ce qui est de la valeur minimum, il faut qu'ils la connaissent ; sinon, le problème est impossible (par exemple, s'ils pensent que les nombres commencent à 1 au lieu de 2, alors la seule solution serait 1 et 4, qui ne rentre pas dans le cadre de l'énoncé). En ce qui concerne la valeur maximum, les deux cas sont possibles (soit ils connaissent la limite, soit ils ne la connaissent pas), ce qui donne deux problèmes différents, intéressants tous les deux. c) Solutions. Puisqu'il y a deux interprétations possibles de l'énoncé, il y a aussi deux solutions distinctes. La première (c.1) suppose que Pierre et Sophie savent que les nombres sont compris entre 2 et 100, alors que la seconde (c.2) suppose qu'ils savent seulement que les nombres sont supérieurs ou égaux à 2. Néanmoins, la méthode utilisée est la même dans les deux cas, à savoir prendre chacune des 4 affirmations dans l'ordre, et en déduire des informations précieuses sur les sommes S et produits P possibles. c.1) 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*25 ou 5*15, mais on ne peut pas avoir P = 77 car alors la décomposition serait unique : 7*11. 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*11) - le cube d'un nombre premier (par exemple 125 = 5*25) - le double du carré d'un premier plus grand que 10 (par exemple, 242 = 2*11*11 = 11*22 : la décomposition en 2*121 est impossible) - un multiple strict d'un nombre premier plus grand que 50 (par exemple 318 = 6*53) - le produit du carré d'un premier plus grand que 10 par un nombre premier (par exemple 242 = 2*11*11 = 11*22 ; la décomposition en 2*121 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" : 11 = 2+9 ; 2*9 = 18 = 3*6 11 = 3+8 ; 3*8 = 24 = 2*12 = 4*6 11 = 4+7 ; 4*7 = 28 = 2*14 11 = 5+6 ; 5*6 = 30 = 2*15 = 3*10 En revanche, la somme 13 ne convient pas car : 13 = 2+11 ; 2*11 = 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*3 + 2), 17 (3*5 + 2), 23 (3*7 + 2), 27 (5*5 + 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 <= S <= 153, on peut écrire S = 53 + n, avec 4 <= n <= 100, si 155 <= S <= 197, on peut écrire S = 97 + n, avec 58 <= n <= 100, si S = 199, on peut écrire S = 100 + 99. Dans chacun de ces trois cas, le produit P correspondant (soit 53*n, soit 97*n, soit 100*99) a une décomposition unique. On peut enfin supprimer la somme S = 51 = 17 + 34, car le produit P = 17*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. 11 : 18 24 28 30 17 : 30 42 52 60 66 70 72 23 : 42 60 76 90 102 112 120 126 130 132 27 : 50 72 92 110 126 140 152 162 170 176 180 182 29 : 54 78 100 120 138 154 168 180 190 198 204 208 210 35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306 37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342 41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420 47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552 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 --- 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: 11 : 18 24 28 17 : 52 23 : 76 112 130 27 : 50 92 110 140 152 162 170 176 182 29 : 54 100 138 154 168 190 198 204 208 35 : 96 124 174 216 234 250 276 294 304 306 37 : 160 186 232 252 270 336 340 41 : 114 148 238 288 310 348 364 378 390 400 408 414 418 47 : 172 246 280 370 442 480 496 510 522 532 540 550 552 53 : 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702 --- 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. c.2) Solution dans le second cas (valeur maximum inconnue). Pierre: Non, je ne peux pas trouver ces deux nombres. Ceci signifie que le produit n'est pas le carré ou le cube d'un nombre premier, ni le produit de deux nombres premiers. Nous ne pouvons rien en déduire de plus pour le moment. --- Sophie: Je le savais. Comme dans le premier cas, nous pouvons éliminer toute somme paire et toute somme d'un nombre premier avec 2, et il nous reste les sommes égales à un nombre composé impair plus 2. Contrairement au premier cas, nous ne pouvons éliminer aucune autre somme. La liste (incomplète) des sommes et produits possibles est la suivante: 11 : 18 24 28 30 17 : 30 42 52 60 66 70 72 23 : 42 60 76 90 102 112 120 126 130 132 27 : 50 72 92 110 126 140 152 162 170 176 180 182 29 : 54 78 100 120 138 154 168 180 190 198 204 208 210 35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 ... 37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 ... 41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 ... 47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 ... ... --- Pierre: Dans ce cas, je connais les deux nombres. Comme tout-à-l'heure, nous éliminons les produits P qui se trouvent plus d'une fois dans la liste. Il reste (liste exhaustive pour toutes les sommes inférieures à 200) : 11 : 18 24 28 17 : 52 23 : 76 112 27 : 50 92 140 152 176 29 : 54 100 208 35 : 96 124 216 304 37 : 160 232 336 41 : 148 288 400 47 : 172 280 496 51 : 98 144 188 308 344 608 620 644 53 : 520 592 57 : 212 260 392 656 800 59 : 220 688 65 : 244 67 : 192 472 1116 71 : 268 448 880 77 : 292 832 976 79 : 228 568 1504 83 : 316 1072 1216 87 : 332 632 836 1136 1340 1472 1880 89 : 1168 93 : 356 1040 1856 1952 95 : 1264 1984 97 : 712 1296 101 : 388 1144 2368 2440 107 : 412 2752 113 : 436 1552 117 : 452 872 1616 3392 119 : 1648 2728 121 : 904 2848 123 : 242 476 1712 3440 3776 125 : 484 1744 3904 127 : 1776 131 : 384 508 3784 4288 135 : 266 524 896 1016 1904 2996 3296 3956 4544 137 : 4672 143 : 556 2032 4120 5056 145 : 1096 2176 3616 147 : 290 1112 1496 2096 2432 3680 4280 5312 155 : 604 2224 157 : 1192 3712 161 : 628 2320 6208 6424 163 : 4192 167 : 652 2416 5080 6592 171 : 338 668 1304 2480 2888 3020 3404 3888 4448 5240 5504 6848 6968 7100 7304 173 : 2512 6976 177 : 692 3140 7232 179 : 2608 185 : 724 187 : 1432 7552 189 : 374 1448 2768 2924 5024 5624 7208 7448 7808 191 : 8128 197 : 772 2896 --- Sophie: Alors moi aussi. Ici encore, il doit rester un seul produit sur la ligne de la somme correspondant à ce qu'a Sophie. Là encore, les nombres 4 et 13 sont solution (S=17, P=52), mais ce ne sont plus les seuls. Les autres solutions sont: 4 et 61 (S=65, P=244), 16 et 73 (S=89, P=1168), 64 et 73 (S=137, P=4672). Bien évidemment, on ne tiendra pas compte des cas où l'un des nombres est plus grand que 100, par exemple pour S=127 et P=1776: les nombres seraient 16 et 111.