Я уже который день тут мусолю одну и ту же головоломку, но она все открывается новыми гранями. Читатель Даниил прислал ссылку на блог Терренса Тао, где формулировка задачи уже несколько иная, и в новом виде она лично мне совершенно взорвала мозг, хотя отличие совершенно пустяковое на первый взгляд. Теперь я могу с полной уверенностью назвать данную задачу моей любимой. Собственно формулировка:

На острове живет 1000 человек с идеальным логическим складом ума. Из них 100 имеет голубые глаза, и 900 — карие. Религия запрещает им знать свой цвет глаз и рассказывать другим о цвете глаз. Никаких отражающих поверхностей на острове нет. Если кто-то вдруг узнает свой цвет глаз, то он обязан в ближайшую ночь устроить публичное ритуальное самоубийство.

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

— [...] и я был очень удивлен увидеть здесь, в столь отдаленном уголке, голубоглазых людей [...]

Вопрос: сколько осталось жить голубоглазым и/или кариглазым островитянам?

Я могу сразу дать единственный верный ответ: на сотую ночь все голубоглазые островитяне совершат ритуальное самоубийство. Почему? Решение задачи такое же как и раньше. Один в один.

А теперь другой вопрос: но как же так может быть? Ведь то что на острове есть голубоглазые люди всем и так было заранее известно, их ведь аж 100 человек. Путешественник не сообщил никому никакой новой информации. Так какого черта им теперь надо заниматься самоубийствами?

Если поразмыслить, то оказывается, что теперь самоубийств все же не избежать. Решение я думаю появится в спорах в комментариях, ну либо позже я опять вернусь к этой задаче.

UPD: Опять же по наводке Даниила подробное решение задачи опять же Терренсом Тао. В частности интересен следующий аспект: решение, до сих пор представленное у меня в блоге, лишь указывает на гарантированный способ определить свой цвет глаз голубоглазому островитянину через 100 дней. Однако в течение этих 100 дней никакой новой информации они не получают, и возникает вопрос: зачем ждать? Не существует ли логики, по которой островитяне смогут определить свой цвет глаз раньше чем через 100 дней? Терренс Тао как раз в частности представляет доказательство для нижней границы по самоубийствам. Это изложение кстати занимает примерно 40 печатных страниц.

В комментариях к прошлой заметке в общем-то уже дали решение, но поскольку комментарии читают не все, то сделаю отдельную заметку, а заодно покажу модификации задачи, на которые указали комментаторы.

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

Про город на 50 семей:

В некотором королевстве проживает всего 50 семей. Во всех этих семьях мужья изменяют своим женам. Жены знают о том, что все мужчины изменяют, кроме собственного мужа. А дальше все так же как и в прошлой задаче. Королева делает объявление:

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

Вопрос: сколько осталось жить мерзавцам?

Про трех мудрецов:

Король выбирает себе советника из трех мудрецов. Он их зовет к себе и надевает каждому на голову шапку, которая может иметь черный или белый цвет, и дает им слово, что по крайней мере на одном надета черная шапка. Мудрецы видят шапки друг друга, но не видят свою собственную. Тот, кто первым назовет цвет своей шапки, становится советником (если называешь неправильно, тебя казнят как идиота). Вопрос: как будут поступать мудрецы?

Про более больше мудрецов:

Король созвал к себе всех мудрецов королевства, и решил проверить кто из них на самом деле мудрец, а кто идиот, и идиотов казнить за то что выдают себя за умных. Он надел всем мудрецам разноцветные шапки на голову. Все мудрецы могли видеть шапки на других, и объявил:

— Через равные интервалы времени будет бить колокол. В каждый удар колокола тот мудрец, который знает цвет своей шапки, должен встать и уйти. Если вы уходите в какой-то другой момент времени, вы идиот и вас казнят. Данное испытание справедливо: шапки я на вас надел таким образом, что вы все находитесь в равных условиях и каждый из вас может быть спасен, если вы и вправду мудры.

Ну а теперь собственно решение. Будем решать первую задачу, там где про изменников.

Во всех формулировках задачи женщины не знают достоверно сколько всего изменщиков в городе. Рассмотрим частные случаи:

— Пусть изменщик всего один. Тогда все женщины кроме его жены знают его, для жены же вообще становится полной неожиданностью, что в городе происходят измены. А раз она об изменах вообще ничего не знала, значит изменщик — это ее муж. В ту же ночь она его прикончит.

