Két matematikus?

#1:

Ott van a feladat: a két számot kell kitalálni.

Legyen a két gondolt szám x és y. Hogy 1 és 100 közötti, azt hogyan kell érteni? Hogy x és y 101-nél kisebb pozitív számok, vagy 1 < x, y < 100?

Az általánosság rovása nélkül feltehetjük, hogy y legalább akkora, mint x.

Az előbbi esetben:

A tudja x*y-t, B tudja x + y.

A nem tudja a két számot x*y alapján, tehát x*y felbontása nem egyértelmű 2 szám szorzatára, tehát x*y NEM PRÍM és nem 1. (Illetve az a fontos, hogy A nem tudja a két számot x*y alapján AKKOR ÉS CSAK AKKOR, HA x*y nem prím és nem 1.) Ez akkor és csak akkor van így, ha x nem 1 és y nem prím (vagy 1).

B nem tudja a két számot x + y alapján, tehát x + y nem egyértelműen bomlik két szám összegére, így x + y LEGALÁBB 4. (Ez is oda-vissza igaz.)

B az összeg alapján tudja, hogy A nem tudja, tehát, hogy x*y nem prím, azaz hogy x nem 1 és y sem prím (vagy 1), ez akkor és csak akkor lehet, ha x + y – 1 nem prím vagy 1. (Ugye ha x + y – 1 prím lenne, akkor x lehetne 1 és y is lehetne prím.)

Ezek alapján A tudja, tehát az x*y-t, amit ismer, pontosan egyféleképpen tudja két szám szorzatára bontani úgy, hogy a két tényező összege mínusz 1 ne legyen prím.

x*y legkisebb lehetséges értékei 4, 6, 8, 9,… Kezdjünk próbálgatni:

4, ez vagy 1*4, 1 + 4 – 1 = 4 nem prím, vagy 2*2, 2 + 2 – 1 = 3 prím, tehát 4 lehet a szorzat, az összeg lehet 5, és akkor x = 1 és y = 4.

6, x + y – 1 az 6 vagy 4 lesz, mindkettő nem prím, tehát ez nem jó.

8, 1 + 8 – 1 = 8 vagy 2 + 4 – 1 = 5, ez is ugyanúgy jó, mint a 4 volt.

A 9 is jó lesz…

Szóval valami el van rontva.

Szerencsés esetben az, hogy valójában 1 < x, y < 100.

Átlagos esetben simán kifelejtek valamit.

Szerencsétlen esetben a megoldás tényleg nem egyértelmű.

Arra jutottam, hogy a 11 a legkisebb olyan szám, ami nem írható fel két prímszám összegeként. Létezik, hogy az egyetlen?... Ha igen, és ez egy nagy HA, mert most nem állok neki tesztet és bizonyítást fabrikálni, akkor B-nek 11-et súgtak, és innen tudta, hogy akármilyen x+y-ból jött ki a neki súgott szám, A kudarcot fog vallani. (Ha nem a 11 az egyetlen ilyen, akkor nem lehetséges megoldani a feladatot.) Ezzel elárulta A számára, hogy a neki súgott szám 11, így a megtudta, hogy teszemazt a neki súgott 18 az 2*9 és nem 6*3, vagy a 24 az 3*8 és nem 12*2, stb. Így ő is megtudta a két számot, de hogy mi a két szám, az a feladatból így nem derül ki.

Valaki bizonyítson vagy cáfoljon. :9

> „vagyis a neki súgott szám 2-nél több prímtényezőt tartalmaz.”

Egészen pontosan kettőnél többet, és ha hármat, akkor az a három nem lehet mindegyik ugyanaz, tehát a 2*2*2 az nem jó, mert az csak 2*4-ként lehet két tényező szorzata.

