Énigme énigmatique

Boécien

Alice connaît le produit des âges de deux personnes (entre 2 et 100 ans) et Bob connaît leur somme. 

Alice : Je ne connais pas leur âge respectif.

Bob : Je savais que tu ne le connaissais pas.

Alice : Maintenant je le connais.

Bob : Alors moi aussi.

Quel est l'âge respectif des deux personnes ?

Je suppose que ce problème est déjà apparu sur ce site... J'ai vu des solutions mais aucune se fait "à la main". Il faut à chaque fois écrire un programme.

Peut on trouver la solution sans aide de l'ordinateur? Cela me parait difficile car le dialogue amène à considérer 4 sous-ensembles emboités de E={(x,y),2<=x,y<=2100} et à arriver à un sous-ensemble qui miraculeusement contient un seul élément que l'on trouve... grâce à un programme.

PetitLutinMalicieux

Bonjour,
déjà, merci. Je ne connaissais pas.

Ensuite, prenons un exemple. Si la somme fait 11 et le produit 18. Alice ne sait pas car 18=2*9=3*6. Mais quand la somme vaut 11, aucune des possibilités ne donne un produit évident. Donc Bob sait que Alice va patauger. Du coup, Alice sait que la somme fait 11, sinon, avec une somme de 9, il y aurait eu 2 et 7 car 2+7=9 et 2*7=14, ce qui n'aurait pas été un problème pour Alice. Elle conclut 2*9=18. Mais Bob ne conclut rien du tout. Car, 24 aurait marché aussi, avec le même raisonnement. 24=6*4=2*12=3*8. Mais 6+4=10 est bloqué par 7+3=10 car 3*7=21 unique. Et 2+12=14 est bloqué par 11+3=14 car 3*11=33 unique. Comment Bob tranche-t-il entre 18 et 24 ? Ai-je loupé un élément de l'énoncé ?

JLapin

Ca veut juste dire que la bonne combinaison n'est pas $11/18$, non ?

PetitLutinMalicieux

(11,18) et (11,24) fonctionnent avec les exclamations d'Alice, ce qui empêche Bob de conclure avec son 11. Tu vas me dire "Donc il n'a pas 11". Mais Alice peut avoir 18 ou 24, et le comportement décrit dans l'énoncé. Et Bob reste coi.

Boécien

Je ne pense pas qu'on puisse partir d'un exemple car il semble bien que la solution (x,y) est unique à l'ordre près.

JLapin

Puisque Bob ne sait pas conclure dans un cas comme dans l'autre, c'est que la solution n'est pas $(11,18)$ ni $(11,24)$.

Ou alors, je n'ai pas compris ce que tu essayes d'expliquer pour dire que le problème est foireux.

jm14d

Je pense que le produit P doit être exprimable sous exactement 2 formes différentes de produits d'entiers (exemple : 12 = 2*6 = 3*4). En effet, s'il s'exprimait sous une seule forme, Alice aurait la réponse directement, et s'il s'exprimait sous 3 formes ou plus, elle n'aurait pas la réponse même après la phrase de Bob.

Si on décompose en facteurs premiers, ça veut dire que P = (a^2) * b   (a et b premiers). En effet :

• a * b ne donne qu'une forme P = a * b
  
• a * b * c donne 3 formes : P = (a*b) * c = a * (b * c) = (a * c) * b
• a^2 * b donne bien 2 formes : P = (a * a) * b = (a * b) * a

Donc déjà on pourrait énumérer les produits candidats :

(2^2) * 3, (2^2) * 5, (2^2) * 7, ... (2^2) * 23

(3^2) * 2, (3^2) * 5, (3^2) * 7, ... (3^2) * 11

(5^2) * 2, (5^2) * 3  

(7^2) * 2... et c'est tout. Il n'y en a pas tant que ça

Bon je vais essayer de faire pareil pour l'étape 2... ça vous semble correct ?

PetitLutinMalicieux

C'est bon, j'ai compris. L'espace des produits d'Alice est restreint par la somme de Bob. S'il a 17, Alice n'a ni 18, ni 24. Donc pas de polémique.

lourrran

