Это одна из моих любимых задач, которой можно надолго занять ребёнка. Или же самому испытать свою логику и умение разрабатывать алгоритмы на прочность.
Ответ в конце статьи.
Задача:
После праздников в комнате осталось 5 коробок в ряд разного размера и цвета. Но так уж вышло, что подаренный хозяину котёнок повадился спать в одной из них каждую ночь. Известно, что на каждый следующий день зверёк меняет коробку. Причем его выбор всегда падает на соседнюю (значит если сегодня он спал в 3, то завтра он предпочтет либо 2, либо 4).
Можно проверить одну любую коробку один раз в сутки.
В учет не берётся удача (можно найти и с первого раза - такое мы не рассматриваем). Коробки убирать нельзя. Котёнок не издаёт звуков и не оставляет никаких следов. Во все коробки животное помещается.
За какое минимальное количество попыток вам удастся гарантированно найти котёнка?
Пишите ваше решение в комментариях (с подробностями и алгоритмом).
Решение:
Котёнок может спать в любой коробке в первую ночь. Но вариантов всего пять. Каждая коробка является либо четной (2 или 4), либо нечетной (1,3,5). Используем этот факт для создания системы решения задачи.
Первая ночь
Предположим, что котёнок начал с чётной коробки (2 либо 4). Проверяем утром коробку 2. Если его там нет, то он спал в 4. А это значит, что на следующую ночь он выберет соседнюю (3 либо 5).
Вторая ночь
На утро проверяем коробку 3. Если его там нет, значит он спал в 5. Получается, что следующую ночь его выбор однозначно остановится на коробке 4, потому что она единственная соседняя к 5.
Третья ночь
Открываем 5 коробку и... не находим его?! Это значит, что в первую ночь котёнок уснул всё-так в нечётной коробке. Значит во вторую он спал в чётной, в третью в нечётной. И в итоге на данный момент получается, что в четвёртую ночь котёнок будет спать в четной коробке (либо 2, любо 4).
А решение для такой ситуации мы как раз рассмотрели за первые трое суток - просто повторяем алгоритм заново (ещё три ночи).
Поздравляю, вы нашли котёнка!
Получается, что гарантированно найти котёнка в 5 коробках можно за 6 ночей (попыток).
Если задачка показалась вам забавной и интересной - ставьте лайк и поделитесь её с друзьями.
Чтобы не пропустить новые публикации - Подписывайтесь на канал.
Буду рад видеть вас снова!