— Пусть изменщиков двое. Все женщины кроме двух знают, что изменщиков двое, а две женщины думают, что изменщик всего один. И каждая из этих двух женщин будет ожидать, что в ближайшую ночь та вторая, чей муж изменяет, прикончит подлеца, руководствуясь логикой того, что если изменщик всего один, его пристрелят в первую же ночь, как мы это видели только что. Когда же утром станет ясно, что все живы, значит изменщик никак не один, а двое, и жены, думающие ранее, что изменщик всего один, поймут, второй — свой же собственный муж. На вторую ночь изменщики погибнут.

— Если изменщиков три, как в первоначальном варианте задачи, то две женщины будут думать, что их только двое, и по логике для двух изменщиков, будут ожидать их гибели во вторую ночь. Когда же утром после второй ночи все останутся живы, то эти три женщины поймут, что изменщиков никак не может быть два, а на самом деле их три, и третий — их муж, о измене которого они ничего не знают. Таким образом ответ на первую задачу: женщины прикончат троих изменщиков в третью ночь.

— В общем случае если изменщиков человек, то женщин будут думать, что их всего и будут ожидать их гибели в ночь под номером . Когда же после этой ночи все окажутся живы, они поймут, что изменщиков на самом деле человек, и прикончат своих мужей. Таким образом для задачи на 50 семей, изменщики погибнут в 50-ю ночь.

Задачи с мудрецами мне меньше нравятся, так как там больше сомнительных тонкостей. Там где мудреца три (назовем их A, B и C), то логика мудреца A должна быть следующей:

— Пусть мудрец A видит на своих оппонентах белые шапки. Поскольку король пообещал, что хотя бы на одном есть черная шапка, логично, что шапка эта надета на мудреце A, который видит две белых шапки. Он называет цвет и выигрывает.

— Пусть мудрец A видит белую и черную шапку на оппонентах B и C соответственно. Если бы на мудреце A была белая шапка, то оппонент С по описанной только что стратегии уже бы назвал свой цвет. Раз он молчит, значит он не может сделать такое заключение,  и значит шапка на A черная.

— Пусть мудрец A видит на оппонентах черные шапки. Если бы на нем самом была белая шапка, то один из оппонентов по уже описанной стратегии назвал бы свой цвет. Раз они оба молчат, значит и на A шапка черная.

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

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

Однако король уточнил, что задача решается и все находятся в равных условиях. Значит информацию мудрецы могут откуда-то черпать, и единственный вариант здесь — увидеть свой цвет на ком-то еще. Это означает, что король шапку каждого цвета надел минимум на двух мудрецов.

Тогда стратегия получается следующей:

— Если мудрец видит шапку какого-то цвета лишь в одном экземпляре, то это значит, что на нем самом шапка имеет тот же цвет. По первому же звону колокола он уходит.

— Если мудрец не видит никакого цвета в единственном экземпляре, то на нем какой-то другой цвет. Допустим, что какой-то цвет он видит в двух экземплярах. Если после первого звона колокола эти мудрецы не уходят, это означает, что они оба тоже видят по два цвета шапок на головах, что значит что всего таких шапок три. По той же логике после второго звона колокола эти три мудреца уходят.

— По той же логике уходят и все остальные мудрецы, после того, как увидев шапок одинакового цвета, мудрецы одетые в эти цвета не уходят после -го звона колокола.

Что и требовалось.

(P.S. для  AkvaVita: ну так чего, будем трахаться?)

Услышал интересную задачку, говорят, что классическая, но ранее я не сталкивался. Услышал я ее в несколько уродском виде, поэтому я для блога ее переформулировал на свое усмотрение, чтобы звучала адекватнее. Надеюсь, никак при этом логику задачи не нарушил.

Но вот собственно задача.

В некотором королевстве, жители которого обладают безупречным логическим мышлением, живет некоторое количество семейных пар. Трое мужчин в королевстве изменяют своим женам, остальные честные. Информация и слухи в городе распространяются мгновенно и об этих изменщиках всем хорошо известно, кроме их жен: правила этикета горожан не позволяют закладывать мужей женам. То есть те жены, которым изменяют, знают об изменах других мужей, но не знают об измене собственного мужа.

И тут вдруг королева делает объявление:

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

Вопрос: сколько осталось жить мерзавцам?

Продолжаю кстати слушать онлайновые курсы по Computer Science. С момента как я в последний раз о них писал, они здорово видоизменились.

