Воскресный пост с задачками / Хабр

Привет, Хабр.

Идея такова: многие из нас любят поломать голову в свободное время. И многие знают много интересных задачек. Так почему бы всем этим скарбом не поделиться?

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

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

PS. Некоторые из этих задач ОЧЕНЬ известные, но тем не менее, то количество раз, что они мне попадались, обязывает меня написать и их.

Погнали?

Задача 1: Парадокс лжеца (куда без нее?). Она очень простенькая, как многие, конечно, знают. Но пост про задачи без нее был бы неполон.

Условие

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

Вопрос:

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

Ответ

Ответ: «Какую дверь мне скажет открыть другой из вас двоих?»

Решение

Решение:

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

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

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

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

Задача 2: В оригинале «Togglers». Назовем их «Перебежчики». Несколько расширенная задачка про лжецов.

Условие

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

Мы не знаем в каком «настроении» они находятся изначально. Но точно знаем, что если они один раз ответили правду, то в следующий раз соврут, и наоборот — если первый раз соврали, то потом обязательно скажут правду.

Но один из этих пяти не «перебежчик». Он всегда говорит правду.
Вопрос:

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

Ответ

Ответ:

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

«Ты всегда говоришь правду?»

Дальше:

— если мы получили ответ «Да», то следующий наш вопрос будет «Кто всегда говорит правду?»

— если мы получили ответ «Нет», то следующий наш вопрос будет «Кто „перебежчик“?»

Решение

Решение:

После первого вопроса мы можем получить ответы «Да» и «Нет». Рассмотрим что это нам дает:

— «Да» означает, что или мы попали на человека, который всегда говорит правду, или мы попали на врущего «перебежчика». Таким образом следующий ответ будет точно правдивым, а значит если мы спросим «Кто всегда говорит правду?» нам укажут на правильного человека.

— «Нет» означает, что мы попали на правдивого «перебежчика». А это значит, что он точно соврет в следующий раз. Значит на наш вопрос: «Кто „перебежчик“?», ему придется указать нам на единственного не «перебежчика» среди этой замечательной пятерки.

Задача 3: Про ящики с табличками

Условие

Перед нами три ящика с яблоками, грушами и в третьем есть и яблоки и груши. На всех ящиках есть замечательные таблички: «Яблоки», «Груши», «Яблоки и Груши».

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

Ответ

Ответ:

Достаточно достать один фрукт из ящика, на котором табличка «Яблоки и Груши»

Решение

Решение:

Так как мы знаем, что таблички неверны, то в этом ящике или яблоки или груши. Допустим нам попалось яблоко. Тогда мы снимаем табличку «Яблоки» с того ящика, на котором она висит и вешаем ее вместо таблички «Яблоки и Груши». Теперь у нас остался ящик, на котором красуется неправильная табличка «Груши» и у нас в руках табличка «Яблоки и Груши». Теперь переломный момент. Как разобраться куда вешать что? Очень просто. Используем условие, что мы знает, что ВСЕ таблички висят неправильно, а значит перевешиваем табличку «Груши» на ящик, на котором в самом начале было написано «Яблоки», потому что эта табличка никак не может остаться на своем месте. И вешаем табличку «Яблоки и Груши» на единственное свободное место.

Задача 4: Про торт и бесстыдную птичку

Условие

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

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

Какое минимальное количество разрезов нужно сделать бабушке, чтобы разрезать торт?

(Уточнение, это именно торт, не пирог. Его нельзя разрезать по горизонтали, так как тогда одному из внуков придется довольствоваться только кремом)

После вырезания куска торт, схематически выглядит так:

Ответ

Ответ 2

Решение

Решение:

Все линии проходящие через центр прямоугольника делят его площадь точно пополам.

Задача 5: Про лестницу (более сложный вариант этой задачи уже был на Хабре, вот тут)

Условие

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

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

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

Ответ и решение

Ответ и решение:

Заключенные должны выбрать какой нибудь цвет. Пусть это будет черный. Тогда верхний заключенный, номер 10, должен посчитать шапки черного цвета. Далее он должен сказать «черный» если шапок черного цвета было четное количество, и «белый», если шапок черного цвета было нечетное количество. Его жизнь, конечно же, не гарантирована. Ему может повезти, а может не повезти.