Notons a et b les âges des 2 personnes. 
On sait que a et b sont compris entre 2 et 100. Donc en particulier, ils sont différents de 1.
Alice connait le produit ab.
Elle nous dit qu'elle ne connaît pas les 2 valeurs a et b. 
Donc on en déduit que a et b ne sont pas tous les 2 premiers. 
Bob dit : je savais que tu ne savais pas.
Cette information est 'énorme'.
Si par exemple le nombre communiqué à Bob avait été de la forme p+q avec p et q premiers, Bob n'aurait pas dit ça.
Alice apprend donc à ce moment là que le nombre communiqué à Bob n'est pas de la forme p+q

A suivre.

JLT

Soient $s$ la somme et $p$ le produit. Alors on peut dire que $p$ n'est pas un produit de deux nombres premiers, puis que $s$ est impair (sinon $s$ serait la somme de deux nombres premiers...), puis que $s-2$ n'est pas premier. Mais ça ne réduit pas beaucoup le nombre de cas à vérifier.

jm14d

Il restait 15 produits "candidats", chacun étant obtenu d'exactement 2 manières, ça nous fait 30 paires {a, b} possibles. Je les passe au crible de la remarque de Lourran : la somme ne peut pas avoir une décomposition en somme de 2 nombres premiers. C'est parti (je suis mon petit tableau ligne par ligne) :

ligne 1
4*3 = 12, S = 7 = 2 + 5 -> out
2*6 = 12, S = 8 = 3 + 5 -> out
4*5 = 20, S = 9 = 2 + 7 -> out
2*10 = 20, S = 12 = 5 + 7 -> out
4*7 = 28, S = 11 -> POSSIBLE
2*14 = 28, S = 16 = 11 + 5 -> out
4*3 = 12, S = 7 = 2 + 5 -> out
4*11 = 44, S = 15 = 13 + 2 -> out
2*22 = 44, S = 24 = 19 + 5 -> out
4*13 = 52, S = 17 -> POSSIBLE
2*26 = 52, S = 28 = 23 + 5 -> out
4*17 = 68, S = 21 = 19 + 2 -> out
2*34 = 68, S = 36 = 31 + 5 -> out
4*19 = 76, S = 23 -> POSSIBLE
2*38 = 76, S = 40 = 37 + 3 -> out
4*23 = 92, S = 25 = 23 +2 -> out
2*46 = 92, S = 48 = 43 + 5 -> out

ligne 2
9*2 = 18, S = 11 -> POSSIBLE
3*6 = 18, S = 9 déjà vu comme out
9*5 = 45, S =14 = 11 + 3 -> out
3*15 = 45, S = 18 = 13 + 5 -> out
9*7 = 63, S = 16 déjà vu comme out
3*21 = 63, S = 24 = 19 + 5 -> out
9*11 = 99, S = 20 = 17 + 3 -> out

ligne 3
25*2 = 50, S = 27 -> POSSIBLE
5*10 = 50, S = 15 = 13 + 2 -> out
25*3 = 75, S = 28 = 23 + 5 -> out
5*15 = 75, S = 20 déjà vu comme out

ligne 4
49*2 = 98, S = 51 -> POSSIBLE
7*14 = 98, S = 21 déjà vu comme out

Bref à ce stade et sauf erreur, les paires possibles sont : {4, 7} {4, 13} {4,19} {2, 9} {2, 25] et {2, 49}   soit 6 paires candidates.

Est-ce qu'il y aurait un critère pour continuer à en éliminer ?

Boécien

En tout cas jm14d, la paire gagnante s'y trouve.  C'est presque possible donc.

Namiswan

(4,13) me semble un bon candidat.

samok

Tiens, tiens, la vérité dépendrait du temps !?
Super cet énoncé pour éviter de se confondre et réciproquement. Il date d'au moins avant 1995.

Soc

Il faut éliminer ceux dont la somme correspond à plusieurs candidats restants.

Par exemple (4,7) n'est pas possible, car une fois qu'elle dit qu'elle a trouvé, lui ne sait pas si cela correspond à (2,9) ou à (4,7).

Il reste donc encore ... 4 paires!

Robomo

Petite question @jm14d , pourquoi ne pas avoir considéré (2^2)*29 par exemple ?

jm14d

