Как найти кота?

Во вре­мя пере­ез­да в квар­ти­ре появи­лось 5 пустых коро­бок, и кот стал в них спать. На каж­дой короб­ке напи­са­на своя циф­ра, от 1 до 5, а сами короб­ки сто­ят в ряд по порядку.

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

Есть ли такая стра­те­гия, что­бы гаран­ти­ро­ван­но най­ти кота в какое-нибудь утро, если мы не зна­ем, в какую короб­ку он пошёл спать в первую ночь?

Не ищи­те логи­ку, давай­те про­сто решать.

Решение

Так как кот все­гда пере­хо­дит в сосед­нюю короб­ку, то он по оче­ре­ди спит в чёт­ных и нечёт­ных короб­ках. Исполь­зу­ем это при решении.

Кот начал с чётной коробки

Это зна­чит, что в первую ночь кот уснул в короб­ке 2 или 4. Допу­стим, мы утром откры­ва­ем короб­ку 2. Если кот там — мы выиг­ра­ли. Если кота там нет, зна­чит, он точ­но в короб­ке 4. А раз он точ­но в короб­ке 4, зна­чит, сле­ду­ю­щей ночью он пой­дёт спать в короб­ку 3 или 5.

Вто­рым утром про­ве­ря­ем короб­ку 3. Если кот спит там — мы выиг­ра­ли. Если кота там нет, зна­чит, он спит в короб­ке 5. А это зна­чит, что сле­ду­ю­щей ночью он точ­но будет спать в короб­ке 4, пото­му что у короб­ки 5 нет дру­гих соседей. 

На тре­тье утро откры­ва­ем короб­ку 4 и нахо­дим кота. Победа.

Кот начал с нечётной коробки

Если мы про­шли наш алго­ритм 2–3–4 и не нашли кота, это зна­чит, что он начал спать с нечёт­ной короб­ки. Полу­ча­ет­ся, что в пер­вое утро кот спал в нечёт­ной, во вто­рое — в чёт­ной, а в тре­тье — сно­ва в нечёт­ной. Выхо­дит, что на чет­вёр­тое утро кот сно­ва будет в чёт­ной короб­ке — 2 или 4. 

Но у нас уже есть стра­те­гия нахож­де­ния кота в чёт­ных короб­ках, мы толь­ко что её опи­са­ли в преды­ду­щем раз­де­ле. Зна­чит, нам доста­точ­но при­ме­нить её ещё раз и сно­ва открыть по утрам короб­ки 2, 3 и 4, что­бы точ­но най­ти кота.

Зачем искать котов?

Котов — неза­чем. Коты, когда захо­тят, сами найдутся. 

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

Текст:

Миха­ил Полянин

Редак­тор:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев