La seconde inconnue ...

freddy · 08-04-2009 19:29:39

Voici un joli sujet qui m'avait été donné à résoudre par un jeune et brillant ingénieur débutant dans notre société en 2001. Curieusement, il n'était pas amateur de la résolution d'énigme, et m'avait demandé de bien vouloir l'aider dans celle que lui avait transmise un camarade de promotion qui était parti "chercher fortune" en Australie.

C'est un joli sujet à résoudre (on y aura passé quelques heures sympa), et j'ai fini par trouver sur la Toile des formes de plus en plus compliqués de la version que je vais exposer.

Je vous suggère de chercher la réponse (qui existe et est unique) par vos propres moyens intellectuels, le jeu étant plus de trouver la démarche de résolution que de communiquer la réponse connue par ailleurs.

Voici : on donne à Sophie et à Patricia respectivement la somme et le produit de deux nombres entiers tirés au hasard dans un intervalle compris entre 2 et 100.

Chacune doit donner la valeur des deux nombres tirés au sort.

On entend cet étrange dialogue.

Patricia dit qu'elle ne peut pas répondre.

Sophie répond :" j'étais prête à parier que tu dirais cela".

Quelques secondes plus tard, Patricia dit : " Comme c'est amusant, je viens de trouver" ;

et Sophie de conclure : "c'est amusant, parce que moi aussi".

Bien entendu, Sophie et Patricia sortent de Yale (Ph. D en informatique et mathématique) et ont dans leur cerveau deux puissants Cray quadruple coeur.

Avec ce jeune ingénieur, on dira qu'on a mis quelques heures à trouver (disséminées sur 3 mois de travail sur d'autres sujets plus prioritaires).

Un ami qui goûtait fort ce genre de sujet y passa un petit WE (surtout pour trouver le bon code sous SAS). C'est d'ailleurs grâce à ce code qu'on a établi que la solution était unique pour tout tirage de deux nombres compris entre 2 et 400. Au delà, le nombre de solution augmente. Mais on n'a pas encore trouvé le temps de trouver les liens entre elles en fonction de la borne sup. retenue ...

Bonne chance,

freddy

Dernière modification par freddy (11-04-2009 18:36:55)

Fred · 08-04-2009 22:26:13

Bonsoir,

La première fois que j'ai lu cette énigme, c'était au début des années 90 dans feu la revue "Jeux et stratégie".
Quelqu'un connait son origine?
C'est vrai que c'est "assez" facile à résoudre avec un petit programme, mais à la main, pffffff....il y a tant de cas à envisager.
Il me semble que dans le "corrigé" de la revue, ils faisaient qqch d'assez détaillé.

Fred.

freddy · 09-04-2009 01:01:54

Je me souviens avoir émis une conjecture à partir de la première phrase de Patricia qui se révéla très fructueuse. Le pb fut de s'assurer qu'il n'y avait pas d'autre solution.

SébastienB · 11-04-2009 09:42:31

Bonjour,

Je n'ai jamais vu cette énigme mais en faisant abstraction des commentaires, je ferai comme ceci pour trouver [tex]\text{deux entiers} \ x \ \text{et} \ y \ \text{dont la somme} \ S \ \text{et le produit} \ P \ \text{sont connus}[/tex] :

[tex]x + y = S \ \text{et} \ x \times y = P[/tex]

[tex]\begin{align}(x+y)^2 - (x-y)^2 &= 4xy \\ (S)^2 - (x-y)^2 &= 4P \\ (x-y)^2 &= S^2 - 4P \\ x-y &= \sqrt{(S^2 - 4P)}\end{align}[/tex]

On obtient ensuite donc un système d'équation à deux inconnues que l'on pourra résoudre au choix par substitution ou alors par combinaison linéaire :

[tex]\begin{cases}x+y &= S\\x-y &= \sqrt{(S^2 - 4P)}\end{cases}[/tex]

[tex]\begin{align}2x &= S+\sqrt{(S^2 - 4P)}\\x &= \frac{S+\sqrt{(S^2 - 4P)}}{2}\\y &= S - \frac{(S+\sqrt{(S^2 - 4P)})}{2}\end{align}[/tex]

Connaissant [tex]4 \le S \le 200 \ \text{et} \ 4 \le P \le 10000[/tex], il est probable que ça demande des calculs avec des grands nombres qui prendraient probablement plus de quelques secondes...

Ps : Cette équation [tex](x+y)^2 - (x-y)^2 = 4xy[/tex] aussi connue des Grecs que j'ai trouvé sur Internet
ressemble à l'identité de Diophante mais ce n'est pas tout a fait pareil. Est ce que vous la connaissez aussi ?
@+

Dernière modification par SébastienB (12-04-2009 16:50:15)

freddy · 11-04-2009 11:44:08

Salut SébastienB,

joli travail, mais vous voyez bien qu'on ne peut trouver par simple déduction. Il faut donc interpréter la conversation entre Sophie et Patricia.

Patricia dit qu'elle ne peut pas trouver => le produit n'est pas factorisable en deux nombre premiers seulement.

Sophie dit qu'elle aurait parier que Patricia ne pouvait le faire => la somme est impaire (cf. conjecture de Golbach)

Je vous laisse continuer.

Bon courage et @+

Barbichu · 11-04-2009 15:51:32