hello, parce que c'est supérieur à 100 et l'énoncé limite à 100

jm14d

Bien joué Soc !

Soc

En revenant un peu en arrière, je ne suis pas convaincu sur le fait que le produit ne doit être décomposable que de 2 façons. La condition me semble plutôt que parmi toutes les décompositions en produit une seule permette à BOB de savoir qu'elle ne pouvait pas trouver:

Indice 1: Ce n'est pas une paire de nombre de premiers.
Indice 2: S ne peut pas se décomposer en somme de 2 nombres premiers.
Indice 3: Parmi les décompositions possibles de P en produit, Une seule a une somme qui peut ne peut pas se décomposer en somme de 2 nombres premiers.

Indice 2: Il y a au moins un 2 dans P sinon toutes les sommes sont paires.

Robomo

jm14d a dit :

hello, parce que c'est supérieur à 100 et l'énoncé limite à 100

Ah tu l'as compris comme ça. Je pensais que chaque personne avait un âge compris entre 2 et 100 ans, pas que le produit était compris entre 2 et 100.

Soc

Je pense que c'est l'âge respectif, sinon le produit serait dit "compris entre 2 et 100 ans² "

Robomo

C'est aussi ce que je pensais mais du coup on est d'accord qu'il faut vérifier jusqu'à (2^2)*97 ? Et du coup ça rajoute pas mal de possibilités même si ça élimine tous ceux qui ne sont pas de la forme (2^2)*p.

jm14d

oui, mince, tu as raison !!

Soc

Je persiste à ne pas être convaincu sur la démonstration de la décomposition du produit en seulement 2 cas. Je précise:
* On peut établir la liste des sommes possibles selon l'indice 2, on y a donc tous les nombres s pairs tels que s-2 ne soit pas premier: 11, 17, 23, 27 etc...

* Si le produit se décompose de plusieurs façons telles que les sommes vaillent 8, 9 et 11 alors elle pourra trancher et dire que le seul cas possible est celui dont la somme vaut 11.

Malheureusement cela augmente beaucoup le nombre de cas à traiter, sauf si l'on parvient à reformuler cette contrainte pour mieux identifier les cas éliminés/restants.

Soc

J'ai trouvé ailleurs le cardinal des solutions après chaque indice (trouvé informatiquement) et après l'indice 3 il reste encore 89 candidats. Cela restreint l'espoir de trouver une solution à la main...

Boécien

Effectivement.

lourrran

J'avais un vague souvenir d'une énigme comme celle-ci, mais qui pouvait se résoudre manuellement.
Peut-être que la limite max n'était pas de 100, mais plus basse.
J'ai programmé ça (en m'inspirant fortement du lien donné par Soc), et j'ai joué un peu.

Même si on remplace la limite 100 par 500, il y a toujours une seule solution. Et j'imagine que ça reste vrai pour des valeurs plus grandes.

Alain24

@Boécien  Cela me rappelle une histoire vieille comme le monde de gros dindon parlant très savant. Le gros dindon savant a une boîte sur son dos, il croise Bob qui est chercheur de fractales et lui dit : "Comme il est possible de calculer tous les mouvements des particules de l'Univers, j'ai prévu que je te rencontrerai et prévoirai tes réactions et tes émotions et dans cette boîte, il y a Alice ou un dindon, dis-moi ce qu'il y a dans la boîte que je pose ici avant de partir, si je me suis trompé tu auras ce que tu auras son contenu, sinon tu n'auras rien"

Alors Bob dit "Il y a Alice et un gros dindon savant et parlant"

Boécien

Merci @lourrran c'est intéressant. Peux tu sortir un tableau donnant les cardinaux en fonction de n (l'âge maximum)  (disons pour n=100,200,300,400,500)?

jm14d

Soc a dit :

<...> Cela restreint l'espoir de trouver une solution à la main...

Gloups !  en effet...

Namiswan

Boécien a dit :

Merci @lourrran c'est intéressant. Peux tu sortir un tableau donnant les cardinaux en fonction de n (l'âge maximum)  (disons pour n=100,200,300,400,500)?

