Metóda "alias" používaná na simulačné generovanie diskrétnych náhodných premenných sa opiera o vetu, ktorej špeciálny prípad je možné pekne geometricky interpretovať:
Akýkoľvek bod C vo vnútri štvorstena je ťažiskom nejakého trojuholníka, ktorého vrcholy ležia na hranách tohto štvorstena.
Vedeli by ste túto vetu dokázať? Napadajú Vás nejaké zovšeobecnenia tejto vety?
(Ospravedlňujem sa všetkým riešiteľom, ktorí sa trápili s pôvodnou nesprávnou formuláciou vety.)
25 februára 2011
05 februára 2011
Tri sochy
Kto nám do komentárov ako prvý napíše správne riešenie nasledovnej úlohy, dostane odo mňa knihu "Professor Stewart's Cabinet of Mathematical Curiosities" od Iana Stewarta (to aby som Vás motivoval túto úlohu aspoň dočítať do konca). Zadanie pochádza od Braňa Novotného (ďakujeme) a sponzorom tejto súťaže je, hoci o tom nevie, Thomas Klein (tiež ďakujeme; keď ma bol navštíviť, doniesol mi knižku, ktorú už vlastním :).
Na ceste za pokladom je chrám, z ktorého vedú dve cesty - vľavo a vpravo. Jedna vedie k pokladu a jedna do záhuby. V chráme sú tri sochy. Jedna vždy hovorí pravdu, jedna vždy klame (hovorí nepravdu - tj. nesnaží sa zavádzať), a jedna odpovedá náhodne.
O sochy sa starajú dvojičky, ktoré môžu položiť sochám dve otázky denne, vždy sa musí pýtať práve jeden z nich práve jednej sochy a tá odpovie podľa svojej prirodzenosti, ale keďže sú to iba sochy, tak zvládnu iba A a O, jedno znamená áno, druhé nie. Sochy majú dosť informácií: tj. rozoznajú bratov, vedia ktoré dvere sú správne, majú rozumný prehľad o svojom okolí a ak sa ich niekto spýta otázku, na ktorú nevedia korektne odpovedať A, alebo O, tak odpovedia náhodne.
Hľadačovi pokladu vysvetlia bratia pravidlá a za dostatočnú odmenu sú ochotní spýtať sa sôch dve pútnikove otázky a to tak, že (hľadačom) vybraný brat otázku presne zopakuje vybranej soche a vypočuje si odpoveď a tú povie hľadačovi, lenže starší brat odpoveď vždy zmení na opačnú. Samozrejme bratia neprezradia ktorý z nich je starší, ktoré z A a O je áno a ktoré nie a sochu, ktorej sa budú pýtať, môže hľadač určiť iba ako vľavo, vpravo a v strede.
Aké dve otázky sa má hľadač spýtať, aby sa dozvedel ktorá cesta vedie k pokladu?
Na ceste za pokladom je chrám, z ktorého vedú dve cesty - vľavo a vpravo. Jedna vedie k pokladu a jedna do záhuby. V chráme sú tri sochy. Jedna vždy hovorí pravdu, jedna vždy klame (hovorí nepravdu - tj. nesnaží sa zavádzať), a jedna odpovedá náhodne.
O sochy sa starajú dvojičky, ktoré môžu položiť sochám dve otázky denne, vždy sa musí pýtať práve jeden z nich práve jednej sochy a tá odpovie podľa svojej prirodzenosti, ale keďže sú to iba sochy, tak zvládnu iba A a O, jedno znamená áno, druhé nie. Sochy majú dosť informácií: tj. rozoznajú bratov, vedia ktoré dvere sú správne, majú rozumný prehľad o svojom okolí a ak sa ich niekto spýta otázku, na ktorú nevedia korektne odpovedať A, alebo O, tak odpovedia náhodne.
Hľadačovi pokladu vysvetlia bratia pravidlá a za dostatočnú odmenu sú ochotní spýtať sa sôch dve pútnikove otázky a to tak, že (hľadačom) vybraný brat otázku presne zopakuje vybranej soche a vypočuje si odpoveď a tú povie hľadačovi, lenže starší brat odpoveď vždy zmení na opačnú. Samozrejme bratia neprezradia ktorý z nich je starší, ktoré z A a O je áno a ktoré nie a sochu, ktorej sa budú pýtať, môže hľadač určiť iba ako vľavo, vpravo a v strede.
Aké dve otázky sa má hľadač spýtať, aby sa dozvedel ktorá cesta vedie k pokladu?