petite énigme sympa

[matthias]

Deux mathématiciens, Serge et Pierre, descendent l'escalier de 'immeuble où ils habitent. Leur concierge, qui rève de mettre en défaut ces esprits brillants, les attend.
"Tenez, dit-elle à Pierre en lui tendant un morceau de papier, j'ai écrit le produit de deux nombres entiers compris entre 2 et 100, saurez-vous les trouver ? Pour vous, j'ai écrit leur somme, continue-t-elle en tendant un second morceau de papier à Serge.
- Je ne peux pas déterminer ces nombres avec leur seul produit, annonce Pierre.
- Je le savais, dit Serge.
- Ah, bon ? Alors, je les connais, dit Pierre.
- Dans ce cas, moi aussi, rétorque Serge.
Quels sont ces deux nombres ?

En désespoir de cause j'ai écris un programme pour résoudre le problème. Ca marche bien, mais j'aimerais une solution plus subtile. J'ai pas mal avancé, mais j'arrive pas au bout. Des idées ?
-----

[invitedebe236f]

pierre ne peut pas trouver c est qu il a pas un nombre premier
si serge le savait c est que ca somme ne peut etre 1+nombre premier

mais bon t' as deja du voir ca

[matthias]

En fait si Pierre ne peut pas trouver, c'est qu'il n'a pas un produit de 2 nombres premiers, ni même un nombre premier au cube. Il ne peut évidemment pas avoir un nombre premier, vu qu'il a le produit de 2 nombres différents de 1.
Bon j'ai été un petit peu plus loin que ça quand même, il faudra que je prenne le temps de le mettre par écrit correctement.
Pour la suite, j'utilise le fait que tout nombre pair (hormis 0 et 2) est une somme de 2 nombres premiers (conjecture de Goldbach je crois) ...

[Bobby]

Il n'y a pas vraiment de méthode subtile pour cette énigme, après avoir traduit les différents critères de manière formelle tu peux virer un certain nombre de coupes. Ensuite il faut essayer tous les couples et vérifier lequel coincide avec l'énoncé.

Pour commencer Pierre dit ne pas pouvoir trouver à partir du produit, forcément il ne s'agit pas de deux nombres premiers. Tu peux donc déjà virer tous les couples de premiers.

Serge a dit le savoir, le nombre que le concierge lui a transmis ne peut donc s'écrire comme somme de nombres premiers. Ca permet de virer tous les couples dont la somme est paire (conjecture de Goldbach vérifiée jusqu'à cet ordre).

Tu peux trouver de meilleurs affinements par la suite mais dans tous les cas ça sera une fin de bourrin.

[A voir en vidéo sur Futura]

[matthias]

En méthode bourrin, je suis d'accord c'est facile, d'où le programme. Mais je ne suis pas persuadé qu'on ne puisse pas ruser un peu plus ...

[Bobby]

Je parle en connaissance de cause, me suis déjà pris la tête sur cete énigme justement pour trouver une solution subtile. Mais bon arrivé à un certain point on ne trouve plus rien et après une recherche sur l'Internet il se trouve que la solution admise est de faire le bourrin à partir d'un certain temps. Je t'ai juste donne les deux premières étapes pour affiner ton champ de recherche, il y en a d'autres mais aucune solution ne te filera le couple solution. A moins qu'il y ait du nouveau depuis. De plus quand tu affines ta recherche, le programme devient plus complexe, tu fais ça en basic ?

[matthias]