Je ne crois pas que ce soit le meilleur programme à faire pour comprendre le phénomène arithmétique. Mais peut-on me confirmer avant tout que (4,13) est la solution, pour vérifier que je n'ai pas compris de travers et que je n'ai pas fait d'erreur de calcul (je n'ai fait que de tête).

jm14d

Soc a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2422107/#Comment_2422107

En revenant un peu en arrière, je ne suis pas convaincu sur le fait que le produit ne doit être décomposable que de 2 façons. La condition me semble plutôt que parmi toutes les décompositions en produit une seule permette à BOB de savoir qu'elle ne pouvait pas trouver:

Indice 1: Ce n'est pas une paire de nombre de premiers.
Indice 2: S ne peut pas se décomposer en somme de 2 nombres premiers.
Indice 3: Parmi les décompositions possibles de P en produit, Une seule a une somme qui peut ne peut pas se décomposer en somme de 2 nombres premiers.

Indice 2: Il y a au moins un 2 dans P sinon toutes les sommes sont paires.

Soc je suis d'accord avec ta première remarque (autant pour moi).

Avec tes indices 1 et 2 également.

Dans l'indice 3 pourrais-tu clarifier "qui peut ne peut pas" ?  

Et dans le dernier indice, comment tu établis "sinon toutes les sommes sont paires" ?

Alain24

@Boécien Si Bob et Alice ne parlent pas de leur age il me semble qu'il y a plusieurs solutions.

Soc

Indice 3: Elle peut trouver la réponse.
Son produit correspond à plusieurs décompositions possibles (indice 1). (par exemple  P=24 correspond à 2/12 ou 4/6 ou 8/3)
Chacune de ses décompositions correspond à une somme donnée. (ici S=14 ou S=12 ou S=11)

Indice 2: Parmi toute ces sommes, une seule permettait à bob d'être sûr qu'elle ne pouvait pas trouver.

Cette somme ne doit donc pas être décomposable en somme de 2 nombres premiers (par exemple cette somme ne peut pas être égale à 14 car 14=11+3 et dans ce cas il n'aurait pas pu être sûr qu'elle ne trouverait pas, idem pour S=12 = 5+7).

Pour le 2 dans les facteurs, s'il n'y a pas de 2 alors les deux nombres sont impairs, donc la somme est paire, donc elle est décomposable en somme de 2 premiers), donc Bob ne peut pas être sûr qu'elle ne trouverait pas.

Soc

Namiswan a dit :

Mais peut-on me confirmer avant tout que (4,13) est la solution, pour vérifier que je n'ai pas compris de travers et que je n'ai pas fait d'erreur de calcul (je n'ai fait que de tête).

Si le programme fait bien ce qu'il est sensé faire, alors (4;13) est bien la solution. Il est possible de tête de comprendre que (4;13) est bien une solution, en revanche démontrer de tête que c'est bien la solution sans recours à l'informatique n'a a priori pas encore été réussi.

PetitLutinMalicieux

De tête ??? Tu as pensé que 115=23*5 disqualifiait 28, et que 30, 42, 60, 66, 70 et 72 se trouvaient dans une autre somme que 17 ? T'es trop fort. Moi, rien que pour factoriser 322, j'ai eu un temps d'arrêt.

nicolas.patrois

322=161×2=(140+21)×2…

jm14d

Limpide !!   merci Soc.

Namiswan

PetitLutinMalicieux a dit :

De tête ??? Tu as pensé que 115=23*5 disqualifiait 28, et que 30, 42, 60, 66, 70 et 72 se trouvaient dans une autre somme que 17 ? T'es trop fort. Moi, rien que pour factoriser 322, j'ai eu un temps d'arrêt.

Pas sûr de quoi tu parles, mais ce que j'ai fait n'ai pas si difficile ; j'ai vérifié que pour toute décomposition $17=a+b$ autre que $\{a,b\}=\{4,13\}$, Alice ne peut pas à partir de $p=ab$ déduire $a$ et $b$ à partir la première déclaration de Bob (je donnerai des détails quand j'aurai un peu plus de temps, bien que je n'apporte peut-être rien de plus que ce qui a déjà été dit). Après je suis d'accord avec Soc sur le fait qu'il reste à vérifier qu'aucun autre couple peut marcher. Et je suis d'accord avec Lourrran avec le fait que l'hypothèse $\leq 100$ est peut-être arbitraire, voire inutile. Mais je pense que prouver ce dernier point ferait appel à de l'arithmétique beaucoup trop compliquée à l'heure actuelle.

