Logická úloha
Jdete po dlouhé kruhové chodbě. V pravidelných intervalech zde jsou zde žárovky, u každé je vypínač. Některé zhasnuté, jiné rozsvícené... To nevíme. Chodba je všude stejná, můžete zhasínat a rozsvěcovat žárovky. Jak podle toho co nejrychleji a nejjednoduššeni poznat, že už jste kruhovou chodbu obešli?
Odpovědi
Diskuze
Možná začít s jednou (nebo několika rozsvícenými za zády a žároky jednu po druhé zhasínat. Jakmile bude úplná tma, tak jsi kruh obešel.
Ale je taky (v případě fakt velké chodby) jistá pravděpodobnost, že ty žárovky už tak rozsvícené a zhasnůté (dle mého pravidla) budou při průchodu chodbou (ještě předtím než jsem jí prošel - prostě náhoda třeba). V takovém případě si nemohu být jistý, že jsem chodbu obešel a tudíž bych musel třeba na konec toho mého pravidla přidat třeba 2 rozsvícené žárovky, zapamatovat si přesně, kde jsem to udělal a projít chodbu podruhé. Pak při znovushledání se svým způsobem rozsvicování-zhasínání si můžu být na 99,99999999% procent jist že jsem právě 2x prošel chodbou :D
Jelikož mám rád takové uvažování a předpokládám chodbu třeba s několika miliony žárovek, nemůžu si být nikdy jist, že to co sem právě udělal (třeba znovu upravil pravidlo rozsvícených a zhasnutých žárovek) mně někde náhodou nečeká "předpřípravené", tzn. místo chodby, kde jsem ještě nebyl...
Jasně, ta šance je skoro nulová, ale někdo jako já (jestli se vůbec někdo takový najde :D ) by zmíněnou chodbou procházel asi do nekonečna, protože by nebyl s to uvěřit, že už chodbu obešel :D
No ale pokud bude kruh extrémně velký tak si nemůžu být ani jist je zhasnutá oblast je ten konec cesty (může to být jen anomálie na cestě - představte si ji dlouhou třeba několik kilometrů). Střídavé rozsvěcování je vnášení systému do chaosu. V přírodě také není nic systematické, příroda se vše hned snaží zamíchat. Takže náhodný jev nebude rozsvícení nastřídačku. Náhodný jev budou různé oblasti a rádoby pravidelnosti.
• a co rozsvícení systémem: 0,1,0,2,0,3,0,4,...
• Anonym458600: nebo jednu žárovku povolit - nerozbíjet - ale to také není logika :) vidím že rozbitá žárovka je pevným bodem ve Vesmíru :)
• pak jednu rozsvítíme, další zhasneme, a pak další rozsvítíme systémem: ...,0,1,0,1,0,2,0,3, až do N (až narazíme na sekvenci: 0,1,0,2,0,3,...), která by mohla být začátkem cesty v kruhu (...,0,1,0,1,0,2,0,3,...,N) (ale nemusela být)
• N si zapamatujeme - může to být několik miliard :) a vrátíme se zpět a až dorazíme k výchozí sekvenci začátku cesty 0,1,0,2,0,3,... a jestli je před 0 místo původní jedničky to naše velké číslo N: (...,N,0,1,0,2,0,3,...), tak jsme kruh obešli, pokud tam N nebude (bude tam jednička), vrátíme dopředu se k N a pokračujeme v řadě N,0,N+1,0,N+2,...
• a tak stále dokola dokud nenajdeme to velké N před začátkem sekvence (místo původní jedničky): ...,0,N,0,1,0,2,3,...,N,0,...
... omlouvám se za chaotický popis - ještě ho přepíšu srozumitelněji - pokud mě napadne lepší.
PS: Přešel jsem od původní představy chodby pozemské k chodbě galaktických rozměrů :) akorát nevím, kdo zaplatí tu elektřinu :)
Když to tak vidím, asi by to šlo ještě zjednodušit: začít třeba tou "značkou" ●●☼●☼☼●☼☼☼● (ta první zhasnutá je ta tvoje kontrolní, kterou zkoumám, když se vracím) a pak už prostě rozsvěcet všechny: ☼☼☼☼☼☼☼☼... (ta rostoucí sekvence je tam vlastně zbytečná). A pak už zase jak píšeš - jak narazím na ●☼●☼☼●☼☼☼●, vracím se a když před tou řadou rozsvícených najdu ☼●☼●☼☼●☼☼☼●, je dokonáno.
To vracení a kontrola, že si začínám ničit vlastní dílo, je asi klíčem k téhle záhadě. Ta značka by měla být "přiměřeně dlouhá", abych se nemusel vracet moc často...
Pěkná úloha :-)
PS: jsem zvědavý jestli existuje efektivní řešení