Aztán mivel B sem tudja kapásból a számot, ezért 6-nál nagyobbnak kell lennie az x + y-nak. Mivel B tudja azt is kapásból, hogy A nem tudja, ezért az x + y sehogy sem állhat elő két prím összegeként, se pedig p + p^2 alakban, ahol p prím (különben lehetséges volna, hogy a két szám szorzata olyan alakú, amit az előző bekezdésben kizártunk, és akkor B nem lehetne biztos a dolgában). A Goldbach-sejtést igazolták 10 000-nél kisebb számokra, így az összeg nem lehet páros, mert minden 5-nél nagyobb páros szám előáll két prím összegeként (legalábbis 10 000-ig, de 200-ig biztos). Ezenkívül azok a 100-nál kisebb páratlan számok sem lehetnek a B-nek súgott szám értékei, amik valamely prímszámnál 2-vel nagyobbak (a 100-nál nagyobb páratlan számok így sajnos nem esnek ki, mert se x se y nem lehet nagyobb 100-nál). Tehát a B-nek súgott szám ezek alapján lehet

11, 17, 23, 27, …, 191, 193, 195 és 197;

összesen körülbelül 60-70 lehetőség.

Aztán abból, hogy ezek páratlanok, következik, hogy az A-nak súgott számnak párosnak kell lennie

Látom régi a kérdés, de kiemelték. Neki fogok esni, de így elsőre lényeges trükknek tűnik, hogy az a kijelentés, hogy A elsőre nem tud válaszolni, nem csupán azt jelenti, hogy 2-nél több prímtényezője van a számnak. Ezt #7 már kapizsgálta a 2*2*2-vel, de csak a "ha három tényezős, akkor nem lehet három ugyanaz"-ig jutott.

Egy csomó ilyen kizárható 3 vagy akár 4 prímtényezős kombináció is van még. Például 53*2*3*7 felbontás esetén egyértelmű, hogy 53 és 42 a két szám, hiszen semmilyen más kombináció (pl. 106*21) nem működik a <=100-as kritérium miatt.

4 és 13 a két szám, izomból oldottam meg egy programmal. De legalább tudjuk, hogy megoldható.

A feladatban az 1 és 100 közötti azt jelenti, hogy 1 < x, y < 100. Ha az 1 is megengedett lenne, akkor négy lehetséges megoldása lenne. Az, hogy x=y megengedett-e, ami szintén nem volt tisztázott, nem változtat a megoldáson. Mondjuk, hogy megengedett.

A következő a lényeg:

98 számból ismétléssel kettőt kiválasztani (98 alatt a 2) + 98 = 4851 féleképp lehet.

Ebből a 4851 lehetőségből 1775 esetben egyedi a szorzat. Mivel A nem tudta a választ, ezért a fennmaradó 3076 lehetőség egyikével van dolgunk.

Mivel B előre tudta, hogy A nem fogja tudni megoldani a feladatot, ezért tudjuk, hogy az 1775 egyedi szorzatos eset egyikéhez sem olyan összeg tartozik, amit B kapott. Ez a 195 lehetséges összegből 185-öt kizár. B kezében a maradék 10 összeg egyike található (konkrétan 11, 17, 23, 27, 29, 35, 37, 41, 47, 53).

Ez az információ a lehetséges megoldások halmazát 3076-ról 145-re szűkíti, mivel kidobhatunk minden olyan számpárt, ahol az összeg nem a fenti 10 érték egyike.

Eközül a 145 lehetőség közül az A kezébe adott szorzat már egyedi, mivel A ezen a ponton rájött a megoldásra. A 145 esetből a szorzat egyedisége 86 esetben áll fenn.

Mivel B ennek ismeretében szintén rájött a megoldásra, ezért azt is tudjuk, hogy ezen 86 lehetőség közül az összeg szintén egyedi. És ez kizárólag egy esetben áll fenn: ha a két gondolt szám 4 és 13.

Sajnálom, hogy csak ilyen "ronda" megoldást tudok adni rá, de bárki leellenőrizheti a gondolatmenetet egy hasonló programmal. Remélem nem vétettem sehol logikai hibát.