100 узников, 100 коробок

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

Узники будут по одному заходить в комнату под присмотром тюремщика. После этого узник получает 50 попыток для того, чтобы найти в одной из коробок своё имя. Это означает, что он открывает любую коробку, читает имя на бумажке, кладёт бумажку обратно, закрывает коробку, выбирает следующую и так далее. После этого, независимо от результата, он возвращается к себе в камеру.

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

Оставлять какие бы то ни было знаки в комнате с коробками нельзя, тюремщик строго за этим следит. Можно даже считать, что тюремщик подготовил 100 идентичных комнат с коробками (с одинаковым распределением бумажек по коробкам).

Если каждый узник будет выбирать очередную коробку случайным образом, он найдёт своё имя с вероятностью 1/2. Вероятность того, что все 100 узников найдут своё имя, равна 1/(2^100), т.е. ничтожно мала. Могут ли они увеличить вероятность выигрыша, выбрав правильную стратегию?

3 дочери

Встретились два математика, и между ними произошёл такой разговор:
- У меня три дочери.
- Здорово! А сколько им лет?
- Произведение их возрастов равно 72, а сумма возрастов равна номеру того трамвая.
- Мне всё равно не хватает данных.
- Старшая любит мороженое.
- Тогда всё понятно.

Сколько лет дочерям?

Дмитрий Медведев и машина

Дмитрий Медведев привык возвращаться с работы домой на электричке. Каждый день ровно в 7 часов вечера он прибывает на электричке на свою станцию. Его жена каждый вечер выезжает из дома на машине с таким расчётом, чтобы ровно в 7 часов встретить мужа на станции и отвезти его домой.

Однажды, устав после бадминтона, Дмитрий Медведев отпросился с работы немного пораньше и приехал на свою станцию в 18:05, то есть на 55 минут раньше, чем обычно. Чтобы не ждать жену на станции, он пошёл пешком ей навстречу. Встретив жену по дороге, он сел в машину, и они вместе вернулись домой на 10 минут раньше обычного.

Во сколько раз скорость машины выше скорости Дмитрия Медведева?

12 монет, 3 взвешивания

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

Две старушки

Рано утром одновременно из пункта А в пункт Б и из пункта Б в пункт А навстречу друг другу вышли две старушки. Они встретились в полдень и пришли в пункты назначения в 4 часа и в 9 часов вечера того же дня соответственно. Во сколько они вышли утром?

Очередь - 2

На этот раз я немного отойду от темы блога и опубликую алгоритмическую задачу.

Как и в предыдущей задаче, Штирлиц и Мюллер по очереди стреляют по очереди. На этот раз в очереди N человек. Нужно написать программу, которая для каждого из чисел 0 <= N < 1000 вычислит, кто выиграет при оптимальной игре обоих игроков.

Сразу скажу, что решить эту задачу прямолинейным поиском в глубину не получится. Мой вариант на Java тратил больше 10 минут уже при сравнительно небольших N в пределах 40.

Очередь

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

Шары и коробки

n различимых между собой шаров случайным образом распределяют по n различимым коробкам. Сколько в среднем коробок останутся пустыми?

5 пиратов

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

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

Принимая решение, пираты руководствуются следующими приоритетами:
1. Каждый пират хочет выжить.
2. Каждый пират хочет забрать себе как можно больше.
3. При прочих равных условиях, каждый пират предпочтёт выкинуть другого за борт.

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

Камень и лодка

В изолированном пруду плавает лодка. Из лодки за борт выбросили тяжёлый камень, который сразу же утонул. Как при этом изменился (понизился, повысился или остался прежним) уровень воды в пруду?

Задача о палке - 2

Как и в предыдущей задаче, палку снова наугад ломают на три части. Однако, в этот раз "наугад" будет означать следующее. Сначала палку ломают в одной случайно выбранной точке на две части. После этого выбирают один из обломков и ломают его наугад в случайно выбранной точке.

