17 septembra 2012

Horiace tyče


Majme dve tyče z neznámeho nehomogénneho materiálu, pričom vieme len to, že každá z nich zhorí presne za 1 minútu. Rýchlosť horenia v jednotlivých častiach tyčí kvôli neznámemu zloženiu nevieme určiť. Ako pomocou nich zmerať presne čas 45 sekúnd? Čas zapálenia tyče neuvažujeme. 

Túto peknú úlohu nám poslal Peter Mikloš; ďakujeme! :)

16 komentárov:

Rori povedal(a)...

Touto ulohou aj ja trapim ostatnych :) je naozaj zaujimava a preto nebudem pisat riesenie (no jasne, musel som sa pochvalit ze riesenie viem :) (a dosiel som onoho casu nan sam :) ))

goober povedal(a)...

Rori: Tak my si zatiaľ môžeme položiť otázku, že koľko rôznych časových intervalov sa dá takto zmerať (napríklad taká minúta je ľahká :-) ).

No a keby toho bolo málo, môžeme si pridať ďalšiu tyčku či dve ;-)

Radoslav Harman povedal(a)...

... alebo koľko časových úsekov sa dá odmerať, ak máme n tyčí, ktoré horia t_1,...,t_n minút. :)

Lev bez hrivy povedal(a)...

Radoslav, to závisí od toho, či sú t_i navzájom rôzne, nie?

Rori povedal(a)...

no nic mensie ako pol minuty neodmerame (teda aspon ma nenapada pri nehomogennom spagate - teda tyce - ja to poznam zo spagatom)

pri n tyciach vieme zmerat urcite casy z mnoziny (hmmm ako to rozumne zapisat ked tu nemame matematicke symb.)

sum[i => 1 az k] ( 1 / 2 ^ i) - pricom k <= n a vysledok je vlastne z <0,1> pricom 1 znamena casovu dlzku horenia jedneho spagata.

trosku rozmyslam ci sa da vobec nejaky iny cas dosiahnut

Anonymný povedal(a)...

No, skoro tak ako napísal Rori, že s každou tyčou navyše sa vieme dostať k polovici predošlého pokusu. Pre 2 palice je, ak sa nemýlim 6 možných riešení - 1/4, 1/2, 3/4, 1, 3/2 a 2. Pre 3 palice nám pribudnú:
1/8, 3/8, 5/8, 7/8 a kombinácie 1+[niektoré zo šiestich predchádzajúcich riešení. To 1+predch. riešenie platí aj medzi počtom tyčí 2 a 1.
Matematicky by to mohol byť teda rad:
sum[m=1..n] (pre 1<=k<=m, sum[i=0..k] (1/2^i))

Peter povedal(a)...

Ach jaj, a to 1+ som tam nedal. Akurát ma teraz narýchlo nenapadá, ako to tam zakomponovať.

Radoslav Harman povedal(a)...

Len malý komentár: V otázkach typu "koľko rôznych časových intervalov vieme odmerať... " je potrebné upresniť si, čo myslíme pod "odmeraním časového intervalu".

Ak chceme odmeriavať čas počnúc okamžikom keď tyče a zápalky dostaneme k dispozícii, tak vieme odmerať menej časových úsekov, ako keď si môžeme sami zvoliť začiatok merania časového úseku.

Napríklad: V tom prvom prípade nie je možné s dvomi minútovými tyčami odmerať čas 15 sekúnd, no v tom druhom prípade áno. (Samozrejme, stále uvažujeme s tým, že zapálenie čohokoľvek nám trvá nulový čas.)

Rori povedal(a)...

Ja som bral prvy pripad - teda ze start je pri prvom zapaleni.

A zabudol som na cas > 1 :)

ono v podstate vieme vyskladat potom vysledky podobne ako anonym pisal. Dnes kedze uz nemam vela casu tak len tipnem, ze to co som napisal ako prve - tak tie casy sa daju zratuvat (ak mam 5 tyci tak mozem zobrat vysledok 3 a 2 a spocitat) - a ten moj tip je, ze ine riesenia nie su (ale este treba zistit v akom tvare su naozaj tie riesenia co som napisal)

