Štvrtú úlohu do našej súťaže poslal Peter Richtárik, bývalý študent FMFI UK a autor nám dobre známeho blogu "predbarákom".Máme k dispozícii dve identické fľaše, ktoré sa pri pustení z určitej (neznámej) výšky rozbijú. Fľaše môžeme skúšobne púšťať voľným pádom na zem z okien 100 poschodovej budovy. Ak sa fľaša rozbije, už je nepoužiteľná, ale ak sa nerozbije, ani trochu sa nepoškodí. Našim cieľom je zistiť číslo najvyššieho poschodia, z ktorého keď pustíme fľašu tohoto typu, tak sa ešte nerozbije. Koľko pokusných hodov na to určite stačí? Presnejšie povedané: Aký je minimálny počet hodov, pomocou ktorých vieme zaručene určiť číslo najvyššieho poschodia, z ktorého flaša nášho typu prežije pád?
Úlohu Peťovi zadal kolega z Ruska Anton Belyakov. Vzorové riešenie zatiaľ nemáme, takže sa teším na Vaše riešenia v komentároch.
nejakych 13 by malo stacit.
OdpovedaťOdstrániťHmmm. A aká je prislušná stratégia hádzania fliaš?
OdpovedaťOdstrániť13 je podla mna malo..
OdpovedaťOdstrániťked mame len jednu flasu, mozeme len linearne poschodie po poschodi hadzat(ked nejake poschodie preskocime a flasa sa rozbije,nevieme ci by sa na nom rozbila alebo nie..) Ale kedze mame flase 2, jednu pouzijeme na zistenie useku, v ktorom existuje poschodie, od ktoreho sa uz rozbije.
Prvu flasu budeme hadzat z poschodi 10,20...,90 tj.9 max. hodeni. Druhu budeme hazdat v useku na konci ktoreho sa nam prva rozbila. usek ma dlzku 9, takze treba 9 hodeni. Dokopy 18.
No hej, lenze ked by si predpokladal, ze 18 Ti staci, tak hned na prvu supu mozes skusit hodit rovno z 19. poschodia, lebo zvysnych 17 hodov Ti na odlisenie tohto prveho useku stacit bude. Takze... ked staci n hodov, tak mozes rovno hazdat z n+1-eho poschodia, potom z 2n+1-eho, potom z 3n-eho, potom z 4n-2-eho (vzdy sucet radu n+1 + n + n-1 + n-2 + ...) a len to treba nejako rozumne ukoncit. Aspon takto by sa dala wassilova strategia vyrazne vylepsit - a mozno ma aj prvy anonym pravdu.
OdpovedaťOdstrániťoki, prehodnotene, prepocitane...
OdpovedaťOdstrániťanonym sa fakt nemylil ;)
Ide to riešiť aj všeobecne, pre N fliaš. Stačí sa na to pozrieť opačne a napísať si rekurenciu pre T(N,K) = medzi koľkými rôznymi možnosťami dokážeme rozlíšiť, keď máme N fliaš a K hodov.
OdpovedaťOdstrániťVo všeobecnosti T(N,K) = T(N-1,K-1) + T(N-1,K) + 1.
7
OdpovedaťOdstrániť42.
OdpovedaťOdstrániťKto da viac? Nikto, lebo toto je ta fundamentalna odpoved.
1. 100. poschodie
OdpovedaťOdstrániť2. ak sa rozbije, tak 50. poschodie
3. ak sa nerozbije, tak 75. poschodie, inak 25. poschodie
atd.
teda dvojkovy logaritmus 100, co je 7 (2 na co je aspon 100? 2 na 7, co je 128)
... a ked sa Ti rozbije pri druhom hode druha flasa, tak vies, ze je to niekde medzi 1. a 25. poschodim, ale nemas ponatia kde presne. Takze to nepojde.
OdpovedaťOdstrániťMne vyšlo 14. Tiež mi najprv napadlo niečo ako wassila. Ale stále sa mi to zdalo veľa. POZOR! MOJE RIEŠENIE: Najprv vyhodím prvú fľašu zo 14. poschodia a ak sa rozbije, druhú postupne hádžem od 1. k 13. poschodiu. V najhoršom prípade to bude 1+13=14 hodov. Ak sa prvá nerozbije tak ďalej nehodím zo 14+14=28. poschodia, ale zo 14+13=27. Zase ak sa rozbije, tak druhú hádžem už iba 12 krát, čo v najhoršom prípade dáva 2+12=14. Takto pokračujem až do konca, vždy bude v najhoršom prípade súčet hodov prvej a druhej fľaše 14. 14+13+12+11+10+9+8+7+6+5+4 = 99. Koľkaté v poradí je číslo, toľko krát sa hádzala prvá fľaša, a to číslo mínus jedna udáva koľko krát hádžeme druhou fľašou v najhoršom prípade ak sa prvá rozbije. Tento súčet vždy dáva 14. V prípade, že by sa nerozbila prvá ani na 99, tak samozrejme stačí vyskúšať už iba na 100 poschodí, čo je iba 11+1=12 hodov. Takže odpoveď je teda 14. Snáď sa tomu dá rozumieť.
OdpovedaťOdstrániťaj podla mna je to dvojkovy logarytmus zo 100, ibaze anonymny to trochu zle vysvetlil, nezacneme hadzat zo 100 poschodia ale z 50-eho, potom aj ked je spravne poschodie medzi 1.-25., tak mame este 5 pokusov(opat hladame dvojkovy log z 25, co je 5)
OdpovedaťOdstrániťto: detroit72
OdpovedaťOdstrániťprecitaj si este raz zadanie - "Máme k dispozícii DVE (cislom: 2) identické fľaše", spravne riesenie = 14 je uvedene vyssie
Môžem potvrdiť, že riešenie od "FEDOOA" je optimálne.
OdpovedaťOdstrániťNechcel som ho vzorovo písať, tak ako to bolo spravené pri predchádzajúcich súťažných úlohách, pretože narozdiel od nich je táto úloha vcelku riešiteľná (rozumej: nie je ťažká ako šľak).
Veľmi peknú diskusiu ste tu vytvorili, podobnú tomu ako som nad tým uvažoval pôvodne aj ja. Najprv začnem s nejakou predstavou riešenia, rozmýšľam či je ideálne, snažím sa pochopiť ako by sa dalo dokázať, že je optimálne a podobne... Tiež ma napadlo niečo ako konštantné skoky, alebo bisekcia, alebo "začni v strede" a podobne predtým ako som dostal ten FEDOOV nápad, kde už bolo jasné, že riešenie je optimálne.
To riešenie od "FEDOOA" sa dá pomerne ľahko dopliť aj vysvetlením, prečo je optimálne. Fedoo: chce sa ti to dopísať?
Ešte raz: som rád, že vás úloha pobavila tak ako mňa!
Tak ešte poďakujem za super hádanku. Mám rád také, kde sa dá na riešenie prísť čisto logicky bez veľkej znalosti matematiky + najradšej mám tie, ktoré som vyriešil celkom sám :)
OdpovedaťOdstrániťNeviem, čo presne myslí-š/te doplnením. Ak by som skúsil, či by nefungovala trinástka, tak by mi vyšlo 13+12+11+10+9+8+7+6+5+4+3+2+1 čo sa rovná 91. A to je málo, pretože ak by sa prvá nerozbila ani na 91. poschodím ,tak v najhoršom prípade musím ešte overiť 9 poschodí, čo je 13+9=22 a to už je veľa. Myslím, ale že toto nie je dobrý dôkaz optimálnosti :)
FEDOO: Ty vlastne vravíš niečo ako:
OdpovedaťOdstrániťKeby zbehnem môj algoritmus tak, že začnem od 13, tak nebude fungovať.
Samozrejme, z toho samotného nevyplýva, že algoritmus je optimálny. Dá sa však na to celé pozrieť trochu inak; tak, že TVOJ POSTUP JE ZÁROVEŇ DôKAZOM OPTIMALITY.
Polož si otázku: existuje algoritmus, ktorý zaručene potrebuje iba 13 hodov? Ak áno, čo vieš povedať o poschodí z ktorého bude hodená prvá fľaša v tomto algoritme? A čo druhá?
Zbytok nechám na tebe...
Teraz si trochu pripadám ako pri skúške :) Nie som si istý, či presne rozumiem, čo sa odo mňa očakáva. Proste, pre menšie čísla ako 14 tento spôsob nefunguje, pretože súčet n + (n-1) + (n-2) + ... + 1 (pre nejaké n<14) je o veľa menší ako 100.
OdpovedaťOdstrániťSorry FEDOO, nechcel som zniet tak haluzne... Nasiel si pekne riesenie, neviem naco to rozpitvavam.
OdpovedaťOdstrániťEste mi tu chybalo take riesenie, ze nebudem predsa flase hadzat na zem ale ich proste vypijem s kamosmi. To by bolo celkom originalne ;-)
Mne samozrejme vôbec nevadí, že to rozpitvávaš, skôr to, že ja neviem odpovdať. ja sám som zvedavý ako na to odpovedať.
OdpovedaťOdstrániťPredpokladajme že existuje sstratégia S ako to spraviť s 13 fľašami.
OdpovedaťOdstrániťJe potom jasné, že v stratégii S musí byť prvá fľaša hodená nanajvýš z 13. poschodia. Prečo?
Lebo ak by sme prvú fľašu zhodili z vyššieho poschodia a táto by sa rozbila, potom by sme boli nútení hádzať druhú fľašu postupne zo spodu (1. poschodie, 2. poschodie, atď). Inak by sme totiž nemohli zaručiť, že hľadané poschodie presne identifikujeme. Ak teda označíme symbolom S1 poschodie z ktorého táto stratégia hádže prvú fľašu, potom S1 <= 13.
A čo druhá fľaša?
Táto musí byť hodená nanajvýš z poschodia S2<=S1+12. To preto, lebo v prípade, že sa prvá nerozbije a druhá áno, potom musíme postupne hádzať druhú fľašu z poschodí S1+1, S1+2, ..., S2-1 (v najhoršom prípade teda ďaľších S2-S1-1 hodov navyše od prvých dvoch, spolu S2-S1+1). Keďže S1<=13 a chceme aby S2-S1+1<=13, musí byť S2<=25.
Takto pokračujeme ďalej a prídeme na to, že 13 fľaša musí byť hodená nanajvýš z 91 poschodia. To znamená, že nemáme šancu preskúmať poschodia 92-100, čo je spor.
Fedoo: takto som to myslel. V tvojom riešení sa zároveň skrýva dôkaz jeho optimality. Myslím si však, že si to vedel, len si nevedel čo to ja vlastne od teba chcem ;-)
Budem sa tváriť, že som to vedel. Ja som to napísal vlastne iba trošku nepresnejšie a stručnejšie.
OdpovedaťOdstrániťV podstate nam staci 13 pokusov lebo vieme ze ten posledny nemusime skusat lebo je to prave on :-)
OdpovedaťOdstrániťJa som to tušil, že keď ten môj prvý príspevok nerozpíšem podrobnejšie, tak ostane prehliadnutý alebo nepochopený :)
OdpovedaťOdstrániťKeď sa na ten problém díva tým opačným spôsobom, teda keď sa pýtame, medzi koľkými možnými odpoveďami vieme pri danom počte fliaš a pokusov rozlíšiť, tak dostaneme v jednom:
- kompletný návod ako fľaše hádzať -- tak, aby nám v oboch prípadoch [rozbije/nerozbije sa] ostalo nanajvýš toľko možností, koľko ešte zvládame rozlíšiť
- dôkaz, že to na menej hodov ako to, čo sme spočítali, nejde
- ďalšie pekné veci, ako napríklad odpoveď na otázku, z akého najnižšieho poschodia môžeme hodiť prvú fľašu, aby sme ešte stále mali worst case optimálne riešenie
a to celé pre ľubovoľný pevne zvolený počet fliaš, nie len dve :)
tuto sa tou ulohou tiez zaoberaju, ale maju tam namiesto flasi biliardove gule:
OdpovedaťOdstrániťhttp://20bits.com/articles/interview-questions-two-bowling-balls/
MISOF: Samozrejme máš pravdu. Tvoj príspevok som prehliadol. Ak sa Ti chce to vypočítať pre 3 fľaše, rád by som vedel výsledok.
OdpovedaťOdstrániťCHARON: K tomu linku sa síce neviem dostať, ale je mi jasné, že úlohu nevymyslel ten môj kamoš Anton. Keďže som bol lenivý si zisťovať jej pôvod, tak som jednoducho spomenul iba jej pôvod z môjho lokálneho pohľadu ;-)
Ako tam k tej úlohe pristupujú?
mne ten link funguje ked ho skopirujem z mojho postu. ale tak este raz ho davam: tinyurl.com/6ee2j4
OdpovedaťOdstrániťhttp://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle
OdpovedaťOdstrániť