Во-первых, Себастьян Тран и компания запустили собственный проект Udacity. На самом деле этот проект несколько пока разочаровывает. Я прослушал (на самом деле прокрутил довольно быстро, выполнив всего пару заданий) курсы «Building a serach engine» (CS101) и «Programming a robotic car» (CS373, его просмотрел не до конца), и впечатление сложилось негативное.

CS101 оказался на редкость примитивным и мне показалось, что слишком уж примитивны он будет даже для новичка. То есть посоветовать никому я этот курс не могу на самом деле, хотя конечно мне сложно судить — сам с программированием я познакомился много лет назад, и рассуждать что лучше для новичка, не имея преподавательской практики, я конечно не вправе. Но то что курс не тянет на «top university level», как они себя позиционируют — это по-моему очевидный факт даже для CS101. Максимум — уровень среднеобразовательной школы (единственный плюс — изучается Python, а не какой-нибудь Basic или Pascal, как в России).

Домашние задания даже нельзя назвать тривиальными. Пяток программ типа «print 2+3» за неделю — это реально смешно. То есть никакой наработки практических навыков программирования курс не дает, для меня он оказался 100% бесполезным, что странно даже для CS101 — обычно лекторы в любой курс вставляют хотя бы какие-то факультативные факты, которые и для опытного разработчика оказываются новыми. Тут не было вообще ничего.

Короче я не доволен.

CS373 был чуть лучше, но тоже не особо. Задания крайне примитивные и часто вообще не на CS, а на какие-то отвлеченные вещи. Например, домашнее задание на реализацию фильтра Кальмана сводилось к тому, чтобы догадаться о размерности перемножаемых матриц, а смысл самих матриц даже в общих чертах не объяснялся — это полностью убило мою мотивацию слушать лекции Себастьяна далее. Никакой математики почти не рассматривается, а там где она вдруг появляется, она быстро пробегается мимо как что-то очень сложное, а затем опять разжевываются тривиальные вещи.

На все это наслаивается еще и ряд ошибок движка сайта. Половину домашних заданий мне не засчитали из-за каких-то проблем на сервере, причем проблемы эти похоже что не особо лечатся. Это конечно второстепенно, если нет цели получить их сертификат. Но сертификат их гроша ломаного не стоит и вряд ли кому-то сдался.

А вот Coursera произвела совершенно противоположное впечатление. Во-первых, к проекту присоединился целый ряд университетов, и помимо Стэнфорда свои курсы публикуют так же Princeton University, University of Michigan, Universoty of California, Berkley и University of  Pennsylvania. Сам состав курсов тоже значительно расширился: теперь это не только Computer Science и Enterpreneurship, но и медицина, история, социология, экономика, какая-то даже математика.

Из всех курсов, увы, я оказался спобен заниматься только Natural Language Processing. Качаю и остальные, конечно, но выполнять задания не успеваю — восьмичасовой рабочий день банально не позволяет слушать большее количество лекций. Начинал слушать Probabilistic Graphical Models, но не успевал и сконцентрировался на одном только курсе.

Вот эти курсы действительно оказались близки к «top university level». Во-первых, сам материал актуальный, интересный и не тривиальный. Курс составлен очень качественно и продуманно. Но помимо лекций, важны еще и домашние задания.

Одно из последних домашних заданий требовало находить в тексте имена людей. Это на самом деле нетривиальная задача: многие слова имеют двоякий смысл, например «Victoria» может быть именем девушки, а может означать победу, и если это слово стоит в начале предложения, то проверка того имя это или нет сильно затруднено. Так же могут использоваться клички и псевдонимы, которые тоже надо вычленять из текста как имена собственные.

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

Мне это сразу напомнило курс методов оптимизации в МИФИ. Там мы градиентным методом поиска искали экстремум функции . Причем я не шучу — это на полном серьезе называлось словом «лабораторная работа». В других институтах насколько я знаю ситуация с контентом курсов хоть и лучше, но тоже фатальна.

Курс NLP хорош тем, что дает реальные практические навыки в задачах, приближенных к реальным условиям (в отличие от курса CS101 Udacity, например, где мне плакать хотелось, особенно учитывая то что я когда-то немного читал учебник по Information Retrieval), и дает почувствовать масштаб реальных задач.

Еще полезный аспект — реальное применение каких-то математических концепций в Computer Science. Математика там конечно исключительно примитивная (логарифмы, вероятность, производная), но все равно забавно как применение какой-нибудь базовой теории вероятностей порой может кардинально повысить точность в сравнении с чем-нибудь совсем простым и очевидным. Если бы подобные курсы читались в технических ВУЗах, то ни у кого бы не возникало вопроса «а зачем мне это надо».

