Семь задач-гномиков из слэка Open Data Science, а также итоги первого сезона сериала алгоритмических головоломок.
Семь гномиков
В Slack-канале чудесного сообщества Open Data Science есть раздел #gnomiki (назван по этой головоломке). Канал посвящен задачам, заданным на собеседованиях в IT-компании или тем, которые могли бы задать сами участники.
Ниже мы привели в порядке возрастания сложности семь задач-гномиков, не требующих длительного описания решения. В спойлерах – ответы, данные пользователями сообщества. Но не подглядывайте, постарайтесь сначала найти решение самостоятельно.
1. Простая задача про два числа
Начнем с очень простой задачи. Есть два числа, десятичные представления которых ни в одном разряде не содержат нуля. Но при перемножении два числа дают миллион. Что это за числа?
Ответ и решение
Раз речь о произведении, смотрим на множители. 10^6 = 5^6 * 2^6, то есть 15625 и 64.
2. Автомат по розливу чая и кофе
Автомат по розливу чая и кофе имеет три кнопки: «чай», «кофе», «чай или кофе». Первые две наливают то, что написано, третья каждый раз случайным образом делает выбор и наливает либо чай, либо кофе. Бирки с кнопок отвалились и их приклеили наугад так, что ни одна из бирок не попала на своё место. Сколько нажатий потребуется, чтобы однозначно определить где какая кнопка?
Ответ и решение
Ответ: 1 нажатие на кнопку «чай или кофе». Гарантия, что ни одна кнопка не на своём месте, даёт много информации. Нажимаем на кнопку «чай или кофе». Это детерминированная кнопка, поэтому что полилось, такая бирка и была исходно. Допустим, чай (для кофе логика не поменяется). Тогда оставшиеся либо «кофе», либо «чай или кофе». На двух оставшихся кнопках наклеено «чай», на другой «кофе». На текущей бирке «кофе» не может быть кофе, тогда за этой биркой «чай или кофе» (чай мы уже знаем где), а за чаем «кофе».
3. Периметр фигуры
Определите периметр фигуры, если все её углы прямые.
Ответ и решение
Ответ: 260. Сумма трёх вертикальных неизвестных равна 50. Остаются горизонтали. Пусть x – длина нижней стороны, y – длина короткой неизвестной горизонтали. Тогда из того, что в средней части фигуры одинаковое расстояние до вдавленной внутрь части, можно составить уравнение: 50-х = у-30. Отсюда следует х+у=80. Итого 50+50+50+80+30=260.
4. Вероятность найти деньги
Есть четыре коробки, человек говорит: «В одной из коробок с вероятностью 50% есть деньги». Открыли 3 коробки – пусто. Какова вероятность, что деньги в четвертой?»
Ответ и решение
Ответ: 20%. Посчитаем условную вероятность, что в четвертой коробке есть деньги, если в первых трех пусто: P(в 4-й деньги | в 1, 2, 3 пусто) = P(в 4-й деньги, в 1, 2, 3 пусто) / P(в 1, 2, 3 пусто) = (1/2 * 1/4) / (1/2 + 1/2 * 1/4) = 1/8 / 5/8 = 1/5.
5. Волшебный некрошащийся пирог
Вам принесли волшебный некрошащийся пирог, покрытый сверху шоколадом. Вы вырезали из пирога кусок в x радиан, перевернули и вставили обратно. Кусок удивительным образом сросся с пирогом. Потом вырезали следующий кусок в x радиан, так что начало нового куска совпадает с концом предыдущего, и так далее. При каких x рано или поздно весь шоколад опять окажется сверху?
Ответ и решение
Ответ: при любом x. При любом x в определённый момент пирог "перевернется обратно". Пусть у нас отрезается угол c = a + b, где a – размер куска, который остается незахваченным перед завершением круга. То есть круг равен nc + a. Тогда отрежем, начиная от начала, куски a1, b1, a2, b2, ..., an, bn, a(n+1). После отрезания и переворота мы получаем, что начиная с точки разреза лежат куски b1, a1, a2, b2, ..., bn, a(n+1). Повернем пирог на c, получим, что начиная с нового начала лежат куски a2, b2, ..., bn, a(n + 1), b1, a1 – по размерам те же, что и раньше, только сдвинутые. Получается что нам больше ничего резать не придется, только перекладывать уже нарезанное.
6. Матожидание и макаронные кольца
В кастрюле варятся N длинных макаронин. Повар не глядя берет два свободных конца, связывает их и повторяет этот процесс до тех пор, пока не кончатся макаронины со свободными концами. Найти мат ожидание количества макаронных колец (кольцо может состоять не из одной макаронины).
Ответ и решение
Ответ: ln(N)/2. Пусть f(N) – искомое матожидание. С вероятностью 1/(2N-1) мы соединяем макаронину с самой собой, получаем один цикл и на одну меньше макаронину, с вероятностью 1-1/(2N-1) число макаронин просто уменьшается на 1. Значит, f(N) = 1/(2N-1)(1+f(N-1))+(1-1/(2N-1))f(N-1) = f(N-1) + 1/(2N-1) = 1 + 1/3 + 1/5 + … + 1/(2N-1) = ln(2N-1) – ln(N)/2 + o(1) = ln(N)/2 + o(1).
7. Кажется, дождь собирается
Вы собираетесь на работу, вероятность, что идет дождь P. Если дождь идет, то вы берете зонтик. Вечером вы возвращаетесь с работы, вероятность дождя опять P. Если идет дождь и зонтик оказался на работе, то вы его берёте с собой. Сколько поездок в среднем можно совершить прежде, чем промокнешь?
Ответ и решение
Ответ: (2-2P+P^2)/(P-P^2). Назовем состояние 1 – зонт с нами в точке (дома или на работе), 0 – не с нами. Разберемся, как устроены переходы между этими состояниями. Из состояния 0 с вероятностью Р мы попадаем под дождь и заканчиваем наш сухой путь. С вероятностью 1-Р мы делаем поездку и оказываемся в состоянии 1. Из состояния 1 мы с вероятностью Р делаем поездку и снова попадаем в состояние 1, с вероятностью 1-Р делаем поездку и попадаем в состояние 0. Обозначим через Е1 матожидание количества поездок из состояния 1, Е0 – из 0. Записываем выше сказанное в виде уравнений 0) E0 = P*0 + (1-P)*(E1+1); 1) E1 = P*(E1+1)+(1-P)*(E0+1). Решаем линейную систему. Посчитанный ответ Е1 указан в начале спойлера.