Тот заключенный, что под ним, номер 9, должен сравнить то, что видит он с тем, что сказал предыдущий. Допустим, первый сказал «черный». Далее есть два варианта:

— номер 9 видит четное количество черных шапок. Тогда он говорит «белый», потому, что количество черных шапок осталось тем же, а значит на нем белая. Это дает номеру 8 информацию о том, что черных шапок осталось четное количество.

— номер 9 видит нечетное количество черных шапок. Это означает, что он сам под черной шапкой. Тогда он говорит «черный» и номер 8 понимает, что теперь черных шапок нечетное количество.

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

Задача 6: Задачка про гномиков в шапочках:

Условие

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

Причем, гномики — существа довольно апатичные. Все, чем они занимаются в пещере — это сидят в кругу и смотрят друг на друга. Они даже не разговаривают и вообще никакой социальной жизни не ведут. Просто сидят, смотрят и о чем-то думают. Каждый гномик видит остальных 99 гномиков. Соответственно, каждый видит все шапки у всех гномиков, кроме своей. Каждый день, Белоснежка, чтобы не потерять любимых гномиков выводит их на построение перед пещерой. И каждый раз она говорит им: «Кто в голубой шапке — выйти из строя». Гномики, которые уверены на 100%, что на них голубая шапка после этого сделают шаг вперед. Если гномик считает, что его шапка может быть иного цвета, он останется стоять как вкопанный. Чтобы избежать замешательства добавим факт, что те гномики, которые из строя таки вышли переводятся в другую пещеру. Судить о том, что кого-то не хватает остальные гномики могут только когда вернутся в свою пещеру и сядут на свои места в кругу.
Вопрос:

Что будет происходить на построении, на какой день и почему, если мы знаем такие три вещи:

— Белоснежка, со скуки, надела на всех гномиков голубые шапочки.

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

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

Ответ

Ответ:

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

Решение

Решение:

Рассмотрим ситуацию не с сотней гномиков, а что нибудь попроще, скажет с одним гномиком.

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

Теперь рассмотрим вариант, когда гномика два. Они целый день сидят в пещере и смотрят друг на друга. Что они видят?

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

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

Эта же логика легко расширяется на произвольное количество гномиков.

Задача 7: Про два бокала:

Условие

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

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

Чего в чем больше — воды в вине или вина в воде?

Ответ

Ответ:

Одинаково

Решение

Решение:

Пусть в первом бокале (бокал 1) 8 единиц вина и во втором бокале (бокал 2) 8 единиц воды. Пускай ложка вмещает в себя 2 единицы жидкости. После того, как мы перелили чайную ложку вина из бокала 1 в бокал 2 мы получим:

бокал 1: 6 единиц вина

бокал 2: 8 единиц воды + 2 единицы вина

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

воды: 0.8 * 2 = 1.6

вина: 0.2 * 2 = 0.4

После переливания этой чайной ложки назад в бокал с вином:

бокал 1: 6.4 единиц вина + 1.6 единиц воды

бокал 2: 6.4 единиц воды + 1.6 единиц вина

Задача 8: Про ряд из лампочек. (за задачку спасибо nullbie)

Условие

В ряд стоят 100 лампочек.

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

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

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

Ответ

Ответ:

1 4 9 16 25 36 49 64 81 100

Решение

Решение:

Лампочку переключают те люди, порядковый номер которых является делителем номера лампочки. Потому лампочка останется гореть тогда и только тогда, когда в у ее порядкового номера нечетное количество делителей. Обычно делители «ходят» парами. Например, для числа 8:

8 = 1 * 8

8 = 2 * 4

То есть в этом случае, для лампочки с номером 8 – первый человек ее включит, второй выключит, четвертый снова включит и восьмой выключит.

Единственные числа с нечетным количеством делителей — полные квадраты, например 9:

9 = 1 * 9

9 = 3 * 3

Таким образом, у числа 9 есть 3 разных делителя, а значит лампочка с этим номером останется гореть. Аналогично для всех остальных полных квадратов.

Задача 9: Задача про площади.

Условие

Ответ

Ответ:

