C, PHP, VB, .NET

Има 10 затворника, всеки от които е номериран с число от 1 до 10. Дадени са десет шкафчета, които са номерирани с числа от 1 до 10, както и десет карти, на които също са изписани числата от 1 до 10. Произволно във всяко шкафче е сложена по точно една карта.

Затворниците получават достъп до шкафчетата един след друг, като нямат право да комуникират помежду си. Всеки от тях получава право да отвори точно 5 шкафчета. Ако дори само един затворник не успее да открие своето число в отворените от него шкафчета, всички затворници ще бъдат екзекутирани. Ако всички затворници успеят да намерят своето число, всички ще бъдат освободени.

Намерете стратегия, с която затворниците да получат колкото се може по-голям шанс за свобода.

Решение: Очевидно е, че ако затворниците започнат да избират произволни шкафчета, всеки от тях ще има вероятност за успех от 0.5. Понеже затворниците са 10 на брой, това означава, че трябва да умножим вероятностите им, т.е.

[math]P_{случаен} = 0.5^{10} = 0.0009765625[/math]

Това означава, че имат по-малко от 0.01% шанс за успех. Никак не изглежда добре.

Вместо това затворниците измислили следния алгоритъм:

1. Затворник X винаги отваря първо кутия с номер X.
2. Всяка следваща кутия, която затворника ще отвори, ще бъде с номера на картата, която е намерил в предишната.

Твърдението е, че по този начин затворниците ще вдигнат шансът си за успех драматично до над 35%! Защо се получава така?

Нека разгледаме един примерен сценарий. В лявата колона съм сложил номерата на кутиите, а в дясната колона съм сложил номерата на картите:

Примерен сценарий 1:

• 1 - 8
• 2 - 10
• 3 - 2
• 4 - 4
• 5 - 7
• 6 - 6
• 7 - 5
• 8 - 3
• 9 - 9
• 10 - 1

Нека сега видим какво се случва със затворниците - показвам номерата на кутиите, които отварят, а в скоби картите, които са видяли.

Затворник 1: 1(8) -> 8(3) -> 3(2) -> 2(10) -> 10(1): намери своята карта, значи има успех!

Затворник 2: 2(10) -> 10(1) -> 1(8) -> 8(3) -> 3(2): успех!

Затворник 3: 3(2) -> 2(10) -> 10(1) -> 1(8) -> 8(3): успех!

Затворник 4: 4(4): успех!

Затворник 5: 5(7) -> 7(5): успех!

Затворник 6: 6(6): успех!

Затворник 7: 7(5) -> 5(7): успех!

Затворник 8: 8(3) -> 3(2) -> 2(10) -> 10(1) -> 1(8): успех!

Затворник 9: 9(9): успех!

Затворник 10: 10(1) -> 1(8) -> 8(3) -> 3(2) -> 2(10): успех!

Естествено в този момент можем да се усъмним, че примерния ни сценарий е нагласен. Нека направим една дребна размяна в него, като просто разменим две от картите - тези от кутии 10 и 4:

Примерен сценарий 2:

• 1 - 8
• 2 - 10
• 3 - 2
• 4 - 1
• 5 - 7
• 6 - 6
• 7 - 5
• 8 - 3
• 9 - 9
• 10 - 4

Сега ще видим как нещата се провалят от самото начало:

Затворник 1: 1(8) -> 8(3) -> 3(2) -> 2(10) -> 10(4): смърт!

Какво обаче можете да забележите веднага? То е, че ако затворника имаше не пет, а шест опита, то щеше да стигне до своята карта. И още - ако продължим да следваме алгоритъма, т.е. правим неограничен брой тегления, ние винаги ще зацикляме!

Разковничето стои именно в това зацикляне. Реално във всеки един от сценариите имаме по няколко циклични графи. В сценарий 1 те са общо пет на брой:

• 1 -> 8 -> 3 -> 2 -> 10 -> 1: общо 5 възела;
• 4 -> 4: 1 възел;
• 5 -> 7 ->5: 2 възела;
• 6 -> 6: 1 възел;
• 9 -> 9: 1 възел.

В сценарий 2 са четири на брой:

• 1 -> 8 -> 3 -> 2 -> 10 -> 4 -> 1: общо 6 възела;
• 5 -> 7 ->5: 2 възела;
• 6 -> 6: 1 възел;
• 9 -> 9: 1 възел.

Всеки един от затворниците започва да тегли карти попадайки в един от тези графи. При това няма как неговата карта да не се намира в графа, в който е започнал да тегли (докажете, че е така!). Проблемът е, че затворникът има право да прегледа само пет от възлите в графа - не повече. Съответно ако графът, в който е попаднал, има по-малко или равно на 5 възела, той гарантирано ще си извади картата. Ако обаче има повече от 5 възела, това ще е проблем и той ще загуби.

Остава да се провери колко от възможните [mathi]10! = 3628800[/mathi] комбинации на карти и шкафчета са такива, при които най-дългия граф е с по-малко или равно на пет възела. Компютърна проверка показва, че това са [mathi]1285920[/mathi] възможни, т.е. вероятността е:

[math]P_{стратегия} = \frac{1285920}{3628800} \approx 0.354365[/math]

Ето как вероятността им за успех се увеличи до над 35%!

Допълнителна задача 1: Проверете как стои положението с по-малко и с повече затворници;

Допълнителна задача 2: Опитайте се да изведете хипотеза за генерализираната задача с N затворници

Задачата е преразказана от вариант в книгата: So you think you've got problems.