Salut,

Connaissant S et P, les deux nombres à retrouver se calculent facilement comme solutions de l'équation x²-Sx+P = 0

Mais là n'est pas le problème (mis à part qu'à S et P fixé, on sait que la solution est unique à permutation près), car nous ne connaissons ni P ni S...
Le problème est de se rendre compte que chacune de leur phrase communique en fait une information sur l'unicité du problème qu'ils rencontrent :

* Lorsque Patricia dit qu'elle ne peut pas répondre, il faut comprendre qu'en connaissant son propre nombre P (le produit), elle n'a pas de solution unique, il existe donc plusieurs couples (x,y) différents (à permutation près) tels que P=x*y. (Rq : c'est plus fort que juste "ne pas être le produit de deux nombres premiers" : par exemple, P=2*3*99 ne mène qu'à une solution qui est (6,99))

De plus, Sophie aurait pu le parier, ce qui veut dire que, quelque soit la façon de décomposer la somme S=x+y en a+b, on ne peut pas retrouver de manière unique a et b à partir de a*b.
On ne garde donc que l'ensemble E1 des couples (x,y) (x<=y), tels que pour tout a et b tels que a+b=x+y et a<=b, il existe (c,d) avec c<=d tel que a*b = c*d sans que a=c et b=d.

* Puisque Sophie ne peut pas trouver, on ne garde que l'ensemble E2 des couples (x,y) de E1, tels qu'il existe (z,t) dans E1 tel que (z,t) != (x,y) et z+t=x+y.

* Lorsque Patricia anonce qu'elle a trouvé, cela signifie qu'il existe un unique élément (x,y) de E2 tel que P=x*y. Soit E3 l'ensemble des éléments (x,y) de E2 verifiant la propriété : pour tout (z,t) dans E2, si z*t=x*y alors (x,y) = (z,t)

* Lorsqie Sophie annonce qu'elle a trouvé, cela signifie qu'il existe un unique élément (x,y) de E3 tel que S=x+y. Soit F l'ensemble des éléments (x,y) de F verifiant la propriété : pour tout (z,t) dans F, si z+t=x+y alors (x,y) = (z,t)

Miracle, F ne contient que le couple (4,13), la solution existe et est unique.

----------------------------------------------------

Vérifions à la main que c'est bien une solution :
Patricia a 52 et Sophie 17.

Patricia hésite entre {2,26} et {4,13} => Elle ne sait pas

Sophia hésite entre {2,15} {3,14} {4,13} {5,12} {6,11} {7,10} {8,9}
Donc elle sait que Patricia a 30 ou 42 ou 52 ou 66 ou 70 ou 72.
Et elle voit alors que Patricia ne peut pas déterminer.
(30 = 2*15 ou 6*5, 42 = 3*14 ou 6*7, etc ...)
De plus elle non plus ne peut pas le déterminer

Patricia voir que si c'était {2,26} la solution, Sophia aurait 28, et envisagerait {5,23} comme solution, or P=5*23 mènerait directement à {5,23} comme solution et donc Sophia n'aurait jamais pu parier qu'elle ne pourrait pas trouver.
Donc Patricia sait que la solution est {4,13}, et répond qu'elle peut déterminer

Enfin, Sophia envisage toutes les solutions possibles :
* Patricia a 30 => elle ne peut pas deviner une valeur que Sophia sait correcte.
* Patricia a 42 => elle ne peut pas deviner ...
* Patricia a 52 => elle peut trouver que c'est {4,13} !!!!!
* Patricia a 66 => elle ne peut pas deviner ...
* Patricia a 70 => elle ne peut pas deviner ...
* Patricia a 72 => elle ne peut pas deviner ...

Et elle aboutit au fait que 52 est la seule valeur à partir de laquelle Patricia aurait pu trouver.
Donc {4,13} est la seule solution pour Patricia et Sophia

(Quand à nous, nous avions déjà constaté que c'était vrai, et aussi que c'était la seule paire qui convenait !)
----------------------------------
Problème très amusant. Et ça marche effectivement pour 400 au lieu de 100.

++

Dernière modification par Barbichu (11-04-2009 15:55:23)

SébastienB · 11-04-2009 17:38:26

Pigé!
C'est très amusant je suis d'accord, et c'est facile en fait quand on peut éliminer un couple de solution sur deux possible.
J'aimerai bien voir la démonstration avec 196 et 28 par exemple pour voir si pour moi c'est pareil.

Merci =-)

Dernière modification par SébastienB (12-04-2009 16:51:00)

freddy · 11-04-2009 18:34:48

Merci Barbichu,

Je n'aurais pas su mieux expliquer que toi.

Have fun

Forum de mathématiques - Bibm@th.net

#1 08-04-2009 19:29:39

La seconde inconnue ...

#2 08-04-2009 22:26:13

Re : La seconde inconnue ...

#3 09-04-2009 01:01:54

Re : La seconde inconnue ...

#4 11-04-2009 09:42:31

Re : La seconde inconnue ...

#5 11-04-2009 11:44:08

Re : La seconde inconnue ...

#6 11-04-2009 15:51:32

Re : La seconde inconnue ...

#7 11-04-2009 17:38:26

Re : La seconde inconnue ...

#8 11-04-2009 18:34:48

Re : La seconde inconnue ...

Pied de page des forums