Какова вероятность того, что из трёх полученных обломков палки можно будет сложить треугольник?

Задача о палке

Палку наугад ломают на три части. Какова вероятность того, что из полученных обломков можно будет сложить треугольник?

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

100 лампочек

Есть 100 пронумерованных лампочек с выключателями. Сначала некто зажёг все лампочки. После этого он переключил состояние каждой второй лампочки (т.е. лампочек с номерами 2,4,6...), затем переключил состояние каждой третьей, каждой четвёртой и так далее. Остановился он только после того как переключил состояние сотой лампочки.

Сколько лампочек осталось гореть после всей процедуры?

Неустойчивый многогранник

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

Существует ли выпуклый многогранник, неустойчивый на каждой из своих граней?

Кругосветный полёт

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

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

Пароли

Ночь. Тишина. Советская ракетная шахта. Часовой на КПП спрашивает у всех пароль. Система такая: часовой называет одно число, проходящий - другое. В кустах лежит американский шпион и слушает.

Идёт первый солдат.
Часовой: 28.
Солдат: 14.
Часовой: Проходи.

Идёт второй солдат.
Часовой: 22.
Солдат: 11.
Часовой: Проходи.

ЧукчаШпион был не дурак, поднялся с земли, гордо пошёл к посту.
Часовой: 42.
Шпион: 21.
Часовой: Попался! Надо было отвечать 8!

Вопрос: какая система получения отзыва по паролю?

Задача Ландау

Продолжите ряд букв: Р Д Т Ч П ...

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

К сожалению, когда мне впервые дали эту задачку (а было это в Буревестнике в 2007 году), я об этой истории не слышал, и нашёл ответ. Даже и не знаю, что теперь думать.

Список с петлёй

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

Примеры двух списков на рисунке:

За линейное время и константную память необходимо проверить, есть ли в списке петля. Количество элементов в списке заранее не известно.

25 лошадей

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

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

Автобус на неровной дороге

Дорога из пункта А в пункт Б идёт то в гору, то под гору, а горизонтальных участков нет совсем. В гору автобус едет со скоростью 30 км/ч, а под гору он развивает скорость 60 км/ч. Автобус совершил рейс из А в Б и обратно. Какова была его средняя скорость?

7 гирек

Можно ли заказать набор из семи таких гирек, чтобы ими можно было взвесить любой слиток золота весом от 1 грамма до 1 килограмма? Слиток золота весит целое число грамм, гирьки можно класть на обе чаши весов.

Эту задачу мой младший брат решал на собеседовании в Abbyy.

Автобус

В какую сторону (вправо или влево) едет автобус на рисунке, и почему? Рисунок симметричный. Автобус точно едет вправо или влево с ненулевой скоростью, поэтому ответ "стоит на месте" неправильный.

Золотая цепь

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

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

Получить 6 из 0

Как, используя единственный ноль и применяя к нему математические операции, получить в результате 6?

Средняя зарплата

Три программиста пошли после работы пить пиво. По ходу обсуждения тяжёлой и неказистой жизни они решили посчитать свою среднюю зарплату. К сожалению, они все подписывали NDA и не могут просто назвать свои зарплаты друг другу. Как им поступить, чтобы всё-таки посчитать среднюю зарплату?

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

Ситуация, когда кто-то узнаёт, например, что зарплаты остальных X и Y, но не знает, у кого какая, противоречит правилам.

Список со случайными указателями

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

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

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

Два яйца и небоскрёб

Ещё одна довольно известная задача, которую включают почти во все сборники задач с собеседований в Гугл.

У вас есть доступ в 100-этажный небоскрёб и 2 идентичных яйца неизвестной птицы. Никаких данных о прочности скорлупы нет: яйцо может разбиться, упав с первого этажа, а может остаться целым, упав с сотого.

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

Футбольный турнир