28

Решение

Решение:

Проведем прямую EF, которая будет параллельна прямым AB и CD (точка D внизу, она случайно обрезалась). Теперь, если будем двигать точку О в точку Т (пересечение зеленых прямых), то площадь треугольников не поменяется. Дальше все просто. Если кто придумает другое решение — я буду рад его услышать, потому что мое выглядит немного как костыль. Прошу прощения за качества рисунка, под рукой только телефон.

Решение 2

Решение 2: Спасибо за него Xitsa

Проведём дополнительные линии из точки в углы. После этого уже существующие станут медианами треугольников. 2 — 2 + 6 = 24 — 2 + 6 = 28

Задача 10: Заключенные и лампочка

Условие

В тюрьме сидят 100 заключенных. Надзирателям захотелось, как всегда, поразвлекаться и они придумали следующую «игру». Заключенных собираются в произвольном порядке с произвольной частотой водить в комнату, где есть только лампочка и выключатель к ней. Надзиратели также выбирают одного из заключенных (ответственный заключенный), которого при каждом приходе в камеру с лампочкой спрашивают все ли из этих 100 заключенных побывали в камере. Он может сказать, что он не уверен сколько угодно раз. Но, если он говорит, что, мол, да, все побывали, то происходит следующее. Если он не ошибся — всех отпускают, а если ошибся, то, как водится, казнят.
Вопрос:

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

Ответ и решение

Ответ и решение:

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