Clairement, la solution pour le programme (en C, j'aime pas le basic), c'est de jouer les gros bourrins dès le départ, sans chercher à affiner. C'est un chouya plus lent, mais c'est beaucoup plus simple, et de toute façon on a la solution en une fraction de seconde.
Ceci dit c'est vrai qu'après avoir affiné un peu plus avec Goldbach, je bloque. J'espérais juste que quelqu'un ait une meilleure idée que moi.

[Bobby]

Voici un lien vers une réponse plus complète :

http://faq.maths.free.fr/html/node55.html

Excellent site soit dit au passage.

[invitebf65f07b]

bonjour
cette enigme est bien sympa, je me suis penche un peu dessus et j'en suis arrive un resultat partiel sans programmation:

- Je ne peux pas déterminer ces nombres avec leur seul produit, annonce Pierre.

si P etait le produit de 2 premiers alors pierre saurait repondre.

- Je le savais, dit Serge.

donc serge est capable de montrer, a partir de S, que les 2 nombres (a et b) ne sont pas 2 premiers.
on sait donc que S /= p1 + p2 avec p1 et p2 premiers.
si p1 > 2 et p2 > 2 alors p1 + p2 est pair et parcourt tous les nombres pairs selon la conjecture de goldbach, idem pour p1 = p2 = 2, sinon p1 + p2 = 2 + p2 (impaire).
on peut donc dire que S est impaire avec (*) : S/= 2 + p , p premier.
on conclut que a est pair et b impair (ou inversement).

la parite de a permet d'ecrire en facteurs premiers : P = 2^k * p1 * p2 *...* pn avec k>=1 et n>=1 .

- Ah, bon ? Alors, je les connais, dit Pierre.

au vu de l'ecriture de P, n=1 car sinon pierre aurait plusieurs choix possibles.
on a donc P = 2^k * p1 , k>0
autrement dit : a=2^k , b= p1 premier.

la relation (*) nous donne 2^k + p1 /= 2 + p avec p premier
donc p - p1 /= 2^k + 2 , k>0 .
ici, a l'aide d'un tableau excel par exemple, on peut dresser le tableau de la difference entre les premiers inferieurs a 100 et comparer au valeurs possibles de 2^k + 2 (2,6,14,30,62,...).
on constate que seuls 19 et 79 sont possibles pour p1.
si p1=79 , en fait pierre aurait pu parler des le debut car il sait que a et b sont plus petit que 100 et dans ce cas il aurait dit a=2^k et b=79.
donc p1 = 19.

on a donc a=2^k et b=19, de plus a<100 donc k= 2, 3, 4, 5 ou 6 .

c'est a dire S = 23, 27, 35, 51 ou 83

mais la je bloque un peu... si vous voyez comment continuer avec la derniere replique...

[invitebf65f07b]

en mgrattant, on peut encore eliminer 51 et 83. en effet 83=79*4 et 51=17*34 ce qui empecherait serge d'affirmer (2).
il reste alors 23, 27 et 35 pour S

[invite0dacff7f]

apres une lecture rapide du problème et de la solution proposée par robert et ses amis. Une idée m'est venue à l'esprit.

Est-ce que 2 et 100 sont exclus? si oui, on a la solution!

Si b=19 ou 71 et on sais que 71 est impossible. on conclut b=19

k=2 et a=4 obligatoirement selon moi car on peut toujours décomposer les autres 2^k car les produits se décomposerons en plus de terme.

Si on prend S=27, d'autres solutions sont possibles (19*8=152, 4*38 aussi) et le 2e mathématicien ne peut confirmer que lui aussi le sais. Dans le cas de S=23, 4*19=76, si 2 est exclu, aucune autre solution n'est possible!


Parcontre, je ne sais pas si je dérappe ...

En espérant aidé à ceux qui ont plus de temps à y consacrer. Toutefois, l'énigme est vraiment intéressante, Chapeau Mathias!

[matthias]

2 et 100 ne sont pas exclus.

[moijdikssékool]

on peut les exclure car sinon le produit se terminerait par 00 ou serait pair et Pierre dirait tout de suite qu'il peut déterminer les 2 nombres à partir du produit

[invitebf65f07b]

pas d'accord avec toi : 25*16=400

[moijdikssékool]

pas d'accord avec toi : 25*16=400

mince, je croyais que les nombres étaient premiers
100 n'est pas premier de toute façon

[moijdikssékool]

si 1 chiffre doit être impair, l'autre pair et les 2 ne doivent pas être tous les 2 premiers, sans que les décompositions en nombres premiers des 2 chiffres ne se mélangent lorsqu'on les multiplie, avec n1 = 2^j*p1^a1*p2^a2*... pk^ak (j>0) et n2 = 2k+1, afin que Pierre puisse rétorquer

Ah, bon ? Alors, je les connais

, il faut nécessairement que P soit le moins élevé possible (les inconnues diminuent en nombre avec la valeur de P). Donc p1^a1*p2^a2*... pk^ak basta, et comme "les décompositions en nombres premiers des 2 chiffres ne se mélangent lorsqu'on les multiplie", j = 2 et n2 premier (j = 1 entraîneraît n1 et n2 premiers)

d'ou n1 = 4 et n2 = 3

vérification:
P = 12, S = 7

à partir de 12, Pierre ne peut conclure: 12 = 4*3 = 2*6
à partir de 7, Serge confirme étant donné 7 n'est pas pair, donc les 2 chiffres ne peuvent pas être premiers
Pierre a le choix: (2,6) et (4,3). Il sait, par Serge, que la somme des les 2 chiffres ne doit pas être paire. Il conclu que les chiffres sont donc: 4 et 3
Serge, lui, a le choix: (4,3) ou (5,2). (5,2) étant premiers alors que (4,3) non, et sachant que Pierre a trouvé un couple d'entiers non premiers, la réponse est doncc 4 et 3 pour Serge, même résultat que pour Pierre

4 et 3 vérifient bien les conditions

[invitebf65f07b]

y a un probleme : si serge voit S = 7, rien ne peut lui dire que les 2 nombres cherches ne sont pas 5 et 2 auquel cas pierre pourrait repondre c'est a dire qu'avec S=7, serge ne peut dire "- Je le savais, dit Serge."
de plus tu proposes un resultat en desaccord avec ma demonstration, j'imagine donc que tu la trouve invalide. je suis humain et donc capable d'erreurs (la n'est pas la question) mais si un point te semble louche dans ma demonstration , ca m'interesse d'en discuter

[matthias]

Il faudra que je regarde ça en détail moi aussi, mais effectivement 4 et 3 n'est pas la solution.

[moijdikssékool]

qu'avec S=7, serge ne peut dire "- Je le savais, dit Serge."

j'ai cru, au travers des posts, que seule une somme paire pouvait être le résultat de la somme de 2 nombres premiers... c'étais sans compter que 2 est à la fois pair et premier

t'inquiètes pas j'ai regardé et ca a pas l'air d'être faux

Donc serge n'aurait pu conclure

Je le savais, dit Serge

si S était impair
il faut tenir compte de 2, que S soit stirctement plus grand que 2 + 100 = 102 pour conclure que les 2 nombres sont plus grands que 2 et potentiellement premiers sans être pairs. Si S>102 et impair, Serge est sûr que les 2 nombres ne sont pas premiers, et donc qu'il y en a 1 qui est pair et l'autre impair


on a ( ou est premier autre que 2)

1)n1 = 2 , n2 = (p1^a1*p2^a2*... pk^ak impair, k>1 ou a1>1) exclu par S > 102

soit

2)n1 = (2^j*p1^a1*p2^a2*... pk^ak, j>1 ou (k>0 ou a1>10) et j=1) + n2 = (P1^A1*P2^A2*... Pm^Am impair)