Ну и сами задания по программированию интересны. Я как-то писал, что в большинстве случаев довольно глупо требовать от учеников решения задачек — вместо этого надо выполнять проекты. Курс NLP почти целиком следует этому подходу (следовать ему целиком — сложная задача разработчика курса, и вероятно не всегда решаемая). В половине Programming Assignments не существует верного ответа, и вы можете рассчитывать лишь на некоторую точность работы вашей модели, выраженную в процентах (вернее, там почти всегда используется F1-мера, но это уже детали). У вас не получится догадаться какое должно быть решение и у вас не получится нащупать какой-то один заранее запланированный путь — вы именно сидите и думаете над реальной задачей, где решение не определено, а ваш балл получается не за ошибки в решении, а за его реальную применимость в жизни. И это очень круто (на самом деле существование решения конечно предполагается, и вам оно примерно известно из лекций, но и собственная творческая работа там довольно обширна).

Кстати, занятно, что многие из тех алгоритмов, которые рассматриваются в курсе, были разработаны еще годах в шестидесятых, но в те времена они не имели применений из-за отсутствия необходимых мощностей и объемов текстов в электронном виде. Сейчас это направление становится актуальным, и если предположить, что вычислительные мощности будут расти, эти направления скоро станут крайне актуальными и востребованными, и я например смогу рубить больше бабла. И это тоже хорошо.

Но это в общем-то главным образом про NLP. Остальные курсы я смотрел лишь мельком — там не везде есть Programming Assignments, но лекции тем не менее производят приятное впечатление. Так что всем рекомендую.

Подобная инициатива кстати есть и у MIT, но у них там пока только курсы по электрическим цепям, чего я не потяну. Помимо них конечно есть куча выложенных лекций в рамках проекта MIT OCW, среди которых есть хорошие, но там по большей части все же не полноценные курсы, а порой и вообще только заметки от руки или текстовая расшифровка лекций без формул, что конечно не имеет смысла.

Но собственно все это я написал, чтобы как-то прорекламировать. Всем настоятельно рекомендую. Coursera — это пожалуй наиболее полезный и интересный курс, который мне до сих пор приходилось слушать. Очень жалею, что не успеваю больше.

P.S. Очень извиняюсь перед всеми, кому не успеваю отвечать на почту или ВКонтакте. Меня жутко раздражают люди, игнорирующие письма, я это считаю довольно высокомерным и не приятным поведением, но я сам теперь стал таким. Пишут мне много, и я банально не успеваюсь, особенно на фоне того

Вот вам еще головоломка.

Есть три компьютера. Они запрограммированы отвечать на вопросы «да/нет». Предполагается, что компьютеры обладают всей информацией об окружающем мире.

Один из компьютеров всегда отвечает правильно на поставленный вопрос.

Другой компьютер всегда врет.

Третий компьютер отвечает всегда наугад (назовем его рандомным)

Вы не знаете какой из этих компьютеров какой, и вы имеете право задать лишь один вопрос одному из компьютеров.

Задача: задав этот самый один вопрос однозначно указать на компьютер, который отвечает правду или ложь, но не наугад (то есть задача указать на одного из нерандомных компьютеров).

Вот.

Наткнулся ВКонтакте на такую вот картинку:

Она была размещена в качестве прикола, но самое интересное, что здесь есть однозначное решение. В значительной степени это конечно довольно субъективно, так же как и все задачи из области «найди лишнее», но тем не менее.

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

Наверняка уже все знают, но чтобы никто точно не пропустил, тоже напишу.

Стэнфордский университет уже второй семестр подряд предлагает крутые бесплатные онлайновые курсы по разным тематикам. Представляют собой курсы видеолекции, быстрые «контрольные» на понимание базовых концепций, домашние задания, экзамены, форум для общения, иногда сеансы прямой связи с преподавателями, где можно задать интересующие вопросы.

В прошлый раз курсов предлагалось три:

1. Artificial Intelligence
2. Databases
3. Machine Learning

Внимание общественности главным образом привлек Artificial Intelligence по трем причинам:

1. Название курса «искусственный интеллект» звучит круто.
2. Ведут курс прославившиеся ученые Peter Norwig и Sebastian Thrun (у обоих послужные списки очень обширные, но общественностью наиболее была замечена попбеда в DARPA Grand Challenge робота Stanley, разработанного командой Себастьяна).
3. В конце обещали дать сертификат об окончании курса, что многими было воспринято чуть ли ни как диплом Стэнфорда (на деле это просто электронный документ, подписанный цифровой подписью Питера и Себастьяна, что к Стэнфорду никакого юридического отношения не имеет).

