Arszlán, Belián és Cipórián 97 másik "barátjával" együtt volt bezárva valahol. Egy napon az őrök mindenkit felsorakoztattak az udvaron.
– Emberek! Az elnök úr a születésnapjára való tekintettel mindenkinek kegyelmet igért, feltéve, hogy kiálljátok a következő próbát. Én ugyan egy cseppet sem bízom bennetek, de vezetőnk itt élet-halál ura, tehát tolmácsolom, amit nekem mondott.
– Van egy szoba a hatos szárnyon, amiben van két lámpa, és mindegyikhez egy-egy kapcsoló. Mostantól fogva időről-időre kiválasztok közületek valakit. Tetszőlegesen. Lehet, hogy valakit egymás után ötször is elviszek, lehet, hogy valakire jó ideig nem kerül sor. Előbb-utóbb azonban mindenkit kiválasztok majd. Ezt az embert beviszem a szobába, és engedem, hogy a kapcsolókon állítson, a lámpák világításáról meggyőződjön.
– Ha, és ez egy nagyon nagy HA, emberek… Ha ezután a rab azt mondja, hogy biztos benne, hogy már mind a százan megfordultatok a szobában, és tényleg eltalálja a dolgot, akkor másnap reggel mindenki amnesztiával hazamehet. Ha viszont téved, akkor, jómadarak, nincs több lehetőségetek.
– A továbbiakban teljesen elszeparálunk titeket egymástól, most azonban még kaptok egy kis időt arra, hogy tanácskozzatok.
Ezután az őrök elvonultak, a rabok pedig összedugták a fejüket. Végül három barátunk állt elő a győztes javaslattal. Mi lehetett az?
Nagyjából összeraktátok, de álljon itt egy összefoglaló is.
Arszlán a főnök, ő mindkét lámpát kapcsolgatni fogja, a többiek csak a "kettes" lámpát
Egy rab akkor kapcsolja fel a kettes lámpát, ha 1) még eddig nem kapcsolta fel, illetve ha 2) már korábban felkapcsolta, de azóta megváltozott az "egyes" lámpa állapota.
Arszlán a kettes lámpát mindig lekapcsolja, ebből tudja ugyanis meg, hogy legutóbbi látogatása óta jártak-e a szobában más rabok. Első látogatásakor átállítja az egyes lámpát is, hogy azok a rabok, akik esetleg előtte már jártak a szobában, újra kapcsolják fel a lámpájukat.
Az egész játék addig megy, amíg Arszlán össze nem számol 99 rabot.
Ez 100.000-es minta alapján kb. 10.520 látogatást vesz igénybe.
A rabok a lámpák állásához hozzárendelnek egy kettes számrendszerbeli számot (felkapcsolt lámpa:1, lekapcsolt lámpa: 0).
Ha az éppen bekísért rab nem tudja növelni az értéket túlcsordulás nélkül, akkor nem csinál semmit, egyébként megnöveli az értéket eggyel, ezt viszont legfeljebb 4 alkalommal csinálja meg.
Arszlán a többiektől etérően viselkedik. Ő mindig 00-ra állítja a lámpákat és összeadja az eddig látott értékeket.
Namost. Attól függetlenül, hogy Arszlán első belépése előtt jártak-e már rabok a szobában vagy sem, Arszlán számlálója előbb utóbb el fogja érni a 4*98+1 = 393-at. Ekkor azonban a skatulya elv alapján biztos lehet benne, hogy minden rab megfordult már a szobában legalább egy alkalommal.
A négyszeri kapcsolgatás azért szükséges, mert Arszlán nem ismeri a lámpák kezdőállapotát, így az első néhány (legfeljebb 3) kapcsolást nem tudja beszámítani az összegbe.
Az algoritmus futásideje, 100.000-es mintán vizsgálva kb. 13.909 látogatás…
Comments are closed.
Lesz majd visszaesőknek is egy lámpával?
Börtönlázadás!
@csakazertse: Úgy tudom, lesz. 🙂
@cooldavee: én csak 1 lámpával tudom megcsinálni 🙂
Van-e valami extra feltétel, vagy az feltételezhető, hogy amíg nem mondják,hogy stop, addig minden rab többször is a szobába lesz víve, persze véletlenszerűen, h kit mikor és hányszor?
Kissé gondolkodtam, de nem sikerült az általam ismert egylámpás megoldást drasztikusan feljavítani – mindössze annyira, h a zárkanyitások számának várhatóértéke ~harmadára csökkent.
A számot próbáltam levezetni, de annyira csúnya maradt, h inkább írtam egy szimulációt – így ‘véletlenszerű’ kiválasztással ~3500 lámpavizsgálat adódott. Ezt viszont nem igazán életszerű 🙂 egy napon kivitelezni – létezik lényegesen jobb megoldás is?
Küldd be a megoldásodat, hátha a többiek tudnak rajta javítani.
@Shadowrunner: feltételezhető.
A két lámpát kettes számrendszerbeli számokként fogják értelmezni a rabok, 0-3 megegyezés/értelemszerűen.
Arszalán kivételével mindenkinek csak annyi lesz a dolga, h ha a bent talált szám kisebb mint három, és még soha nem változtatott a kapcsolókon, akkor az értéket eggyel megnöveli.
Arszalán pedig megtanul fejbentartani egy 100-nál kisebb természetes számot, nulláról indul, és ha 0-tól eltérő számot talál a kijelzőn, azzal megnöveli a fejbentartottat, és a kijelzőt nullázza. Ha pedig eléri a 99-et – önmaga a századik – jelezhet, h már mindenki járt bent.
Azért sem írtam le, mert ha létezik jobb megoldás, annak is inkább csak a tényére volnék kiváncsi ..
Na ez egész jól hangzik, már csak egy probléma van: nem ismert a kapcsolók és lámpák kezdeti állapota.
Akkor talán marad a fenti, egyik kapcsolón a most már csak 0-1 szám, a másodikat pedig átbillenti Arszalán mikor először bemegy és számolni kezd. A többiek feltétele pedig módosul, h az általuk nem kapcsolható második kapcsoló állásának megváltozása esetén mégegyszer kapcsolniuk kell az elsőn (amikor az épp 0)
Ez viszont hozza a 10000 körüli vizsgálatot, ami 24 órában ~8 másodpercenként egy kapcsolás.
Hmm, most látom, egy napról nincs szó a feladatban, mea culpa.
@csakazertse:
Ez kétségtelenül jó megoldás.
A probléma csupán az, hogy Arszlánnak legalább 33-szor kell bemennie.
Biztosan van gyorsabb megoldás is…
@rusty: még akkor is, hogy ha a kezdeti állapota ismeretlen a kapcsolóknak?
Nem nagyon látok jobb megoldás, mint a fenti.
Ha nincs semmi extra trükk, akkor van 2 darab 2 állapotú jelző. Ez összesen 4 féle lehetőség, ennyivel kell megoldani az összes kommunikációt. Mivel nincs elég kombináció, hogy csak a lámpák állapotából megmondható legyen, hogy eddig mennyien voltak ezért legalább egyvalaki számol, és a lámpák állapotával kommunikálnak egymással.
Az, hogy nem ismert a kezdőállapot tovább szűkíti a lehetőségeket, mert itt már csak az egyik kapcsoló állapotváltozással lehet jelezni, hogy a számoló először volt a szobában így az addigi jelzések nem számítanak. Ekkor azok akik az állapotváltozás előtt már jeleztek, újra jeleznek, a többiek meg rendesen jeleznek 1x.
Ha kettő, vagy több személy számlálna, akkor azoknak valahogy egymással is kommunikálniuk kéne, ahhoz meg dedikált kapcsoló kéne nekik, így az már nem fér bele a kettőbe.
Persze, ha van valami trükk, hogy növeljük a kombinációk számát, akkor lehet bonyolultabb algoritmusokat is kitalálni, amik rövidebb idő alatt céltérnek
@Shadowrunner:
A kommentem kicsit elhamarkodott volt…
A kezdeti állapot nem ismerése valóban megnehezíti a dolgot.
Felmerül azonban a kérdés, hogy az első ember tudja, hogy ő az első?
Ezt fel lehet oldani azzal, hogy -mondjuk- az első órában bemenők 01-re állítják a kapcsolót, és utána úgy tesznek, mintha még nem jártak volna bent… (akkor is agy tesznek a az első órán belül esetleg többször is behívják őket)
Bár ezzel tovább nő a megoldás időtartama.
Ennél kell lennie egy jobb megoldásnak, de beleragadtam most ebbe a számolós algoritmusba…
“Ezt az embert beviszem a szobába, és engedem, hogy a kapcsolókon állítson, a lámpák világításáról meggyőződjön.” Tehát ha az első ember beállitja 0,0-ra onnan mehet a már emlitett (csakazertse 2009.11.23. 09:56:24 ) megoldás.
Sajnos aki bemegy a szobába, az nem tudja magáról, hogy első-e.
Értem, de nem is kell hozzá. Ha mindenki megfelelően kapcsolgat, a kiválasztott, pedig számol és 0,0ra állit. Amikor a kiválasztott ember először bemegy, akkor még nincs mit számolnia, csak 0,0-ra állit, és onnantól kezdve tudja majd számolni.
Ezzel csak az a baj, h akik A első bemenetele előtt járnak a szobában, azok honnan fogják megtudni, h újra kell billenteniük – legnyilvánvalóbb annak a problémája aki véletlenül 00 kiindulási helyzetben találja a kapcsolókat (nem tudván, hogy) elsőként.
igaz
Szerintem ezt lehet kivédeni azzal, ha az első órában mindenki 01-re állít, és utána úgy viselkedik, mintha még nem járt volna bent…
@rusty:
Gyakorlatilag 1 óra 1 perckor indul a (csakazertse 2009.11.23. 09:56:24 ) megoldás.
Időkorlátokat max az én hibás soraimból lehet eredeztetni – a feladat szerint lehet h nem is visznek be senkit első nap pl.
Sőt lehet h a rabok nem is tarthatnak órát 🙂
@csakazertse:
Ez esetben más irányba kell elindulni. A ‘módszert’ megöli az, ha nem ismert a kiindulási állapot.
Bár…
Ezt ki lehet védeni, ha nem 99ig, hanem 102ig számol, így, ha 11 volt a kiinduló pont, akkor is jó megoldásra jutunk…
@rusty:
csak nem tudja, hogy mikor kell megállnia, mert ha pl. 00-val kezdődött, akkor 99 fölé sose fog jutni, a 102-t nem fogja elérni.
Mindenkinek pontosan 4-szer kell jeleznie, és 396-ig kell a számolónak számolni. Igy, ha 00-val kezdődik, akkor pont 396 mindenki lesz 4-szer, azaz megvan, ha pedig 11 kezdődne, akkor 396-nál igazából még csak 393 részvétel volt, de az is garantálja, hogy legalább egyszer mindenki kint volt.
Ha pedig csak egy lámpa lenn, akkor mindenkinek kétszer kell jelezni és 198-ig kell számolni, ezt itt is meglehetne csinálni, de a 4-szer jelezni és gyakorlatilag hármasával számolni az gyorsabb.
Érdekes kérdés, hogy mennyi szobalátogatások számának várható értéke!?
Jópofa megoldás.
Dacára, h megengedtem, h minden bemenetelkor annyit adjon hozzá a belépő, amennyit csak tud (két lámpás esetben max 3) így is az első módszer a gyorsabb ~10.000:13.000 arányban – hacsak persze el nem rontottam a szimulációt.
Több lámpára meg még rosszabb az arány (az első 600, a második 10000 felé tendál) – ami persze nem ellensúlyozza, h 1 lámpával meg csak az utóbbi működik.
Valamint lehetne már új feladat 🙂
látom ..
persze ha 100 lámpa lenne, akkor nagyon könnyű lenne 🙂
Szerintem az 13000-ed nem jó, hiszen legalább 198-szor be kell mennie, ami kb 19800-ból jön össze, és ugye van amikor bemegy, de nincs jelzés.
És az elsőre nekem több mint 10000 jött ki, de mindjárt át nézem a képleteket…
50-es mintán 13900 az átlag az 4 kör 3 max jelzéssel.
@Kuszmák: akkor megegyeztünk a számokban? Midkettő több volt, csak a jónak tűnő jegyeket tartottam meg, sőt most nézem nagyvonalúan egyenesen kihagytam az A első bemenetele előtti részt, nagyságrendileg úgysem számít
Már bocs ha furcsát kérdezek, de ha nem kötelező kapcsolgatni a raboknak, például minenki csak első alkalommal kapcsol egyet, akkor Arszlánnak csak azt kell néznie, hogy hányszor történt egy kapcsolás, és 99-nél már szólhat is. Ez így túl egyszerű. Szóval tuti lehet olyat is, hogy valaki nem csinál semmit?
Mivel a kiindulási állapot nem ismert, amikor A először bemegy, nem tudja, h azért ég -e lámpa, mert vki már számolt egyet, vagy pedig ez volt a kiindulási állapota – valamint h ezután 99-ig vagy 98-ig kell -e számolnia