Задача 11: Задачка про фокусника и карты. (уже не помню где взял, но решал, когда 4 часа сидел в очереди за новым свидетельством о рождении. Не решил 🙂 (UPD: Задача вызвала большой ажиотаж, добавил уточнения в условии и новое решение для того условия, что было изначально)

Условие

Фокусник берет стандартную колоду из 52 карт, и отдает ее зрителям. Зрители выбирают (каким угодно способом) любые 5 карт и отдают их помощнику фокусника. Тот смотрит на карты и называет фокуснику 4 из них. В ответ фокусник называет пятую. Кроме мастей и значений карт, фокусник не получает никакой дополнительной информации (помощник говорит ровным голосом, без пауз и т.д.) (Уточнение: имелось в виду, что помощник не говорит фокуснику ничего кроме масти и наименования карт).
Вопрос:

Каким образом фокуснику удается «угадать» пятую карту?

Ответ и решение

Ответ и решение для варианта с уточнением:

Помощник получил от зрителей 5 карт. По скольку мастей карт всего 4, значит по крайней мере 2 карты имеют одинаковую масть. Эту масть и будет угадывать фокусник. Первая карта которую назовет помощник будет иметь ту же масть, что и карта которую надо будет угадать фокуснику(помощник в праве сам выбрать какую карту не называть). С мастью разобрались. Чтобы узнать тип карты, работает знаменитая система двоичного исчисления. Поскольку разных карт в колоде всего 13, а помощник будет называть 4 карты при этом 4 карты это 4 бита, то с помощью 4 бит можно изобразить максимальное число 1111, что в десятичной системе 1*2^3+1*2 ^2+1*2^1+1*2^0=1*8+1*4+1*2+1=8+4+2+1=15, то есть вполне достаточно для изображения 13 карт. Пусть 2=2,3=3,4=4…10=10, валет=11, дама=12, король=13, туз=14. Теперь для обозначения «1» карта называется так «сначала масть, потом сама карта», для обозначения «0» — «сначала карта потом масть».

Ответ и решение

Ответ и решение для варианта без уточнения:

Сначала выбираем две карты одинаковой масти. Пусть их значения x и y (по модулю 13). Вычисляем разность x-y. Если (x-y+13)%13>6, то отложим карту x, иначе отложим y. Назовём вторую из этих карт. Она определяет масть загаданной карты и диапазон из 6 вариантов значений. Так, если мы назвали вольта пик, то загаданной картой может быть только дама, король, туз, двойка, тройка или четвёрка пик.

Осталось три карты, которыми надо закодировать один из 6 вариантов. Заранее договариваемся о какой-нибудь функции сравнения карт в колоде, после чего 6 вариантов кодируются порядком, в котором мы назовём эти три карты. Если оставшиеся карты A, B, C, где A < B < C, то услышав последовательность X, A, B, C, фокусник назовёт X+1, услышав X, A, C, B — X+2,…, а на X, C, B, A скажет X+6.

И напоследок для настроения,
Задача 12: Про смотрящую корову (детская)

Условие

Знакомьтесь, это корова. Она смотрит.

Вопрос:

Как, переложив 2 спички, можно заставить корову смотреть в другую сторону?

Ответ и решение

Ответ:

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

10 логических задач с собеседований, которые заставят застрелиться

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

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

Автомат с напитками

Начнём с простой логической задачи.

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

Вопрос: сколько потребуется денег, чтобы определить, где какие автоматы?

Ответ

Потребуется одна монета, которую нужно бросить в автомат с наклейкой «случайный». Мы знаем, что это неправильная наклейка, поэтому это автомат с чаем либо кофе. После этого определяются остальные два автомата методом исключения. Например, если автомат выдал чай, то автомат с наклейкой «чай» на самом деле выдаёт кофе, а автомат с наклейкой «кофе» выдаёт случайный напиток.

Инопланетяне и десяток храбрецов

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

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

Вопрос: каким должен быть ответ, чтобы в живых осталось как можно больше людей?

Ответ

Люди должны договориться о следующем принципе ответов: отвечающий считает количество чёрных шляп у остальных людей. Если шляп нечётное количество, он называет «чёрный», если чётное — «белый». Следующий человек в ряду, видя шляпы остальных и зная чётность чёрных, может вычислить цвет своей шляпы. Например, если чёрных всё ещё нечетное количество, то на нём белая шляпа. С такой тактикой выживут 9 из 10 человек. Один же из них героически погибнет, спасая остальных.

Поездки на мотоциклах

У вас есть 50 мотоциклов с полным баком, которого хватает на 100 км езды.

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

Ответ

Самое простое решение, которое может прийти в голову — просто завести все мотоциклы и одновременно проехать на них 100 км. Но можно проехать и больше. Для этого сначала проедьте 50 км. Все мотоциклы будут с наполовину заполненными баками. Перелейте топливо с одной половины мотоциклов в другую половину. Теперь у вас 25 мотоциклов с полным баком. Проедьте ещё 50 км и повторите операцию. Таким образом можно проехать 350 км

3 лампы и 3 выключателя

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

Вопрос: как узнать, за какую лампу отвечает каждый из выключателей?

Ответ

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

Два стражника

А такая логическая задача часто встречается на интервью от Apple. Игрок дошёл до финального задания в квесте. Перед ним оказались две двери. Первая приведёт к богатству и победе, другая — к поражению. Под дверьми стоит по одному стражнику. Они знают, куда ведут их двери. Но один из них скажет неправду. Не известно, кто именно солжёт. Игрок может спросить одного стражника всего один раз.

Вопрос: что нужно спросить у стража, чтобы выйти к богатству и выиграть квест?

Ответ

У любого стражника нужно спросить: «какая дверь, по мнению другого стражника, ведёт к победе?». Если игрок спрашивает у правдивого стражника, то тот укажет на дверь с поражением, ведь второй стражник всегда врёт. Если же спросить у второго стражника, то он соврёт о мнении правдивого стражника и тоже укажет на дверь с поражением. Зная неправильную дверь, вам просто нужно выбрать другую.

Пьяные кролики

Как-то раз один наследник захотел убить своего короля, чтобы власть скорей перешла в его руки. У короля была 1000 бутылок вина его любимого сорта. Наследник послал убийцу, чтобы тот отравил любимое вино короля. 10) уникальных комбинаций состояний кроликов. Пронумеруем все бутылки в двоичной системе, для этого хватит 10 разрядов (в задаче нумерация регистров начинается с 1):

• 1-я бутылка = 0000000001
• 2-я бутылка = 0000000010
• 3-я бутылка = 0000000011
• …
• 999-я бутылка = 1111100111
• 1000-я бутылка = 1111101000