Собственно на деле курс по AI оказался наиболее слабым: слишком много времени уделялось подстановке цифр в формулы, слишком частные случаи рассматривались, слишком низкий уровень математической подготовки студентов предполагался, домашние задания сводились так же к подстановке цифр в формуле и не предполагали никакой интеллектуальной работы.

Это с одной стороны. С другой стороны как обзорный он вышел очень даже хорошим общеобразовательным. Там было дано и общее представление о регрессионных моделях, и алгоритм A*, и скрытые марковские процессы, и байесовы сети и куча всего другого. Это все сейчас постепенно становится теорминимумом для любого человека, который хочет заниматься программированием чуть на более высоком уровне чем программист 1С, и знать это такие штуки хотя бы существуют часто полезно (а подробности всегда можно посмотреть в Википедии).

Для сравнения, в МИФИ я отучился на CS четыре года и если бы не бунтовал, то был бы сейчас бакалавром. За время обучения я прошел несколько связных с AI курсов типа «Искусственные нейронные сети», «Цифровая обработка сигналов», «Анализ данных» и еще что-то  (все это очень условные названия курсов на самом деле, так, в курсе по нейронным сетям в том числе читались генетические алгоритмы как способ решения оптимизационных задач), но из всего перечисленного у нас были только регрессионные модели, да и те ограничивались простейшими видами — не было даже логистической регрессии, которая вообще самая базовая после линейной.

Итогом курса AI стало приглашение тысячи лучших студентов прислать авторам курса свое резюме. Правда, насколько я понял, рассылались приглашения только студентам из США, но мне в общем-то пофигу

Что касается курсов Machine Learning и Databases, то они оказались очень крутыми. Machine Learning слабенький в плане математики, но требует программировать на языке Octave (open-source аналог MATLAB) всякие вещи. Это довольно полезное занятие — материал лучше откладывается в мозгах и в общем-то изложенный материал становится понятным не только на уровне абстракций, но и как-то на уровне физических ощущений. Опять же как общеобразовательный курс, развивающий параллельно простые навыки работы в математических пакетах, очень он очень хорош.

Databases же вообще выше всяких похвал. С ними у меня всегда были проблемы — мне никогда не приходилось программировать ничего более-менее сложного, связанного с базами данных, а задания в соответствующем курсе в МИФИ были слишком тривиальны (уровня «вывести все университеты, на которых читается CS» без каких-либо изысков). Книжки и онлайн-лекции так же практики не представляли.

Стэнфордский курс очень краткий, сжатый, но содержит хоть какие-то интересные упражнения, при этом копает сразу на довольно глубокий уровень. Для меня это было просто то, что очень долго мне не хватало.

Кстати хотя этого и не объявлялось и не пиарилось, но курсы по Machine Learning и Databases в результате так же дали подписанные сертификаты, ни чуть не более худшие чем сертификат AI. А понимающие люди согласятся, что они и куда более серьезны.

Все эти курсы до сих пор доступны. Баллы за домашние задания уже не выставляются и сертификат не получить, но сами задания доступны, так что я бы всем заинтересованным очень рекомендовал пройти эти курсы — по базам данных вы вообще маловероятно что лучший источник найдете. Знакомство с Octave тоже может оказаться полезно. AI рекомендовать не могу — проще посмотреть список тем и почитать соответствующие статьи в Википедии. Хотя как простенький обзорный материал тоже можно использовать, но слишком уж лекции там затянуты.

(Кстати, справедливости ради надо сказать, что сам я в результате балл набрал невысокий — точно не помню сейчас, но что-то вроде 77% или около; я забил на часть домашних заданий, а что-то мне было лень считать).

В наступающем семестре Стэнфорд предлагает вообще огромную кучу курсов:

Lean Launchpad

Technology Enterpreneurship

Anatomy

Making Green Buildings

Information Theory

Model Thinking

CS 101

Machine Learning (повтор)

Software as a Service

Human-Computer Interaction

Natural Language Processing

Game Theory

Probabilistic Graphic Models

Cryptography

Design and Analisys of Algorithms

Computer Security

Пока сложно заранее предположить что это будут за курсы, но видя уровень уже прошедших курсов, есть ощущение, что по крайней мере часть из них будут охеренной. Жаль, что не получится слушать все. Записался я на все конечно, что именно буду слушать разберусь уже по ходу дела.

