Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 10. 11. 2011 18:56 — Editoval check_drummer (10. 11. 2011 19:06)

check_drummer
Příspěvky: 2397
Reputace:   65 
 

"Metaúloha" o myšlených číslech

Ahoj,
reaguji na úlohu http://forum.matweb.cz/viewtopic.php?id=29054, v podstatě je velmi podobná a ještě zamotanější. :-)
Původní úlohu jsem vyřešil s pomocí PC a hrubé síly a řekl jsem si, že ji ještě obohatím - řešení by dle PC mělo rovněž být jednoznačné. Zde je znění úlohy - tučně jsem označil místa, která jsou oproti původní úloze navíc.


Myslím si dvě přirozená čísla; každé z nich je větší než 1 a menší než 100. Nyní vezmu tato čísla, sečtu je a výsledek řeknu osobě A. Potom čísla mezi sebou vynásobím a výsledek řeknu osobě B. (Pozn.: obě osoby všechny tyto informace znají, jen neví, jaké číslo jsem sdělil druhé osobě.) Následně mezi těmito (náležitě matematicky nadanými) osobami proběhne konverzace:

B: Nemám zdání, jaká čísla to jsou.
A: Věděl jsem, že to nemůžeš uhodnout.
B: Stále nevím, jaká čísla to jsou.
A: Já také ne.

B: Už vím, která čísla to byla.
A: Já také.

Jaká čísla jsem si myslel?


Achilleovo tvrzení: Ocitl jsem se v patové situaci.

Offline

  • (téma jako vyřešené označil(a) check_drummer)

#2 14. 11. 2011 00:13

check_drummer
Příspěvky: 2397
Reputace:   65 
 

Re: "Metaúloha" o myšlených číslech

↑ check_drummer:
Dle mého algoritmu (programu) vychází jednoznačné řešení:


Ovšem není zřejmé, zda algoritmus je správný - budu velmi rád, kdyby někdo přišel se stejným výsledkem. :-)


Achilleovo tvrzení: Ocitl jsem se v patové situaci.

Offline

 

#3 15. 11. 2011 15:28 — Editoval Pavel Brožek (15. 11. 2011 16:20)

Pavel Brožek
Místo: Praha
Příspěvky: 5694
Škola: Informatika na MFF UK
Pozice: Student
Reputace:   194 
 

Re: "Metaúloha" o myšlených číslech

↑ 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):

Code:

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.

Offline

 

#4 15. 11. 2011 17:45

check_drummer
Příspěvky: 2397
Reputace:   65 
 

Re: "Metaúloha" o myšlených číslech

↑ Pavel Brožek:
Mně to mám pocit pro vyšší čísla - myslím kolem 2000 - dávalo už nejednoznačné výsledky, ale do tisíce to bylo myslím stále jednoznačné. Pro maximální hodnotu 3000 došla perlu paměť, i když zrovna perl na toto moc vhodný není. :-)
Díky. :-)


Achilleovo tvrzení: Ocitl jsem se v patové situaci.

Offline

 

#5 07. 04. 2017 07:25 — Editoval Cheop (07. 04. 2017 07:26)

Cheop
Místo: okres Svitavy
Příspěvky: 7330
Škola: PEF VŠZ Brno (1979)
Pozice: pracující
Reputace:   362 
 

Re: "Metaúloha" o myšlených číslech

↑ 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.


Nikdo není dokonalý

Offline

 

#6 02. 11. 2017 10:24

Andrejka3
Moderátor
Příspěvky: 1885
Škola: PŘF UP Olomouc (2015)
Reputace:   112 
 

Re: "Metaúloha" o myšlených číslech

↑ check_drummer:
Ahoj. Mě vyšly dva výsledky,
kromě 2, 15 také 21, 32.
Jste si už jistí, že to je jednoznačné? Díky.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#7 04. 11. 2017 21:53 — Editoval check_drummer (04. 11. 2017 21:56)

check_drummer
Příspěvky: 2397
Reputace:   65 
 

Re: "Metaúloha" o myšlených číslech

↑ 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.


Achilleovo tvrzení: Ocitl jsem se v patové situaci.

Offline

 

#8 05. 11. 2017 00:16

Andrejka3
Moderátor
Příspěvky: 1885
Škola: PŘF UP Olomouc (2015)
Reputace:   112 
 

Re: "Metaúloha" o myšlených číslech

↑ check_drummer:
Ahoj.
Našla jsem ve svém kódu pár chyb. Myslím, že už je dobře. Vychází mi to jednoznačně, stejně jako vám.
Díky za reakci.
Psala jsem to v C.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson