Головоломка: кто умнее, вы или кот?

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

Хвостатые давно пронюхали, что пол — это лава, так что где бы они ни прятались — на чистой перинке или в мусорном баке, коты всегда на высоте. Волна фотографий с подписью «Найди кота», которая прокатилась по твиттеру, это доказывает.

И это только разминка.

Коты играют с людьми и в прятки, и в напёрстки. Кот за дверью из этой головоломки — тот еще плут. Вот что дано:

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

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

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

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

Ключ к головоломке — визуализация.

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

А теперь дверей пять:

Если кот за одной из семи дверей, то вы можете выкурить его оттуда за 10 дней. Эта формула работает до бесконечности. Вы всегда сможете поймать кота за (число дверей минус 2) X 2 дней. Если бедняга там еще жив, конечно.