25 decembra 2008

Úlohy pod stromček

Prajem Vám všetkým krásne sviatky! Aby ste vedeli, že na Vás myslím, tak som pre Vás ako darček pod vianočný stromček vymyslel tri matematické úlohy. Časti a) sú jednoduchšie a časti b) náročnejšie.

1. a) Koľko existuje rôznych ofarbení kocky dvomi farbami? Predpokladáme, že každá stena musí byt celá zafarbená jedinou farbou. Pochopiteľne, dve farbenia považujeme za identické, ak sa líšia len rotáciou kocky. b) Koľko existuje rôznych ofarbení kocky tromi farbami?

2. V súťaži o najkrajšiu matematickú úlohu je 12 úloh. Vzhľadom na to, že všetky sú rovnako pekné, každý hlasujúci sa rozhodne dať svoj hlas každej z týchto úloh s pravdepodobnosťou 1/12. Nájdite pravdepodobnosť, že niektoré dve úlohy dostanú rovnaký počet hlasov, ak je hlasujúcich a) 65; b) 650. Predpokladáme, že hlasujúci sa správajú navzájom nezávisle.

3. Máme štyri kladné čísla a,b,c,d, z ktorých najväčšie je menšie ako súčet zvyšných troch. a) Dokážte, že existuje štvoruholník so stranami dĺžok a,b,c,d, ktorého vrcholy ležia na spoločnej kružnici. b) Je možné takýto štvoruholník skonštruovať len pomocou ceruzky, pravítka a kružidla? (Predpokladáme, že na papieri už máme úsečky dĺžok a,b,c,d zakreslené.)

Pri riešení úloh 1b, prípadne 2b môžete použiť počítač. Priznám sa, že úlohu 3b som (v mojom limite 30 minút) nevyriešil, takže som zvedavý, ako úspešní budete Vy.

7 komentárov:

Lukáš povedal(a)...

Ja som bol trochu lenivý a na prvý príklad som si napísal program. Používam Burnsidovu lemu (http://en.wikipedia.org/wiki/Burnside's_lemma). V leme potrebujem zrátať počet ofarbení, ktoré fixuje nejaká rotácia. Každú rotáciu si predstavíme ako permutáciu. Prvky na každom cykle permutácie musia mať rovnakú farbu. Preto počet fixovaných ofarbení danou permutáciou je počet dostupných farieb umocnený na počet cyklov permutácie.

Keď som došiel až sem, tak sa mi cykly tých 24 permutácií hľadať nechcelo a napísal som si radšej program. A aby som nenaťahoval, vyšlo mi 10 ofarbení pre 2 farby a 57 pre 3 farby. Program je tu: http://paste2.org/p/120676

Janka povedal(a)...

Ďakujeme krásne, že na nás myslíte aj takto cez Vianoce.

A len taká malá poznámočka, že úlohu 3c) zatiaľ asi nikto nevyrieši, keďže ste nenapísali jej zadanie :).

Prajem Vám a Vašej rodinke ešte príjemné a pohodové Vianoce..

Radoslav Harman povedal(a)...

Lukáš: Fajn! Ak to v Tvojom programe predstavuje len malú zmenu a je to časovo prípustné, mohol by si nám vypočítať aj počet rôznych ofarbení štyrmi, piatimi, prípadne šiestimi farbami.

Janka: Trochu som tie písmenká poplietol; pardon. Už som to opravil.

Lukáš povedal(a)...

Upravil som program tak, aby rovno vygeneroval vzorec na počet ofarbení, ak máme k dispozícii n farieb: http://paste2.org/p/120718. Program vypíše vzorec (8*n^2 + 12*n^3 + 3*n^4 + 1*n^6) / 24.
Pre čísla 4, 5 a 6 má hodnotu 240, 800 a 2226.

Z toho vzorca sa dá inak vyčítať, že z tých 24 rotácií má 8 z nich 2 cykly, 12 má 3 cykly, 3 má 4 cykly a jedna má 6 cyklov.

katka povedal(a)...

K tej ulohe 3b, len strucne:

Chcem zostrojit tetivovy stvoruholnik ABCD, pricom poznam dlzky jeho stran (|AB|=a, atd.). Trojuholniky ABX a DXC su podobne (vrchlove uhly pri X, obvodove uhly...), takisto aj trojuholniky BXC a AXD su podobne. Z toho viem zistit v akom pomere sa uhlopriecky pretinaju, a aj pomer dlzok uhlopriecok (vyjadreny pomocou a, b, c, d). Takze si viem zostrojit nejake usecky vo vhodnom pomere, a aj ich rozdelit vo vhodnom pomere. Teraz uz len staci nejako ich niekolkonasobne zvacsit/zmensit, aby som dostala ich skutocnu velkost. (Totiz ak budem poznat dlzku niektorej uhlopriecky, uz nie je problem ten stvoruholnik skonstruovat.) Vdaka Ptolemaiovej vete poznam sucin dlzok uhlopriecok. S vyuzitim podobnosti trojuholnikov a Euklidovych viet uz nie je problem skonstruovat usecky pozadovanych dlzok (mozno nie uplne priamociaro, ale ide to :)).

Takze takyto stvoruholnik sa da skonstruovat len pomocou ceruzky, pravitka a kruzidla.

misof povedal(a)...

2a) 1, lebo na to, aby mali všetky navzájom rôzne počty hlasov, treba aspoň 0+1+...+11=66 hlasujúcich.

2b) Všetkých spôsobov hlasovania je 12^650, počet zlých (kedy majú všetci navzájom rôzne počty) je 12! * počet hlasovaní, kedy prvá úloha dostane najmenej, druhá viac, tretia ešte viac, atď. A na to si my leniví programátori napíšeme rekurenciu (napr. "koľkými spôsobmi viem priradiť hlasy A ľudí B úlohám tak, aby počty ľudí priradených úlohám boli rastúce a za každú hlasovalo viac ako C ľudí?") a program poráta.
Odpoveď by mala byť po zaokrúhlení na 8 miest 0.94198043. Kód tu: http://paste2.org/p/121114
a presný zlomok je dlhý jak sviňa (aj v normálnom tvare majú čitateľ aj menovateľ skoro 700 cifier), takže ho sem pastovať nejdem :)

Radoslav Harman povedal(a)...

Ďakujem za odpovede!

K príkladu 1 a hlavne ku grupe rotácií kocky asi ešte napíšem nejaký samostatný príspevok a ak sa mi bude chcieť, tak aj všetky tie rôzne ofarbenia kocky tromi farbami nakreslím (samozrejme pomocou počítača).

Katkino riešenie príkladu 3 si ešte musím v kľude premyslieť. Samozrejme, dá sa formulovať prirodzené zovšeobecnenie na ľubovoľný n-uholník so zadanými dĺžkami hrán.

Príklad 2 som uviedol preto, lebo sa mi zdalo byť zaujímavé, že aj ak máme zdanlivo veľmi veľa hlasujúcich, tak je kontraintuitívne vysoká pravdepodobnosť, že niektoré dve úlohy dostanú rovnaký počet hlasov. Je to trochu podobné ako narodeninový paradox