petite énigme sympa

[invitec314d025]

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

[invitec314d025]

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]

[invitec314d025]

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 ?

[invitec314d025]

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!

[invitec314d025]

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

[invitec314d025]

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 ?

[invitec314d025]

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

[invitec314d025]

Il faut trouver 4 et 13