В мире масса интересных сложных и не очень задач. Большинство из них можно решить, имея только знания и навыки. По алгоритму или перебором (если есть достаточные ресурсы). Такие задачи роботы и искусственный интеллект решают даже лучше и быстрее человека.
Но в некоторых задачах без логики не обойтись. Как только найдешь изюминку, отыщешь подход, решение становится делом техники. Более того, с известной идеей задача кажется легкой. А без идеи она кажется нерешаемой. Именно поэтому те, кто умеет находить решения, получают больше, чем те, кто занимается реализацией этого решения.
Вот вам отличный пример. Мне эта задача очень понравилась.
В лаборатории есть 1000 пробирок, в одной из которых яд. Нужно с помощью 10 мышек узнать, в какой именно. Проблема в том, что яд убивает через 20 часов, а в вашем распоряжении не больше суток.
На первый взгляд эта задача кажется похожей на классические задачи из учебников про взвешивания монет и поиск фальшивки (ссылку на одну из них оставлю в конце), но с таким подходом на поиск яда уйдет минимум 3-5 дней. У нас же есть только сутки.
На второй взгляд задача вообще не имеет решения, потому что... Потому что это кажется невозможным: тысяча пробирок, всего десять мышей. За сутки проверишь 10 пробирок. Ну или 100. Если повезет, то пробирка с ядом будет в числе первых, но нам-то нужен способ, который приведет нас к решению наверняка, а не если подфартит.
Однако, как вы понимаете, решение есть. Правда, найти его нелегко. Подумайте, не спешите смотреть идею решения ниже.
Решение
Как вы понимаете, решение нетипичное. И это как раз тот случай, когда нам нужно перейти от десятичной системы счисления к двоичной. Если вы плохо помните, как переходить от одной системы к другой, вот эта статья вам в помощь.
На всякий случай напоминаю, как перевести 1000 из десятеричной системы в двоичную. Просто делим на 2 до тех пор, пока есть, что делить, а потом записываем последнее частное и все остатки справа-налево — смотри картинку ниже. В галерее также показан перевод из десятеричной системы в двоичную чисел 999 и 631.
Как мы поняли, 1000₁₀=1111101000₂; 999₁₀=1111100111₂; ... ; 631₁₀=1001110111₂; и т.д.
Аналогично, переводя все числа от 1 до 1000 из десятеричной системы в двоичную (можно воспользоваться специальным калькулятором), мы можем каждую из тысячи пробирок пронумеровать числом в двоичной системе счисления. Получится как-то так.
Как видим, для записи максимального числа нам понадобится 10 нулей и единиц, то есть 10 бит. И по условию задачи у нас как раз 10 мышей. Совпадение? Не думаю!
Тут можете остановиться и подумать, что делать дальше.
Дальше
А дальше начинается ни что иное, как магия.
Рассаживаем наших мышей в 10 клеток так, чтобы они не бегали и не могли поменяться местами. В каждой клетке у нас всё время сидит одна и та же мышь. Клетки расставляем в ряд.
Теперь даем самой правой мышке каплю из первой пробирки (в двоичной системе её номер 0000000001).
Из второй пробирки (её номер в двоичной системе — 0000000010) даём каплю второй справа мышке.
Из третьей пробирки (номер 0000000011) даём по одной капле мышам в двух правых пробирках.
И так далее.
Из 631-ой пробирки (номер 1001110111) даём по капле мышкам под номерами один,четыре, пять, шесть, восемь, девять и десять.
...
Из 999-ой пробирки (номер 1111100111) даём по капле всем мышам, кроме шестой и седьмой.
Из 1000-ой пробирки (номер 1111101000) даём по капле мышкам под номерами 1, 2, 3, 4, 5 и 7.
Если кто не понял, то каждой пробирке соответствует уникальная последовательность нулей и единиц. По капле из одной и той же пробирки мы даем мышкам в тех клетках, номера которых соответствуют местам, на которых стоят единицы в двоичном номере пробирки.
Таким образом, через сутки, когда часть мышей погибнет, мы однозначно узнаем, в какой пробирке был яд. Каким образом? Тут нам пригодится обратный перевод из двоичной в десятеричную систему счисления.
Живых мышек обозначим нулями, мертвых — единичками.
Например, через сутки после эксперимента погибшими оказались три мышки слева и две мышки справа, остальные — живые. В двоичном коде этому соответствует пробирка номер 1110000011. Переводим это число в десятеричную систему (смотри фотографию ниже или вот эту статью) и получаем, что яд был в 899-ой пробирке.
Как вам такой фокус? По-моему шикарная задача. Как видите, зная идею, решить задачу сможет любой старшеклассник (и даже младшеклассник, если объяснить ему, куда нажимать на калькуляторе). Но вот додуматься до этой идеи сможет далеко не каждый. В том числе не каждый руководитель IT-отдела и не каждый тимлид. Насколько я знаю, эту задачу на собеседовании решили единицы.
Пишите в комментариях, решили ли вы сами задачу или с подсказками? И догадались бы до такой хитрой схемы? Также не забываем про мои каналы в Ютубе, Инстаграме и ТикТоке.
Ещё интересно: "Бородатая" задачка, которая до сих пор ставит многих в тупик. 12 монет и 3 взвешивания
Задача родом из СССР про фальшивые монеты, которую давали на собеседовании в МГУ