Ah, bon ? Alors, je les connais, dit Pierre

j'en arrive toujours à dire que P doit être minimal, donc n1 et n2 aussi
le choix restant:

(n1 = 2^j ou 2*p1), n2 = P1 tel que n1 + n2 > 102

prenons P1 = 3, p1 = 50, on a n1 = 100, n2 = 3

P = 300, Pierre ne peut conclure
S = 103, Serge peut dire qu'il le savait car 103 n'est pas la somme de 2 nb premiers <= 100
Pierre conclut donc que Serge a un nombre strictement + grand que 102
Or 300/4 = 75
300/5 = 60
etc...
300/98 = 3.06 n'appartient pas à N

or 75+4, 60+5, ... ne dépassent pas 102
la seule qui puisse le faire est 100+3 (300/3 = 100). Donc n1 = 100, n2 = 3 conviennent

la réplique

Dans ce cas, moi aussi, rétorque Serge

indique que S est minimale (et supérieure à 102 d'après la réplique précédente de Serge)

[matthias]

Bon, reprenons depuis le début.

bonjour
si P etait le produit de 2 premiers alors pierre saurait repondre.

On peut aller plus loin, en disant que le produit ne peut pas être un nombre premier au cube.

donc serge est capable de montrer, a partir de S, que les 2 nombres (a et b) ne sont pas 2 premiers.
on sait donc que S /= p1 + p2 avec p1 et p2 premiers.
si p1 > 2 et p2 > 2 alors p1 + p2 est pair et parcourt tous les nombres pairs selon la conjecture de goldbach, idem pour p1 = p2 = 2, sinon p1 + p2 = 2 + p2 (impaire).
on peut donc dire que S est impaire avec (*) : S/= 2 + p , p premier.
on conclut que a est pair et b impair (ou inversement).

Jusque là, on est d'accord.

la parite de a permet d'ecrire en facteurs premiers : P = 2^k * p1 * p2 *...* pn avec k>=1 et n>=1 .
au vu de l'ecriture de P, n=1 car sinon pierre aurait plusieurs choix possibles.
on a donc P = 2^k * p1 , k>0
autrement dit : a=2^k , b= p1 premier.

C'est cohérent avec la solution, mais j'aurais tendance à dire qu'il faudrait être certain que tous les P de cette forme soient admissibles jusqu'à ce point pour que la démonstration soit rigoureuse.

la relation (*) nous donne 2^k + p1 /= 2 + p avec p premier
donc p - p1 /= 2^k + 2 , k>0 .

p - p1 /= 2^k - 2

ici, a l'aide d'un tableau excel par exemple, on peut dresser le tableau de la difference entre les premiers inferieurs a 100 et comparer au valeurs possibles de 2^k + 2 (2,6,14,30,62,...).
on constate que seuls 19 et 79 sont possibles pour p1.

Là je ne suis plus. Comment tu te retrouves avec seulement 19 et 79 ?

[matthias]

Pour info, avec mon programme, j'ai déterminé que le problème fonctionne si on prend des nombres compris entre 2 et N, avec N appartenant à [62;865].
Je me demandais, est-ce que vous voulez la solution donnée par le programme ? Ou la source du programme ?

[moijdikssékool]

je crois que la solution dépend uniquement des dires et répliques de Sierre et Perge
Il est possible qu'en effet il y ait plusieurs couples de solution (étant donné que les décompositions en élément simple ne peuvent inclure plus d'indéterminées que P ou S ne peuvent résoudre indépendemment l'un de l'autre, au fur et à mesure de leur discours)
Mais il n'y en aurait qu'un sur lequel P et S peuvent statuer de la manière dont leur discours le suggère

