За 4-ма: Предполагам 12 1/3 го получаваш като третият влязал(не третият ден, а третия различен затворник, който влиза за първи път) обявава край на играта. Но краят може да се обяви от първият и/или вторият, ако те са влезли след третият и преди 4-тият.
Тактиката е когато влизаш за първи път сменяш осветлението - така при първо влизане всеки знае четността си на влизане(тъй като 3-тият знае, че не е първи, то явно разбира, че е трети; вторият разбира, че е втори само ако е влязал 2-рият или 3-тият ден(иначе не знае дали не е 4-ти)). При всяко следващо влизане, ако лампата е различна от това дето е оставил последният път, то разбира, че поне още някой е влизал. Първият също така при следващато си не последователно влизане, ако завари същото осветление значи, че са минали 2-ма(т.е. влиза първите к дена и е оставил светнато, ако не е влязал на к+1 ден, то явно, че е влизал поне още един затворник, но ако когато влезе за втори път(първите к последователни влизания може да ги броиме за един път) и ако пак е светнато, то явно, че са минали още 2-ма след него(той вече е преброил 3-ма). След това ако види загасена лампа може да обяви край на играта). Вторият и четвъртият не знаят кои са, но могат да предполагат, че са втори(т.е. ще знаят поне двама са минали). При следваща смяна на осветлението, която забележат ще увеличават с 1-чка броят на хората, които са минали със сигурност (разбира се такова нещо може да се случи само на вторият, тъй като четвъртият е последният, който променя осветлението).
Би трябвало да може да се докаже, че очакването по горните съображния е към 10 7/9(но дали е оптимално не знам)
10 милиона симулации дават това:
The average is:10.7763614
min is:5
max is:62
array_10:7
array_50:10
array_80:13
array_85:14
array_90:16
array_95:18
array_99:24
А че няма как четвъртият винаги да знае, че е четвърти може да се докаже лесно:
Ако допуснеме, че винаги може да го знае, то ще имаме една функция f(x)->{0,1} за всяко х>=3, по която затворник като влезе за първият път в ден х ще знае дали е 4-ти или не. Това означава, че влезлият в ден х винаги ще знае, в какво състояние да остави лампата. Но ако влезе за първи път след третият ден и не е четвърти(така му показва функцията), то той няма да знае дали е 3-ти или 2-ри. Ако е 3-ти трябва да остави лампата в състояние f(x+1), ако е втори в противопложното състояние.
|