Matematické Fórum

↑ check_drummer:

Vychází mi to stejně :-).

Ověřil jsem to i pro zadání, kde místo 100 je 500 a stále vychází pouze jediné řešení. Neplatí náhodou, že to je jediné řešení i v případě, že čísla shora nebudeme omezovat?

Zdrojový kód (pro program Mathematica):

Soucin[list_]:=Apply[Times,list];
Soucet[list_]:=Total[list];
RozkladyNaSoucet[n_]:=Table[{k,n-k},{k,Max[2,n-99],Min[99,n-2,n/2]}];
RozkladyNaSoucin[n_]:=Select[{#,n/#}&/@Divisors[n],And[#[[1]]<=#[[2]],#[[1]]!= 1,#[[1]]>=n/99]&];

A0[dvojice_]:=A0[dvojice]=RozkladyNaSoucet[Soucet[dvojice]];
B0[dvojice_]:=B0[dvojice]=RozkladyNaSoucin[Soucin[dvojice]];

A1[dvojice_]:=A1[dvojice]=Select[A0[dvojice],Length[B0[#]]>1&];
B1[dvojice_]:=B1[dvojice]=B0[dvojice];

A2[dvojice_]:=A2[dvojice]=A1[dvojice];
B2[dvojice_]:=B2[dvojice]=Select[B1[dvojice],Not[MemberQ[Length[B1[#]]&/@A0[#],1]]&];

A3[dvojice_]:=A3[dvojice]=Select[A2[dvojice],Length[B2[#]]>1&];
B3[dvojice_]:=B3[dvojice]=B2[dvojice];

A4[dvojice_]:=A4[dvojice]=A3[dvojice];
B4[dvojice_]:=B4[dvojice]=Select[B3[dvojice],Length[A3[#]]>1&];

A5[dvojice_]:=A5[dvojice]=Select[A4[dvojice],Length[B4[#]]==1&];
B5[dvojice_]:=B5[dvojice]=B4[dvojice];

reseni={};
For[i=2,i<100,i++,
  For[j=i,j<100,j++,
    If[And[
        Length[B0[{i,j}]]>1,
        Not[MemberQ[Length[B0[#]]&/@A0[{i,j}],1]],
        Length[B2[{i,j}]]>1,
        Length[A3[{i,j}]]>1,
        Length[B4[{i,j}]]==1,
        Length[A5[{i,j}]]==1],
      reseni=Append[reseni,{i,j}];
    ];
  ];
];
reseni//TableForm

Poznámky ke kódu:

1) Konstrukce f[x_] := f[x] = casoveNarocnaFunkce[x]; je tam proto, aby se casoveNarocnaFunkce nemusela pro stejné x počítat víckrát. Po prvním volání f[x] se vypočte casoveNarocnaFunkce[x] a hodnota se uloží do f[x]. Při dalším volání se tak vlastně nevolá funkce f[x_], ale jen se vezme vypočtená hodnota f[x].

2) Funkce Ai[x] resp. Bi[x] vrací všechny možné dvojice, které mohou být řešením podle osoby A resp. B po i-tém řádku dialogu za předpokladu, že původní dvojice z které se počítal součin a součet byla x.

↑ check_drummer:
Já jsem přišel na to:
Dva matematici
Jsou dána dvě přirozená čísla a a b větší než 1. Utvoříme jejich součet a+b a jejich součin a.b.
Dva matematici mají za úkol obě čísla najít. Jeden matematik (Adam) zná pouze součin a.b, druhý matematik (Bedřich) zná pouze součet a+b.
Sledujme jejich rozhovor:
Adam: "Nevím, která jsou to čísla."
Bedřich: "To jsem věděl."
Adam: "A tak já už vím!"
Bedřich: "A tak já už vím taky!"

Najděte čísla a a b, víte-li že součin a.b je menší než 100.
Řešení

Nejdříve je třeba si uvědomit, že Bedřich ze součinu nepoznal, co jsou to za čísla. To znamená, že rozklad na součinitele měl více než jednu možnost --> číslo a*b není součin 2 prvočísel, neboli bud a nebo b neni prvočíslo [nebo obě nejsou].

Poznatek z druhé věty už je zajímavější:
Adam věděl, že Bedřich nemohl hned uhodnout co jsou to za čísla. Tedy musel mít takový součet 2 čísel, který pro všechny možnosti rozkladu na soucet 2 čísel nedával 2 prvočísla. Pro lepší pochopení příklad: Pokud by měl Adam 9, zkusil si všechny možnosti rozkladu:
7+2
6+3
5+4

Jenomže, kdyby čísla a,b byla čísla 7 a 2, výsledný Bedřichův součin by byl 14 A to je součin 2 prvočísel – v tomto případě by tedy Adam nemohl tvrdit, že ví, že Bedřich to nemohl vědet. Pojmenujme čísla, která splňují vlastnost věty 2, tedy že ve všech možných rozkladech se nevyskytuje prvočíslo+prvočíslo kandidátem. Prvním takovým netriviálním kandidátem je číslo 11:

11=9+2
11=8+3
11=7+4
11=6+5

V žádné z těchto možností nedojde k tomu, že by se součet skládal ze dvou prvočísel, tedy Adam opravdu mohl tvrdit, ze Bedřich neví co jsou to za číisla. Shrneme-li vlastnosti kandidáta, musi splňovat:
kandidat – p1 je různé od p2 [kde p1 a p2 jsou vhodná prvočísla – p1 mensi nez kandidát]

Takových kandidátů je však stále mnoho, přejděme k třetí a čtvrté věte.

Bedřich podle Adamovy reakce poznal co je to za číslo. To znamená, že z možností rozkladu jeho čísla a*b na 2 součinitele byl právě jen jeden kandidát. Pro lepší názornost zase příklad:
Rekněme, že Bedřich dostal číslo 18. To jde rozložit jako 9x2 a 6x3. Adam řekl, že vědel, že to neví, tedy jeho součet byl kandidát. Z možnosti [9+2=11] a [6+3=9] je kandidátem jenom číslo 11, Bedřich by tedy hned vědel, že čísla a, respektive b jsou 9 a 2. Tímto však příklad stále není vyřešený, protože je tu 4-tá věta. Podle Bedřichovy nadšené reakce Adam také poznal čísla a,b. To by však v případě součtu (kandidáta) 11 nepoznal. Proč? Chudák Adam si musel trochu započíitat, řekněme například, že měl číslo 11:
Nejdříve zkusil všechny rozklady na soucet 2 čísel, čímž zjistil, zda-li ma kandidáta [viz věta2]:
11=9+2
11=8+3
11=7+4
11=6+5

Pro každou tuto možnost musel spočítat součin a*b, tedy možné Bedřichovo číslo:
11=9+2 --> 9*2=18
11=8+3 --> 8*3=24
11=7+4 --> 7*4=28
11=6+5 --> 6*5=30

Pro každé takto vzniklé číslo [říkejme mu Bedřichův kandidát – v našem příipadě to jsou čísla 18, 24, 28, 30] si musel vytvořit všechny jeho rozklady na součiny možných čísel a,b:

18 = 2*9 = 3*6
24 = 2*12= 3 * 8 = 4*6
28 = 2*14 = 4 * 7
30 = 2*15 = 5 * 6

Adam ví, že Bedřich hnedka podle věty 2 poznal čísla a a b. Tedy ve všech možnostech rozkladu Bedřichova kandidáta na součin a*b byl součet a+b kandidátem pouze jednou! Toto splňuje například číslo 18 [2+9=11 je kandidát, 3+6 kandidát není], naopak číslo 30 to nesplňuje [5+6=11 je kandidát, 2+15=17 je ale taky kandidát --> Bedřich by nemohl říct, že už ta čísla ví!]. Adam tedy mohl vyloučit možnost a=6,b=5, protože při ní by Bedřich hned nepoznal čísla a i b. Bohužel takto vyloučit nemůže možnosti a=9,b=2  ; a=8,b=3 ; a=7, b=4. Tedy pokud konverzace probíhala jak je napsáno výše, Adam by po třetí větě nebyl schopen určitčísla a,b! Tímto jsme vyloučili číslo 11. Dostali jsme další podmínku pro kandidáta, tedy číslo, které obdržel Adam a to
Adamovo číslo musí být kandidát a navíc pro všechny možnosti rozkladu kandidáta na součet 2čísel musí platit: Kandidát = c + d, potom číslo (c*d) jde rozložit na všechny možné součiny e*f takové, že e+f  není kandidátem pouze jednou. V předchozím příkladě s číslem 11 by tedy muselo platit, že pouze jeden z Bedřichových kandidátů nejde napsat jako součin 2 čísel takových, že jejich součet je kandidátem.

Podle me to jsou všechny omezující podmínky, které nam stačí k najití rešení, tedy čísel a a b.
Je zřejmé, že najít takového kandidáta ručne není jednoduchá práce. Ale s podmínkou, že součin nemá být větší než 100 to ručně půjde.
Prvočísla:
2 3 5 7 11 13 17 19 23 29......

Kandidáti splňující větu2:
11 17 23 27 29 ………..

Prvním nalezeným výsledkem je kandidát 17.(11 jsme vyloučili) Ověřme, že je to opravdu řešení

17=15+2 --> 15*2=30 ale 30=5*6  a 5+6=11 je kandidát
17=14+3 --> 14*3=42 ale 42=21*2 a 23 je kandidát
17=13+4 --> 13*4=52 --> 52 se dale dá napsat jen jako 26*2 a 28 kandidátem není!
17=12+5 --> 12*5=60 ale 60=20*3 a 23 je kandidát
17=11+6 --> 11*6=66 ale 66=33*2 a 35 je kandidát
17=10+7 --> 10*7=70 ale 70=35*2 a 37 je kandidát
17=9+8   --> 9*8=72 ale 72 = 3*24 a 27 je kandidát

Předpokládejme tedy že výsledek je a = 13 b = 4 a ověřme ještě znovu komunikaci mezi Adamem a Bedřichem:

B: Nevím co jsou to za čísla [to neví, dostal 52 a to se dá napsat jako 13*4 ale i 26*2]
A: Věděl jsem, že  to nevíš[to věděl, protože číslo 13 + 4= 17 je kandidát]
B: Teď už vím[ano, protože 26 + 2=28 kandidátem není]
A: Teď už taky vím [ano, protože jenom jedna jediná možnost z rozkladu 17-ky na součet 2 čísel byla taková,že tam nevznikl další kandidát při rozkladu na součin [viz výše].

Výsledkem příkladu je tedy a= 13, b= 4. Mezi další výsledky patří:

a = 4,b = 61,
a = 16,b =73
a=16,b=111
a=32,b=131
a=16,b=163
a=4,b=181
a=64,b=127

Ale tato čísla už nesplňují podmínku součinu a*b < 100

Myšlená čísla jsou tedy 4 a 13.

Doufám, že se v tom vyznáš.
PS: Ikdyž úloha je trochu jiná než ta Tvoje.

↑ Andrejka3:
Ahoj, už je to hodně dávno co jsem to psal, tak už ten program asi nenajdu.. Ale Pavel Brozek výše uvádí zdrojový kód toho svého.
A je opravdu Tvé druhé řešení řešením? Použáváš nějaký program?
Možná bys mohla zdůvodnit u každé odpvědi osob A,B výše, proč je to korektní řešení, např. proč v daném kroku osoba A ještě nemůže znát ta čísla, apod.