Je me demandais, est-ce que vous voulez la solution donnée par le programme ?

aboule

[matthias]

Il faut trouver 4 et 13

[moijdikssékool]

pour N = 100?

parceque 4+13 = 17 = 2+15
et 2*15=30, à partir de 30 tout comme avec 4*13=52, Pierre aurait pu dire

Je ne peux pas déterminer ces nombres avec leur seul produit

cependant, 17 ne peut résulter de la somme de 2 nombres premiers

[matthias]

c'est la même solution quel que soit N dans l'intervalle où le problème est soluble.
Et si tu prends juste la première réplique de Pierre, il reste beaucoup, beaucoup de nombres possibles ....

[invite0dacff7f]

Je me posais une question!

pour N = 100?

parceque 4+13 = 17 = 2+15
et 2*15=30, à partir de 30 tout comme avec 4*13=52, Pierre aurait pu dire


cependant, 17 ne peut résulter de la somme de 2 nombres premiers

Je vois très bien ton raisonnement.

Piere recoit : 52
- Je ne peux pas déterminer ces nombres avec leur seul produit, annonce Pierre.
52=4*13=2*26
S=17 ou 28.
- Je le savais, dit Serge.
or S=impair
- Ah, bon ? Alors, je les connais, dit Pierre.
S=17, P=52 or a=4, b=13
- Dans ce cas, moi aussi, rétorque Serge.
On doit refaire le cheminement inverse
S=17, P=2*15, 3*14, 4*13, 5*12, 6*11, 7*10, 8*9.
P=30,42,52,60,66,70,72!
Si pierre les connais, seulement 52 est possible. Je suis d'accord.


Reprenons avec 76=19*4