Peter povedal(a)...

Pokial by sme potrebovali ten cas 45s urcit len s istou povolenou chybou, tak by sme mohli tyc rozrezat na napr. 60 malych casti, vybrat z nich nahodne 45 a tie postupne zapalovat (zapalit dalsiu hned ked zhori predosla). Vsetkych 45 casti by malo zhoriet v priemere za 45s. Dlzka dielov by sa dala znizit pre dosiahnutie vacsej presnosti.

Ak by sme potrebovali aj interval spolahlivosti, tak by sme mohli najprv druhu tyc rozrezat na vela malych casti, ktore by sme zapalili vsetky naraz a zmerali ich dlzky po nejakom case (kym este nezhori ani jedna celkom). Z nich by sa dalo odvodit statisticke rozdelenie rychlosti horenia jednej casti. Simulaciou by sme potom vypocitali statisticke rozdelenie suctu dlzok horenia pri nahodnom vybere 75% dielov tyce.

goober povedal(a)...

Rori: S tým "skladaním" to nebude také jednoduché. Áno, keď máš C špagátotyčiek, môžeš si ich rozdeliť na A a B a potom sa pohrať samostatne s jednou A-ticou a s druhou B-ticou (t.j. každý takto skombinovaný časový interval je skutočne zrealizovateľný).

To však nepokrýva všetky možnosti -- napríklad, ak by si to aplikoval na 2 tyčky, mohol by si ich rozdeliť (iba) ako 1+1. Lenže s jednou dokážeš zmerať len 0, 1/2 a 1, a teda s dvoma by si mal vedieť len 0, 1/2, 1, 3/2, 2. Ako ale sám vieš, dá sa spraviť aj viac (napríklad 3/4) :-)

Radoslav Harman povedal(a)...

Peter: Super nápad! Tvoje "Monte Carlo" riešenie síce neumožňuje odmerať daný čas úplne presne, no aj tak sa mi veľmi páči, pretože je originálne. Navyše, Tvojim spôsobom by sa dal aspoň približne odmerať ľubovoľný časový úsek, zatiaľčo "štandardné" riešenia umožňujú odmerať len niekoľko málo časov.

Peter Mikloš povedal(a)...

Problém Petrovho riešenia je akurát ten, že tyče môžu byť úplne rozdielne, takže zo štatistického rozdelenia zisteného z jednej tyče podľa mňa nemožno uvažovať rovnaké aj pre druhú tyč.
Takisto Peter uvažuje, že zmeraný čas môžeme uchovať a následne s ním narábať, čo v reále pri zhorených tyčiach a absencii čohokoľvek iného nebude možné. Samotné horenie tyče/tyčí je totiž neopakovateľné meranie.

Charon ME povedal(a)...

"cas zapalenia tyce" = dlzka horenia prvych 0.000001m tyce v mieste zapalenia

misof povedal(a)...

No ja si pamätám, že po tom, ako som za mlada prišiel na "autorské" riešenie tejto úlohy, tak som sa s tou úlohou ešte hral ďalej. Ak trebárs máme nehomogénne lano, ktoré celé zhorí za hodinu, nie je problém odmerať napr. 20 minút: stačí, aby v každom okamihu lano horelo na troch miestach. Takže ho na začiatku niekde rozrežem (trebárs odhadnem tretinu) a potom zapálim jeden kus (trebárs ten dlhší) na oboch koncoch a druhý len na jednom. A potom vždy, keď mi jeden kus dohorí a z druhého ešte ostáva, tak rozrežem to čo mi ostáva a zase zapálim potrebný počet koncov. (A ak náhodou nemám čím rezať, nie je problém niekde v strede to lano zapáliť, počkať, kým prehorí, a prípadne jeden koniec uhasiť :) )

goober povedal(a)...

Tak Mišofovi teraz zakážeme (potenciálne) nekonečne veľa zapaľovaní :-)