Кроликов нужно пронумеровать от 1 до 10. Каждый из них  будет соответствовать одному из 10 разрядов числа. Кроликов нужно поить из тех бутылок, где в соответствующем кролику разряде есть единица. Например, из первой бутылки пьёт только первый кролик; из третьей — первый и второй. Напоив кроликов из всех бутылок, нужно подождать один день. Номера кроликов, которые погибли, подскажут разряды числа, в которых должны быть единицы. Таким образом, если погибли только 3-й и 1-й кролики, то отравлена 5-я бутылка (0000000101 = 5).

Голодные белки

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

Вопрос: сколько желудей за 9 минут съедят 9 белок?

Ответ

Если вы не зависли на моменте «1.5 белки», то у вас есть все шансы осилить эту логическую задачку — завсегдатая собеседований. Нужно лишь иначе представить заданные условия. Если 1,5 белки съедают 1,5 жёлудя за 1,5 минуты, то 1 белка за 1,5 минуты съедает 1 жёлудь. Тогда 9 белок за 1,5 минуты съедают 9 желудей. Но по условию нужно узнать количество желудей, съедаемых за 9 минут:

1. 9 / 1,5 = 6 — во столько больше раз нам даётся времени;
2. 9 * 6 = 54 — столько желудей съедят 9 белок за 9 минут.

Треугольник муравьёв

Есть треугольник с равными углами. На углах стоят по одному муравью. В какой-то момент муравьи начинают идти в другой угол вдоль стороны треугольника. В какой именно — определяется случайно.

Вопрос: каков шанс того, что ни один муравей не столкнётся с другим муравьём?

Ответ

Может показаться, что вероятность 33%, но это не так. Есть два варианта необходимого движения муравьёв: по часовой стрелке и против. Давайте сконцентрируемся на одном муравье. После того, как он случайным образом выбрал направление, ему нужно, чтоб и остальные муравьи двигались в эту же сторону. Шанс того, что второй муравей пойдёт в его направлении — 50%. Аналогичная вероятность и у третьего муравья. Это значит, что общая вероятность того, что муравьи не столкнутся — 25%.

Котлета, котлета и ещё одна котлета

У вас есть 2 сковородки и 3 котлеты. На приготовление 1 котлеты с одной стороны уходит 1 минута. На одной сковороде вмещается лишь 1 котлета.

Вопрос: за какое минимальное время вы сможете полностью обжарить все 3 котлеты?

Ответ

Первым в голову приходит ответ — 4 минуты. Но можно уложиться и в 3 минуты. Для этого придерживайтесь следующей последовательности:

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

Необычная оплата

В поместье пришёл путник. В кармане — ни гроша, лишь одна золотая цепь из 6 звеньев. Хозяин поместья предложил брать плату в виде одного кольца с цепочки за один день проживания, при условии, что будет распилено только одно звено. Хозяин должен получать плату каждый день. Он не хочет принимать предоплату или давать в долг.

Вопрос: как путник должен распилить цепочку, чтобы вносить оплату за жильё каждый день в течение 5 дней?

Ответ

В условиях задачи не запрещался обмен звеньями цепи. Было лишь требование, чтобы с каждым днём у хозяина жилья прибавлялось одно звенье. Нужно распилить третье звено цепи, чтобы получить 3 части по 1, 2 и 3 звена. За 1-е сутки странник платит одним звеном. На 2-е сутки он платит куском из 2 звеньев и получает сдачу — одно звено (которым он расплатился за 1-е сутки). На 3-и сутки платит куском из 3 звеньев и забирает кусок из 2 звеньев. По такому принципу странник и должен оплатить все оставшиеся дни.

Заключение

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

А для любителей поломать голову мы подготовили тест на проверку логики и математики.

100 Головоломка с побегом заключенных

Вызов

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

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

Довольно маловероятно

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

Имея всего одного пленника, он имеет шанс 50:50. Есть 100 ящиков, и он может открыть (до) 50 ящиков в поисках своего билета. Если он откроет коробки наугад, он откроет половину коробок, и его билет будет или не будет в той половине, которую он открывает. Его шанс на успех равен ½.

С двумя заключенными, если оба выбирают случайным образом, это также будет иметь ½ шанса на успех у каждого, поэтому для двух заключенных это ½ × ½ = ¼. (Они добьются успеха один раз из четырех).