Piere recoit : 76
- Je ne peux pas déterminer ces nombres avec leur seul produit, annonce Pierre.
P=76=4*19=2*38
S=23 ou 40.
- Je le savais, dit Serge.
or S=impair
- Ah, bon ? Alors, je les connais, dit Pierre.
S=23, P=76 or a=4, b=19
- Dans ce cas, moi aussi, rétorque Serge.
On doit refaire le cheminement inverse
S=17, P=2*21, 3*20, 4*19, 5*18, 6*17, 7*16, 8*15, 9*14, 10*13, 11*12.
P=42,60,76,90,102,120,126,130, 132.
Pour que pierre les connaissent, seul 76 est possible.

Existerait-il plusieurs solutions??? Non impossible!! c'est tout simplement nous ne sommes pas tombé sur la réponse finale! Je dois toutefois admettre que j'ai de la difficulté à saisir l'expression "leur seul produit" je ne fais pas de différence avec "seul leur produit".

Laissons le débat continuer en espérant trouver une solution unique. J'ai une question par rapport au programme aussi. S'il s'agit d'un compteur à partir du quel on impose les conditions, c'est évident que le programme s'arrêtera à la premiere solution. Est-ce le cas?

[moijdikssékool]

- Je le savais, dit Serge

pi la Pomme est saire, ca ne srouve rien. Plupieurp répultat soppiblep: 2 nombrep imsairp décomsopablep, 2 nombrep sairp décomsopablep, 2 nombrep sremierp ou 2 nombrep dont un imsair décomsopable et un sremier
pi la Pomme est imsaire, il y a le cap 2+s où s sremier. S imsaire seut donc être la pomme de 2 nombrep sremierp. Or, panp que Sierre le dipe, Perge pait que Sierre ne souvait trouver une décomsopition, c'est à dire qu'il ept sûr que le Sroduit n'ept sap décomsopable en 2 nombrep sremierp. A fortiori, la pomme ept slup grande que 102

a slup!

[invite0dacff7f]

Je me posais une question!

J'ai une question par rapport au programme aussi. S'il s'agit d'un compteur à partir du quel on impose les conditions, c'est évident que le programme s'arrêtera à la premiere solution. Est-ce le cas?

J'ai trouvé ma réponse. Non ce n'est pas fait à partir d'un compteur car pour P=20 on a:

Je ne peux pas déterminer ces nombres avec leur seul produit, annonce Pierre.
P=20=2*2*5,
S=9 ou 12.
- Je le savais, dit Serge.
or S=impair
- Ah, bon ? Alors, je les connais, dit Pierre.
S=9, P=20 or a=5, b=4
- Dans ce cas, moi aussi, rétorque Serge.
On doit refaire le cheminement inverse
S=9, P=4*5,3*6,2*7.
P=14,18 ou 20
Puisque dans les cas de 14 et 18 pierre aurait conclu dès le départ or, a=5,b=4!

Je suis de plus en plus sceptique sur l'unicité de la solution de cette énigme! Bref je vous laisse continuer, j'ai faite ma part!

[Bobby]

Serge déclare que Pierre ne pouvait pas devnier à partir du produit, ça veut dire que la somme S qu'on lui a donnée ne peut pas être décomposée en somme de nombres premiers.

Le couple (4;5) n'est pas solution du problème, la somme serait alors 9 décomposable en 2+7 ou 3+6.

Les produits correspondant auraient alors été 14 ou 18.
Si ça avait été 14 Serge aurait pu directement déduire la solution, mais ce n'est pas le cas. La somme ne peut donc être 9.

[matthias]

Je dois toutefois admettre que j'ai de la difficulté à saisir l'expression "leur seul produit" je ne fais pas de différence avec "seul leur produit".

Pas de différence en effet.

J'ai une question par rapport au programme aussi. S'il s'agit d'un compteur à partir du quel on impose les conditions, c'est évident que le programme s'arrêtera à la premiere solution. Est-ce le cas?

Non évidemment. Le programme fonctionne de manière totalement bourrine, ce qui le rend relativement simple. Il s'agit de partir d'un tableau de tous les couples possibles, puis d'éléminer au fur et à mesure tous ceux qui ne correspondent pas avec les déclarations. Et heureusement à la fin il n'en reste qu'un.

Je suis de plus en plus sceptique sur l'unicité de la solution de cette énigme!

Si vous voulez je poste les sources du programme (en C). Je ne pense pas qu'il y ait d'erreur, mais on sait jamais.