Ультрасложная задача про шляпы
Есть 4 очень логичных математика, и есть 4 шляпы — 2 красные и 2 синие. Троих поставили друг за другом, а четвёртого — за стену. После этого каждому надели на голову шляпу, и никто не знает, какого цвета шляпа на нём надета. Математики не могут поворачиваться друг к другу и не могут говорить ничего до тех пор, пока хотя бы один из них точно не скажет, какого цвета на нём шляпа. Всё, что может произнести каждый, — цвет своей шляпы, и то только тогда, когда он в этом стопроцентно уверен. Если он ошибётся — все проиграли.
Сможет ли хоть один математик точно назвать цвет своей шляпы?
Очевидно, что ни третий, ни четвёртый математик не видят ничего, кроме стены, поэтому они не смогут сделать никаких выводов:
Два оставшихся математика прикидывают, какие вообще комбинации шляп могут быть. Всего расставить 4 шляпы двух цветов можно шестью способами:
Второй математик смотрит на цвет шляпы третьего и видит, что она — красная. Это значит, что можно вычеркнуть все варианты, где красная шляпа не стоит на третьем месте:
Точно так же рассуждает и первый математик. Он уже понял, что второй сократил список комбинаций до трёх. Но у первого впереди синяя шляпа:
Это значит, что первый математик может вычеркнуть ещё одну комбинацию, где синяя шляпа не стоит на втором месте. Теперь у него осталось только две комбинации, но точный ответ первый математик до сих пор не знает:
А теперь самое сложное и интересное. Раз все молчат, включая первого, то второй математик понимает, что первый в замешательстве и не может дать точный ответ. Второй понимает, что если бы первый математик видел перед собой две красных шляпы, то сразу бы дал ответ, что на нём — красная. Но он молчит. Это значит, что он видит последовательность из синей и красной шляпы, а таких вариантов всего два:
Но в обоих этих вариантах на втором месте стоит синяя шляпа, поэтому второй понял, что на нём — тоже синяя шляпа. И как только он это понял, то сразу сказал, что на нём синяя шляпа.
Л — логика.
Задача про хакатон и неразбериху с местами
На хакатон пришли программисты, все сели на пуфики по 4 человека, но четверо осталось стоять. Подумав, программисты развернули пуфики, сели по 6 человек на каждый, и тогда 4 пуфика остались свободными.
Сколько всего людей пришло на хакатон?
Обозначим количество участников хакатона за x. Если на каждый пуфик сели по 4 человека и ещё четверо остались стоять, получается, что на пуфиках было x − 4 человека, а всего пуфиков было (x − 4) / 4.
С другой стороны, если после разворота пуфиков на каждый сели по 6 человек и 4 пуфика остались пустыми, получается, что всего пуфиков было (x/6 + 4).
Так как количество пуфиков неизменно, то мы можем приравнять обе формулы друг к другу:
(x/6 + 4) = (x − 4)/4
Решаем уравнение — умножим сначала обе части на 4, чтобы избавиться от деления:
4(x/6 + 4) = x − 4
2x/3 + 16 = x − 4
x − ⅔x = 16 + 4
⅓x = 20 → x = 20 × 3 = 60
Выходит, что на хакатон пришло 60 человек.
Сила компьютера в том, что он может быстро перебрать много вариантов решения и сразу найти нужный ответ. Всё, что нам нужно сделать, — объяснить в коде, как это сделать.
Напишем на JavaScript простой скрипт, который переберёт разное количество участников хакатона и по очереди проверит, подходит ли это число как решение или нет. Если подходит — выводим, если нет, то переходим к следующему. Проверку решения возьмём как в математическом решении — сравним обе части уравнения, и если значение совпадает, то это и есть верный ответ.
Для простоты представим, что в хакатоне участвует миллион программистов — компьютеру всё равно, сколько человек проверять, а нам будет спокойнее, что мы точно найдём решение.
// перебираем по очереди разное количество программистов на хакатоне
for (let x = 0; x <= 1000000; x++) {
// если обе части условия равны
if ((x / 6 + 4) == ((x - 4) / 4)) {
// то это значит, что мы нашли решение, поэтому выводим его на экран
console.log('В хакатоне участвовало ' + x + ' человек')
// останавливаем цикл, если нашли решение
break;
}
}
Как в офисе обойти всех программистов по одному разу
А вот вам логическая и математическая задачка.
В одной ИТ-компании офис разбили так, чтобы у 15 программистов и менеджера было по своему кабинету. Для этого офис разделили на 16 помещений и сделали сквозные двери в каждом кабинете. Менеджер сидит в первом офисе, а общий вход и выход — через кабинет № 16:
В конце рабочего дня менеджер решает обойти всех программистов, чтобы узнать, что они сделали за день. Он не хочет встречаться с одним и тем же программистом дважды и хочет построить маршрут так, чтобы встретиться с каждым по одному разу и финальным шагом выйти через общую дверь. Какой маршрут ему нужно построить?
Математическая теория говорит про это так: невозможно в такой конфигурации обойти каждый кабинет только один раз, чтобы выйти из кабинета № 16. Чтобы это доказать наглядно, раскрасим кабинеты как шахматную доску:
Каждый шаг между кабинетами — это перемещение с белой клетки на чёрную и наоборот. Нам нужно пройти 15 кабинетов, а значит — сделать 15 ходов. Если количество ходов нечётное, то старт и финиш будут на клетках разного цвета:
- один ход: с белой на чёрную;
- два хода: белая → чёрная → белая;
- три хода: белая → чёрная → белая → чёрная и так далее.
Но у нас клетки 1 и 16 одного цвета, а значит, дойти до финиша без повторений и возвратов не получится. Такая теория, кстати, работает для всех шахматных досок с размерностью N×N, где N — чётное число.
Получается, что у этой задачи нет решения даже в теории и менеджеру придётся заглянуть к кому-то дважды.
Хитрость в том, что в задаче нас просят не обойти каждый кабинет один раз, а встретиться с каждым программистом один раз:-) Это сразу меняет дело, следите за руками:
1. Менеджер переходит в кабинет 2 и встречается там с программистом.
2. После этого он возвращается в свой кабинет, который пустой — там никого нет, поэтому менеджер там никого не встретит. Это ключевой момент решения: пустой кабинет позволяет нам увеличить количество шагов на единицу, чтобы обойти ограничение теории из предыдущего раздела. Таким способом мы делаем 16 шагов, и это значит, что первая и последняя клетка должна быть одного цвета, как нам и нужно.
3. После этого менеджер обходит остальные 14 кабинетов и заходит в каждый по одному разу. Всего таких маршрутов будет 4:
Задача про спикеров: в каком порядке выступать, чтобы оно прошло успешно?
Руководители одного ИТ-стартапа решили выступить на конференции и рассказать о своём проекте, чтобы получить новые инвестиции. Они выяснили, что если спикеры будут выступать в определённом порядке (Алексей → Борис → Владимир), то шансы на успех сильно вырастают. Но в конференции, кроме них участвует, ещё 5 человек, а организаторы не могут сказать заранее, кто за кем выступает.
Каковы у руководителей ИТ-стартапа шансы на то, что спикеры выступят в нужном порядке? То, что между ними, до или после них могут выступать другие спикеры, не влияет на успех, главное, чтобы сохранился общий порядок выступления.
Эта задача может показаться сложной из-за дополнительных спикеров, но на самом деле решается она довольно просто. Для решения нам понадобится правильный порядок выступлений, поэтому обозначим его по первым буквам их имён: А → Б → В.
Если у нас три спикера, то всё просто: порядок будет А → Б → В. Теперь добавим четвёртого, которого обозначим за х — он может выступить так:
- x → A → Б → В
- А → х → Б → В
- А → Б → х → В
- А → Б → В → х
Получается, четвёртый спикер может выступить четырьмя разными способами — это значит, что если добавим его, то у нас уже будет 4 варианта успешного выступления.
Теперь добавим пятого спикера — он может выступить на одной из 5 позиций — в начале, между каждым существующим спикером и в самом конце. Получается, пятый спикер даст нам ещё 5 вариантов.
По этой схеме, шестой, седьмой и восьмой спикер дадут нам 6, 7 и 8 новых вариантов выступлений. Получается, общее количество выступлений, при которых сохраняется выбранный порядок — 4 × 5 × 6 × 7 × 8.
Общее количество вариантов порядка выступлений восьми спикеров — это 8!, где восклицательный знак — это факториал числа, то есть 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8.
Чтобы найти вероятность успешного выступления, разделим число успешных выступлений на общее количество:
(4 × 5 × 6 × 7 × 8) / (1 × 2 × 3 × 4 × 5 × 6 × 7 × 8)
Сократим общие множители и получим: 1 / (1 × 2 × 3) = ⅙
Получается, что вероятность успешного порядка выступления — ⅙ или 16%
Наблюдение
Раз у нас успешность зависит только от порядка выступления наших трёх спикеров, то давайте посчитаем вероятность правильного порядка среди трёх человек. Количество перестановок, которые можно сделать — это 3!, то есть 1 × 2 × 3 = 6. Но из них нас устраивает только один порядок, поэтому вероятность успешного выступления в этой комбинации — ⅙.
Технически этого было бы достаточно для решения, но нам нужно было убедиться, что добавление остальных участников не перевесит шансы на успешное выступление в какую-либо сторону. Поэтому мы пошли сначала по длинному пути, а потом убедились в том, что и короткий тоже работает.
Задача про демонов с собеседования на аналитика
Вот вам демонически сложная задача на логику. Условия:
- В деревне растёт одно яблоко и живёт 65 демонов.
- Если демон съест яблоко, он сразу уснёт.
- Если демон съест другого спящего демона, он тоже сразу уснёт.
- Демоны очень голодны и едят что угодно при первой удобной возможности.
- Демоны очень умны и всегда рассчитывают свои действия на много ходов вперёд.
- Наивысший приоритет для демона — собственная безопасность, поэтому, если ему будет грозить опасность, он никого не съест.
- Демон съест что угодно, только если после этого его жизни ничего не будет угрожать.
- Что вот-вот произойдёт в этой деревне?
На первый взгляд кажется, что с яблоком ничего не случится: как только любой демон его съест, его самого тут же съедят другие, поэтому демоны не будут трогать яблоко из-за опасения стать следующим. Теперь разберёмся, что будет на самом деле.
Для решения используем принцип математической индукции. Это значит, что мы начнём с маленьких цифр, будем постепенно их увеличивать и посмотрим, сможем ли мы найти при этом какую-то закономерность.
1 демон
Если в деревне будет только один демон, то всё просто: демон съедает яблоко и засыпает сам, но он в безопасности, потому что больше никого нет.
1 демон — яблоко съедено, больше ничего не происходит
2 демона
Если в деревне будет два демона, то яблоко останется целым — оба демона будут опасаться за свою безопасность. Дело в том, что стоит кому-то из них съесть яблоко, то ситуация становится одинаковой с предыдущей, только вместо яблока — спящий демон, а значит, и поведение будет таким же.
Получается, что второй демон съест спящего первого и уснёт сам в безопасности, потому что ему больше ничего не угрожает.
2 демона — яблоко целое, больше ничего не происходит.
3 демона
Если в деревне будет 3 демона, то случится такое:
- Первый демон съест яблоко и уснёт.
- Ситуация превратится в предыдущую, только вместо яблока — спящий демон.
Это значит, что оба оставшихся демона не съедят первого, опасаясь за свою жизнь. Работает это так: любой демон из трёх съедает яблоко и засыпает, и ситуация превращается в предыдущую. Это значит, что каждый оставшийся демон не будет есть первого, потому что его сразу съест оставшийся демон.
3 демона — яблоко съедено, больше ничего не происходит.
4 демона
Если в деревне будет 4 демона, то вот один из вариантов:
- Первый демон съедает яблоко, и ситуация превращается в предыдущую, только вместо яблока — демон.
- Это значит, что этого спящего демона может съесть второй демон и спокойно уснуть, не опасаясь за свою жизнь — оставшиеся два других его есть не будут, зная, что их тоже съедят.
Получается, что всем демонам логично не есть яблоко, иначе их сразу съест кто-то второй.
4 демона — яблоко целое, больше ничего не происходит.
Кажется, что мы нашли закономерность: если демонов нечётное количество, то яблоко останется целым, а если нечётное — первый демон съест яблоко и всё, больше ничего не произойдёт. Давайте убедимся в этом на пяти демонах.
5 демонов
Если в деревне будет 5 демонов, то случится такое:
- Первый демон съест яблоко и уснёт.
- Ситуация превратится в предыдущую, только вместо яблока — спящий демон.
- В предыдущей ситуации никто из демонов ничего не ел, чтобы с ним ничего не случилось.
Дело в том, что каждый демон хочет стать последним — тем, кого не съедят. Мы помним, что демоны очень умны и могут просчитывать ситуацию на много ходов вперёд. Каждый демон обдумал ситуацию и понял, что в ситуации с 5 демонами в безопасности только тот, кто съел яблоко, потому что помнит разбор предыдущей ситуации.
5 демонов — яблоко съедено, больше ничего не происходит.
Это называется математическая индукция, когда можно делать выводы и опираться на результаты предыдущих вычислений и опытов.
По этой индукции получается, что если в деревне будет 65 демонов (а это нечётное число), то один из них съест яблоко и больше ничего не произойдёт. А вот если бы их было 64, то яблоко бы осталось целым.
Шок-задача про длинный мост
Два программиста поехали в отпуск и увидели четырёхкилометровый прямой железнодорожный мост. У них состоялся такой диалог (между собой, а не с мостом):
— Ты же помнишь, что при нагревании металл расширяется?
— Конечно, а почему ты спрашиваешь?
— Представь, что летом от солнца железная дорога нагрелась и удлинилась на 1 сантиметр и выгнулась бы немного посередине вверх.
— Так, и?
— Как ты думаешь, ты бы смог это заметить? А если да — смог бы ты дотронуться до середины этого прогиба, чтобы указать точно, где он?
— А можно использовать шарики, уровень или любые другие подручные инструменты?
— Да вообще что угодно, главное — ответь на вопросы:-)
Второй программист задумался, а потом просиял и дал правильный ответ. Что же он ответил?
Для решения нам не понадобится ничего, кроме школьной программы по математике за седьмой класс. Вопрос про инструменты задан специально, чтобы нас запутать. Сейчас мы это решим.
Чтобы понять, как ответить на оба вопроса, сначала нарисуем мост в обычном, ненагретом состоянии:
Теперь, если мост нагреется, он удлинится на один сантиметр. Это значит, что он прогнётся посередине, в самом простом виде это будет выглядеть так:
Теперь совместим две картинки и попробуем найти высоту этого подъёма. Для этого используем теорему Пифагора:
Раз общая длина увеличилась на сантиметр, то длина половины увеличилась на полсантиметра. Зная это, переведём 4 километра в сантиметры и решим уравнение. При этом помним, что раз мы работаем с половиной моста, то и длину тоже нужно разделить сначала пополам:
a² + b² = c²
200000² + b² = 200000,5²
b² = 200000,5² − 200000²
b² = 40000200000,25 − 40000000000 = 200000,25
b = √200000,25 = 447,21 сантиметра
Получается, что середина железной дороги поднимется над центром моста почти на 4 с половиной метра! Это значит, что дотронуться до прогиба, стоя на мосту, точно не получится, а вот заметить, что дорога выгнулась, — точно получится.
Задача: угадать месяц по двум дням
Один аналитик в компании хвастался, что может сделать нужные выводы даже из минимальной информации. Руководитель задал ему такую задачку:
Если взять дату, которая была в последний понедельник прошлого месяца, и сложить с датой, которая будет в первый четверг следующего месяца, получится число 38. Какой сейчас месяц и год, если это всё месяцы одного года?
Аналитик подумал несколько минут и дал правильный ответ. Какой это ответ? Как он узнал?
Находим числа
Для начала определимся, какие числа могут вообще быть у последнего понедельника и первого четверга, вне зависимости от месяца и года.
Начнём с четверга следующего месяца и посмотрим на календарь:
По календарю видно, что первый четверг может быть первым числом, вторым, третьим и так далее до седьмого. Но восьмым числом четверг уже быть не может, потому что он тогда будет не первый уже, а второй.
Получается, что диапазон дат первого четверга лежит от 1 до 7. Но общая сумма дат равна 38, а это значит, что дата последнего понедельника предыдущего месяца лежит в диапазоне от 37-го до 31-го числа. В месяце не может быть больше 31 числа, а значит, единственные даты, которые нам подходят, такие:
понедельник, 31-е число
четверг, 7-е число
Определяем месяц
Теперь посмотрим, в каких месяцах есть 31-е число:
- январь,
- март,
- май,
- июль,
- август,
- октябрь,
- декабрь.
Это значит, что в нашем текущем месяце максимально может быть:
- 28 чисел, если это февраль;
- 29 чисел, если это февраль високосного года;
- 30 чисел, если это один из тех месяцев, что следуют за месяцем с 31 днём;
- 31 число, если это август, который идёт после июля.
Проверим их все по очереди, но сначала нарисуем календарь на прошлый месяц так, чтобы 31-е было последним понедельником:
Февраль, 28 дней. Раз 31-е число — это понедельник, то 1 февраля будет вторник, а 28 февраля снова понедельник. Получается, что в следующем месяце первое число будет вторником, а третье — четвергом. Но 31 + 3 = 34, что не соответствует условию задачи, поэтому февраль, где 28 дней, нам не подходит.
Февраль, 29 дней. Раз 31-е число — это понедельник, то 1 февраля будет вторник, а 29 февраля тоже будет вторник. Получается, что в следующем месяце первое число будет средой, а второе — четвергом. Но 31 + 2 = 33, что не соответствует условию задачи, поэтому февраль, где 29 дней, нам тоже не подходит.
Месяц, где 30 дней. Раз 31-е число — это понедельник, то 1-е число текущего месяца будет вторник, а 30-е среда. Получается, что в следующем месяце первое число будет четвергом. Но 31 + 1 = 32, что не соответствует условию задачи, поэтому февраль, где 29 дней, нам тоже не подходит.
Методом исключения получается, что единственный вариант, который у нас остаётся, — это когда и в прошлом, и в текущем месяце есть 31-е число. Такое бывает только у двух пар:
декабрь → январь;
июль → август.
По условию все месяцы должны быть одного года, поэтому декабрь и январь нам не подходят. Остаётся июль, август и сентябрь — проверим их:
Получается, сейчас — август. Осталось понять, какого года.
Методом простой сверки с календарями разных лет выясняем, что 7 сентября выпадает на четверг в 2023, 2017, 2006, 1999 году и так далее. То есть в среднем каждые 6–9 лет. Чтобы понять, какой это конкретный год, нужно как-то ограничить поиск.