Для трех заключенных это ½ × ½ × ½ = &frac18;.

Со 100 заключенными это ½ × ½ × … ½ × ½ (100 раз) .

Это:

P _r ≈ 0,000000000000000000000000000008

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

Невероятный ответ

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

Решение

Сначала я объясню решение, затем объясню, почему оно работает.

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

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

Прелесть этой головоломки не в том, чтобы знать решение, а в том, чтобы знать, почему решение работает!

Почему это работает?

Длина цепочки

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

Если максимальная длина цепи меньше пятидесяти ящиков, то все успешны!

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

Шанс на длинную цепочку

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

Pr _win = 1.0 — Pr _{вероятность цепочки длиннее 50}

Немного математики

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

Вероятность того, что все заключенные получат свой билет, составляет 31,18%

Ниже приведен график, показывающий вероятности (по оси Y) для всех цепочек длины l (по оси x). Красным показаны все отказы (кривая здесь — просто график 1/l ). Зеленый показывает успех (вычисления для этой части графика немного сложнее, так как существует несколько способов определения максимальной длины < 50). Суммарная вероятность полос зеленого цвета составляет 31,18% вероятности побега.

Изображение: Quartl (Википедия)

Гармонические Числа (Необязательная часть для компьютерщиков)

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

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

Доведено до предела, если вместо 100 ящиков мы имеем сколь угодно большое число ящиков (скажем, всего у нас 2n ящиков).

Постоянная Эйлера-Маскерони γ сокращается.

По мере увеличения числа заключенных, если тюремщик по-прежнему позволяет им открывать до половины ящиков, процентная вероятность выживания асимптотами достигает 30,685%

(Если вы выбрали чисто случайное угадывание, то при увеличении n вероятность побега падает практически до нуля!)

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

Логическая головоломка зеленоглазых и важность метаинформации | by Bảo Lê Đức

Изображение из видео Ted-ed

Итак, я наткнулся на логическую головоломку Green-eyed от Ted-ed, которая гласит:

1. На острове есть 100 заключенных, у всех зеленые глаза.
2. Все 100 заключённых в совершенстве владеют логикой.
3. Все они хотят сбежать с острова.
4. Условие побега с острова состоит в том, что можно определить цвет собственных глаз и сообщить ответ охранникам в полночь. Если ответ правильный, заключенный освобождается. В противном случае его/ее убьют.
5. Ограничения таковы: никто из них не знает цвет своих глаз (через зеркала, отражающие поверхности или иным образом), и никому из них не разрешено общаться друг с другом каким-либо образом.
6. Однако они могут видеть друг друга и знать цвет глаз всех остальных.

Вы гость у владельца острова (теперь он называется IO). Вы хотите освободить всех заключенных. IO позволяет:

1. Сделать одно и только одно заявление в виде объявления всем заключенным.
2. Заявление не содержит никакой новой информации.

Вопрос:

Вы сказали:

«По крайней мере, у одного из 100 из вас зеленые глаза».

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

Почему ?

Photo by Olav Ahrens Røtne on Unsplash

Для популяции из 100 заключенных естественной реакцией является, конечно, доказательство по индукции.

Базовый вариант

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

Абель подумал про себя:

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

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

Шаг индукции

Теперь задача решена для 2 заключенных. Добавьте третьего заключенного, Сета, в бассейн.

Сет подумал про себя:

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

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

Следуя той же логике, все 100 заключенных сбегут в 100-ю ночь.

И все живут долго и счастливо. Правильно?

Photo by Ludovic Migneault на Unsplash

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

Как будто идеальному логику нужно, чтобы кто-то напомнил ему о чем-то, что он уже знал.

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

Снова повторим доказательство по индукции.

Базовый вариант

Теперь Каин и Авель впервые видят друг друга. Каждый из них знает, что у другого зеленые глаза.

Абель подумал про себя:

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

Будь я проклят.

Каин тоже. Они не убежали.

Авель и Каин уничтожены ФАКТОМ и ЛОГИКОЙ Бена Шапиро

Итак, какая разница в сообщении посетителя?

Без сообщения Авель не знает, знает ли Каин, что есть хотя бы один зеленоглазый заключенный.

С сообщением, он делает.