Возвращаясь к задачке, которую недавно публиковал. Там в принципе в комментариях уже было описано решение, но чисто формально я как бы наверное должен ее расписать отдельно, раз обещал. Условие я здесь не формулирую, если кто-то не помнит или просто все пропустил — пройдите по ссылке.

А решение простое, и чтобы его понять, достаточно разбить все норки на четные и нечетные, и рассмотреть начальное положение мышки в четной или нечетной норке отдельно.

Пронумеруем все норки цифрами от 1 до 5 и предположим, что мышка изначально находится в норке с четным номером, то есть с номером 2 или 4.

Суем лапу в норку 2. Либо мы ее поймали, либо она была в норке 4 и после может перебежать лишь в норки 3 и 5. Суем лапу в норку 3. Либо поймали, либо она из пятой норки теперь перебежала в норку 4. Суем лапу в норку 4 и ловим мышь.

Если после этих трех попыток мышь до сих пор не поймана, то это значит, что изначально она находилась в норке с нечетным номером. Однако при каждом перебегании она перебегает из четной норки в нечетную или наоборот, и следовательно после трех наших попыток, она в любом случае прибежит в четную норку.

Таким образом, если изначально она была в нечетной норке, то сейчас она гарантированно в норке с четным номером, и мы можем повторить проделанные действия еще раз и на этот раз уже точно поймать мышку.

В итоге наша последовательность засовывания лап в норку выглядит так:

2, 3, 4, 2, 3, 4

Но на самом деле конечно было бы интереснее, если бы норок было не 5, а, скажем, N. В этом случае задача решается аналогичным способом. Предположим изначально, что мышка находится в норке с четным номером, мы суем лапы во все норы подряд начиная со второй:

2, 3, 4, 5, …, N − 1

В предположении, что изначально мышка была в четной норке, эта последовательность в итоге ее дожмет за N−2 шагов. Если же изначально она была в нечетной норке, то надо теперь исходить из этого знания.

Если N нечетное, то мышка будет находиться теперь в четной норке и нам опять же достаточно повторить тот же процесс поиска еще раз.

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

Есть однако и более простой способ: если N нечетное, то после первой неудачи можно перенумеровать норки в обратном порядке и в этом обратном порядке мышка окажется в норке с четным номером. Теперь можно применять ту же процедуру, но только в отношении новой нумерации. Таким образом мы не совершаем одной лишней попытки найти мышку лишь бы загнать ее в четную норку. Результирующая последовательность попыток выглядит так:

2, 3, 4, …, N − 1, N − 1, N − 2, …, 2

Итого 2N−4 шагов.

Возникает резонный вопрос, а существует ли более оптимальная стратегия? Тут уже понадобиться не только смекалка, но и немножечко математики.

Каждый шаг игры мы имеем некоторую информацию о том, где теоретически может находиться мышка. Если подсчитать количество таких потенциальных норок, то можно ввести функцию «неопреденности», которая будет сообщать нам, относительно какого количества норок мы пока неуверенны.

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

5, 4, 4, 2, 2, 1, 0

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

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

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

Подробные выкладки приводить сейчас не хочется (придется писать до фига нудных вещей), но вообще довольно не сложно увидеть, что если у нас неопределенность в четных ячейках x, а в нечетных y, и мы обозначаем это парой (x, y), то в наиболее благоприятном случае если мы выбираем четную ячейку, то после нашей попытки мы получаем неопределенность (y + 1, x − 1). Если выбираем нечетную, то наоборот.

Здесь на самом деле куча деталей. Например, если N нечетное, а x = (N + 1)/2, то выбивая четную ячейку, у нас пара неопределенностей (x, y) перейдет в пару (y − 1, x − 1). Все подобные частные случаи наобходимо рассмотреть в отдельности  и понять когда они происходят.

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

Вот вам задачка, которую мне пару дней назад задал товарищ, и которая очень мне понравилась. Задачка в действительности не сложная, но интересная.

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

То есть игра сводится к тому, что попеременно кошка пытается угадать в какой норке находится мышка, а затем, когда кошка уже вытащила лапу, мышка перебегает в соседнюю норку. Остаться на месте мышка не может, обязательно должна перебежать.

Теперь вопрос: какая должна быть тактика кошки для того, чтобы гарантированно поймать мышку за какое-то разумное (конечное) число попыток.

Ответ наверняка кто-то приведет в комментариях, либо если никто не приведет, то я напишу его в следующем году.