В футбольном турнире каждая команда сыграла с каждой по одному разу. Известно, что ровно треть команд хотя бы раз сыграла вничью. Из оставшихся команд ровно 3/4 хотя бы раз проиграли. Сколько матчей этого турнира завершились победой одной из команд?

Апельсины и яблоки

Перед Вами три ящика, на которые прилеплены таблички: "Апельсины", "Яблоки" и "Апельсины и яблоки". Известно, что все три таблички перепутаны, и ни одна не висит на своём месте.

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

9 точек

Расставьте на плоскости 9 точек таким образом, чтобы через них можно было провести 10 прямых, на каждой из которых лежало бы по три точки.

Верёвочный мост

Одна из самых известных задач с собеседований в Microsoft.

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

Каждый из путников может пересечь мост со своей скоростью. Первый делает это за 1 минуту, второй за 2 минуты, третий за 5 минут, четвёртый за 10 минут. Если по мосту вместе идут два человека, то они движутся со скоростью самого медленного из них.

За какое минимальное время путники могут переправиться через реку? Ответ "19 минут" неправильный.

Картинки

Продолжите ряд:

Закольцованный поезд

Несколько вагонов сцеплены кольцом: последний вагон прицеплен к первому. В каких-то вагонах горит свет, в каких-то темно. Вы находитесь в одном из вагонов и можете переходить из вагона в вагон и включать/выключать свет.

Как определить, сколько вагонов в кольце, если все вагоны неотличимы друг от друга, а начальное распределение тёмных и светлых вагонов заранее неизвестно?

Выбрать все числовые отрезки из таблицы

Для разнообразия, небольшая задачка по SQL.

У Вас есть таблица numbers из одной колонки num. Нужно написать запрос, который выберет все отрезки, на которые числа из таблицы разбивают числовую ось. К примеру, если в таблице есть записи 1, 3, 7 и 10, то в результате выполнения запроса Вы должны получить 3 строки: (1,3), (3,7) и (7,10).

Монеты на столе

Двое играют в следующую игру: они по очереди выкладывают на прямоугольный стол одинаковые монеты (в варианте для взрослых - ставят кружки пива). Проигрывает тот, кто не может сделать ход (т.е. тот, кто в свой ход не может найти места для монеты). Есть ли выигрышная стратегия у одного из игроков?

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

Знаменитость

Знаменитостью (celebrity) на вечеринке называется человек, которого знают все остальные присутствующие, а сам он не знает никого. (Нужно отметить, что если Петя знает Васю, то не факт, что Вася знает Петю).

Вы пришли на вечеринку, на которой присутствуют n человек, чтобы выяснить, есть ли на ней знаменитость. Вы можете подходить к очередному гостю и задавать вопрос вида "Простите, Вы знаете человека X?" и получать ответ да/нет.

Как выяснить, есть ли на вечеринке знаменитость, и если есть, то кто именно, задав минимальное число вопросов?

Есть более формальная версия задачи. Рассмотрим ориентированный граф G(V,E). Вершину v назовём стоком графа, если для любой вершины u отличной от v существует дуга (u, v) и не существует дуги (v, u). Требуется либо найти такую вершину в графе, либо указать, что её нет.

Домино

Кость домино представляет собой прямоугольник размером 2x1. На костях нет никаких обозначений, все они неотличимы друг от друга.

У Вас есть коробка размера 2xn, в которую помещаются n костей. Вы можете упаковывать кости плашмя, не помещая одну на другую. К примеру, если у Вас коробка 2x3 и 3 кости, то Вы можете упаковать их тремя различными способами:

Сколькими способами можно упаковать n костей в коробку 2xn?

По данным разведки, такую задачу дают на собеседовании в московском офисе Гугла.

Деление отрезка пополам

Вот и первая задача в этом блоге.

Все мы с детского садика знаем, как разделить отрезок на две равные части с помощью циркуля и линейки. А вот как разделить отрезок пополам, пользуясь ТОЛЬКО циркулем (без линейки)?

Hello World

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

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

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