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 ?

[cricri]

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) ...

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.

[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 ...

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.

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

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

Excellent site soit dit au passage.

[robert et ses amis]

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

Citation:

- 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.

Citation:

- 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 .

Citation:

- 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...

[robert et ses amis]

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

[Joe Hell]

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

[robert et ses amis]

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

[moijdikssékool]

Citation:

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

Citation:

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

[robert et ses amis]

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.