Lámpák és kapcsolók II

on

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?

Megoldás

Nagyjából összeraktátok, de álljon itt egy összefoglaló is.

1. megoldás

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.

2. megoldás

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…

34 thoughts on “Lámpák és kapcsolók II

  1. @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?

  2. 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?

  3. Küldd be a megoldásodat, hátha a többiek tudnak rajta javítani.

  4. 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 ..

  5. 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.

  6. 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.

  7. Hmm, most látom, egy napról nincs szó a feladatban, mea culpa.

  8. @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…

  9. @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

  10. @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…

  11. “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.

  12. Sajnos aki bemegy a szobába, az nem tudja magáról, hogy első-e.

  13. É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.

  14. 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.

  15. 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…

  16. 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 🙂

  17. @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…

  18. @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.

  19. 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!?

  20. 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.

  21. 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 🙂

  22. persze ha 100 lámpa lenne, akkor nagyon könnyű lenne 🙂

  23. 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…

  24. @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

  25. 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?

  26. 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

Comments are closed.