pondelok 18. októbra 2010

Hádanka o výťahu

Často k nám príjdu na návštevu priatelia. Vchod do domu sa nedá otvoriť z bytu, preto musíme ísť každého návštevníka vpustiť a potom zas vypustiť. To sa človek načaká na výťah...

Hádanka o výťahu
V Petržalke je veľa vysokých bytoviek. Predpokladajme, že žijete v osemposchodovom paneláku. Všetci susedia, okrem tých z prvého používajú výťah vždy keď niekam idú, aj keď sa vracajú domov. Susedia sú taký generický šedý priemer a všetci chodievajú von zhruba rovnako často. Výťah sa pohybuje rýchlosťou jedného poschodia za štyri sekundy. Obyvatelia ktorého poschodia sa v priemere načakajú najmenej? Koľko sekúnd?

Zaujímavé by mohlo byť vyriešiť úlohu aj vo všeobecnosti - pre n poschodí.

Samozrejme, ten úvodný problém s otváraním vstupnej brány pre návštevy sme vyriešili inak...

7 komentárov:

Matus povedal(a)...

No, zapísal som dve A5ky, ale myslím, že som to vypočítal všeobecne.
Nechce sa mi to rozpisovať, ale pre 8 to vyšlo najvhodnejšie byť buď na 4. alebo 5. poschodí (pre obe doba čakania 80 sekúnd v priemere).

Všeobecne je najvýhodnejšie poschodie celočíselná hodnota nasledujúceho: (n+1)/2, kde n je počet poschodí. V prípade, že je (n+1) nepárny sa dá zaokrúhliť buď nahor alebo nadol, mali by vyjsť rovnaké doby čakanie, keďže ide o parabolu (funkcia čakania pri chcení ísť dole).

Ak by si chcel, môžem to spísať a poslať ti to mailom, ako som to počítal :)

Matus povedal(a)...

Hodil som výpočet na Scribd: http://www.scribd.com/doc/39917349/Hadanka-o-v%C3%BD%C5%A5ahu

rasťo povedal(a)...

Cau metjush, tesim sa, ze ta uloha chytila. Pocuj, zda sa mi, ze si tam nastavil nejaky private setting, neda sa ten subor pozriet...

Ale zatial len taky common-sence check: 80 sekund je nejaky pridlhy cas, ved ked 4 sekundy trva 1 poschodie, tak cela cesta z prizemia na 8. poschodie trva 32 sekund...

No, kazdopadne som zvedavy na tie vypocty, urcite sa to bude dat doladit! :-)

Matus povedal(a)...

Okej, dal som to už public, nejako mi ušlo, že je to ešte stále private.

A no... :D nejako mi nedošlo, že je to nejako veľa :P Ešte si to pozriem, či tam nenájdem nejakú chybičku.

Charon ME povedal(a)...

asi to nie je sucastou tohto zadania, ale v reali ludia obcas cakaju aj kvoli tomu, ze niekto iny prave pouziva vytah, pripadne sa naakumulovali vacsie skupiny ludi a nezmestili sa vsetci naraz, tak musia chodit po davkach. Potom by v zadani bolo potrebne aj uviest, ako casto ludia chodia, ale tam zavisi aj od distribucie.

A este mi nie je celkom jasne, ci je tam aj prizemie a ci na nom niekto byva. Ked predpokladam ze vytahom sa dole chodi na prizemie a ak vytahom chodia aj ti, co byvaju na prvom, tak mi vyslo ze najvyhodnejsie je byvat na prvom nezavisle od poctu poschodi.

Jano H. povedal(a)...

Ja som uvazoval nasledovne:
Na prizemi nikto nebyva, vytah je vzdy volny ked niekto niekam potrebuje ist a nahodne sa vyskytuje na poschodiach.

Dalsia mimoriadne dolezita uvaha je ze kedze ludia rovnako casto chodia von aj domov (kazdy kto vyjde von, musi sa aj vratit), tak s polovicnou pravdepodobnostou sa vytah nachadza na prizemi, teda 0. poschodi, a s polovicnou pravdepodobnostou na niektorom z poschodi 2 - 8. (Cize na kazdom s pravdepodobnostou 1/14 aby to dalo dokopy 1.)

Potom som si vyjadril tabulku casov, kolko musia cakat na vytah na kazdom z poschodi ak je vytah na lubovolnom inom poschodi a podla pravdepodobnosti som to zmiesal. Vyslo mi ze najmenej caka 2. poschodie a to v priemere 10 sekund, najviac 8. poschodie a to v priemere 22 sekund. Ostatne poschodia vysli v zlomkoch medzi tymito dvomi hodnotami vzostupne, cim vyssie poschodie, tym vyssi cas.

rasťo povedal(a)...

Dakujem za vsetky komentare. Jano H. to nakoniec zratal presne tak, ako som ulohu myslel :-)

Charon ME: hej, nemyslel som na vacsi pocet osob, a myslel som klasicku panelakovu situaciu - na prizemi sa nebyva a ludia z prveho chodievaju pesi (v niektorych druzstvach su dokonca vynati z platenia na vytah a vytahove dvere na 1. posch. su zamknute...).