lourrran

Mauvaise nouvelle pour nous Namiswan, la conjecture est fausse. 
Si on remplace 100 par de plus grandes valeurs, il vient un moment où on a 2 solutions.

Voici en PJ le tableau demandé par Boécien.

Boécien

Merci lourrran. Cela suggère que $\left|E_{i}(n)\right|=\lambda_{i}n^{2}+o(n^{2})$ pour $i=0,1,2,3$ avec trivialement $\lambda_{0}=\frac{1}{2}$ puisque $\left|E_{0}(n)\right|=\frac{n^{2}-n}{2}$.

On peut alors imaginer que pour $\left|E_{4}(n)\right|$ le comportement est différent et qu'il existe une fonction $f$ telle que $\left|E_{4}(n)\right|\leq f(n)$. Si on pouvait trouver une telle fonction vérifiant $f(100)<2$ alors on aurait nécessairement $\left|E_{4}(100)\right|=1$ ou $0$. Il suffirait alors ensuite de trouver une solution pour $n$ petit pour s'assurer qu'il existe une solution unique.

La question est donc peut-on trouver une fonction $f$ intéressante avec les indices de l'énigme ?

Soc

@Lourrran Te serait-il possible de faire la liste des 86 éléments de E3, de préférence décomposés en produits de facteurs premiers? Histoire de voir si on  retrouve quelque particularité qui nous aurait échappée?

lourrran

@Soc, 
je pense que la réponse à nos interrogations se trouve là : Problème de Freudenthal

Ca me paraît une source sérieuse, et s'il y avait une astuce pour réduire cette recherche, sans passer par ces listes de 86 valeurs voire plus, elle serait donnée ici.

A suivre, peut-être ce soir, mais pas sûr.

Edit : Attention, dans le lien la contrainte $a \le 100$ et $b \le 100$ est remplacée par $a+b \le 100$ voire $a+b \le M$

@Boecien : Dans le lien que j'ai donné, les paragraphes suivants (Attention aux modifications de l'énoncé  et  toujours plus fort ) abordent ce que ça donne quand on change les bornes. 


Nouvel Edit : 
Je lis au fur et à mesure, 
L'énigme 'Une journée de réflexion' toujours sur le même lien paraît complètement dingue !

Boécien

Merci lourrran pour ce lien vers cet excellent article de Jean-Paul Delahaye. L'extension des bornes engendre une conjecture non résolue!

PetitLutinMalicieux

Étonnant. Ce qu'exprime ce problème, c'est qu'il n'y a qu'une seule parabole ayant des intersections avec les axes sur les intersections du quadrillage (espacement de 1). Les âges a1 et a2 sont les solutions de l'équation : 

$x^2-(a_1+a_2)x+a_1a_2=0$

Pourtant, a priori, on penserait plutôt que (0,P) peut être n'importe où, et (S,0) aussi.

Robomo

L'énigme "Une journée de réflexion" est franchement sympa à faire. Je viens de la faire avec un tableur en éliminant les possibilités au fur et à mesure et on obtient bien une seule solution à la fin.

kioups

Merci Boécien pour l'énigme et lourrran pour le lien !

lourrran

J'ai adapté mon petit programme pour reproduire la règle du lien de ce matin (borne supérieure du type $a+b \le M$ et non $a \le M$ et $b \le M$)
Dans beaucoup de cas, les tailles des tableaux intermédiaires sont inchangées par rapport au 1er traitement, mais ça doit pouvoir s'expliquer assez bien. 
Pour M=900, 950 ou 1000, la 2ème solution est (4,61), et ça m'interpelle. Pourquoi ce couple de 'toutes petites' valeurs apparaît seulement quand on traite M=900 ?

Soc

Dans le même ordre d'idée il y a aussi 16/73 et 64/73 et 67/82 qui apparaissent aussi dans l'enigme "toujours plus fort" qui me semblent en contradiction avec la solution unique. du cas des deux valeurs inférieures à 100...