Хочу вот изучить разные подходы к решению задач, а для начала попробую рассказать о своем. Я решаю задачи разного рода (математические, программистские, лингвистические) на дилетантском, но высоком уровне, судя по результатам, и мне это интересно, так что мучайтесь теперь — придется вам читать об этом.

Моя методика основана на наблюдении за информацией. Я смотрю, какая информация доступна и как ее можно использовать, аккуратно так в мозгу раскладываю: мы знаем это, это и это, а на выходе нам нужно вон то. Для задач, в основе которых лежит некоторый процесс, это вообще офигенная тактика — фиксировать, какая информация доступна на каждом шаге (или в каждый момент, в непрерывных случаях).

Вот и задачка, мне она понравилась, когда я ее решил. Пока не решил — думал, что она бредова по своей сути и все это неправда, но ведь решил же!

Есть 100 заключенных. Для них придумали испытание — в один конкретный день их рассадят по одиночкам (сейчас они все вместе сидят и могут договориться о плане действий), так, что они не смогут переговаривать, а потом по одному в случайном порядке станут заводить в комнату.

В комнате есть 100 закрытых коробочек, в каждой из которых бумажка с именем одного из заключенных (они не повторяются, то есть все каждое имя есть ровно в одной коробочке). Он может открыть любые 50 из них (но не двигать их, не отмечать ничего и так далее). Если ни в одной из открытых им нет его имени, то зек проиграл и казнят абсолютно всех (т.е., надо, чтобы не ошибся никто!).

Как сделать так, чтобы вероятность благоприятного исхода (не казни) была хотя бы 30%?

На первый взгляд, идиотизм какой-то: каждый найдет себя с вероятностью ½, итого вероятность того, что все найдут свое имя — 0.5 в сотой степени, ужасно мало. 30% это больше, чем 0.5 в квадрате, так что кажется, что тут кто-то ошибся или задача с унылым подвохом. Ан нет, все по-честному. Вот «эталонный», бугага, ход размышлений — моих.

Ну, для начала упростим задачу: пусть зеки и коробки пронумерованы числами от одного до ста. Еще заметим, что порядок следования зеков абсолютно ни на что не влияет (чтобы потом не путаться), а потом начнем следить за информацией.

Итак, в самом начале, пока чуваков не расселили, у них нет вообще никакой информации, кроме общего представления о ходе эксперимента.

В тот момент, когда зека заводят в комнату, а там сотня закрытых коробок, у него тоже никаких новых знаний не появляется: после каждого зека комнату приводят в первозданный вид, закрывают коробки и стирают тайные значки, если таковые были.

Потом, думаю я, ему всего лишь остается выбрать 50 коробок и поглядеть что в них. Поскольку информации нет, то он найдет свой номерок в половине случаев, и ничего хорошего в этом нет — всем зекам капец практически по-любому. Вот блин!

Значит, новая информация все-таки есть. Но при входе в комнату он ничего нового, по сравнению с тем, что знал ночью, он не узнает, а то, что он знает при выходе — содержимое открытых им коробочек — он никому не сможет рассказать, а ему самому это уже не поможет. Где же сраная информация? Она должна быть!

ААА!!11111111 (Тут должно наступить озарение. Хотя я обычно перед этим снова говорю, что задача — бред и идете вы нахрен).

Он же не обязан их одновременно открывать! И вот она, информация — после открытия первой коробки он знает ее содержимое. Пыщщь! Ватсон, мы на верном пути.

Теперь, когда мы знаем информацию, если еще не догадались, можно поглядеть, как ее использовать. Как можно использовать какой-то номер от одного до ста, который нам выпал почти случайно? Ну, наверное, открыть коробку, на которой он написан. А потом следующую и так далее, пока не исчерпаем лимит или зациклимся.

Если мы зациклимся, то придем в ту коробку, с которой начали; то есть, если мы зациклимся, нам попадется номер первой коробки. Опачки! Нам же нужен наш собственный номер! А значит, стоит начинать с коробки под собственным номером, и в том случае, если цикл, в который она входит, длинной меньше 51, то мы победили и все хорошо.

Итак, теперь, когда мы знаем алгоритм, надо подсчитать вероятность в самоутверждающих целях (ужасное скучное занятие — считать всякие комбинаторные фигни). Нам требуется, чтобы среди наших ста вершин не было ни одного цикла длиной 51 и больше; вероятность того, что среди 100 вершин нет ни одного цикла длины N равна 1/N (ну, там це из эн по ка надо подсчитать), ну и потом просто сложить 1/N при N от пятидесяти до ста, это что-то вроде 0,29, уж не знаю, сами считайте.

Офигеть, да? Хотя вам, наверное, пофигу. Или нет, раз уж дочитали до сюда. У таких задачек есть одно тупое свойство — хрен о них расскажешь кому, будут ведь зевать и называть (про себя) тебя ботаником.