CURSOR Блог

Логічна задачка про те, як знайти кота?

Умова


Під час переїзду, в квартирі з'явилося 5 порожніх коробок, і кіт, знайшовши собі улюблене місце, почав у них спати. На кожній коробці написана своя цифра, від 1 до 5, і стоять вони в ряд по черзі.

На ранок кіт вилазить з чергової коробки, а на ніч переходить спати в сусідню праворуч або ліворуч, яка стоїть поруч з тією, де він ночував минулого разу. Щоранку можна відкрити тільки одну коробку, щоб перевірити, чи є там кіт.

Питання

Чи є така стратегія, щоб гарантовано знайти кота в будь-який ранок, якщо ми не знаємо, в яку коробку він пішов спати у першу ніч?

image

Розв'язання


Оскільки кіт завжди переходить у сусідню коробку, то він по черзі спить в парних і непарних коробках. Використовуємо це при вирішенні.

Якщо кіт почав з парної коробки

Це означає, що в першу ніч кіт заснув в коробці 2 або 4. Припустимо, ми вранці відкриваємо коробку 2. Якщо кіт там — ми виграли. Якщо кота там немає, значить, він точно в коробці 4. А раз він точно в коробці 4, значить, наступної ночі він піде спати в коробку 3 або 5.

Другою вранці перевіряємо коробку 3. Якщо кіт спить там — ми виграли. Якщо кота там немає, значить, він спить в коробці 5. А це означає, що наступної ночі він точно буде спати в коробці 4, тому що коробка 5 не має інших сусідів.

На третій ранок відкриваємо коробку 4 і знаходимо кота. Перемога.

Якщо кіт почав з непарної коробки

Якщо ми пройшли наш алгоритм 2-3-4 і не знайшли кота, це означає, що він почав спати з непарної коробки. Виходить, що в першу ніч кіт спав у непарній, в другу — у парній, а третьої ночі — знову в непарній. Виходить, що на четвертий ранок кіт знову буде в парній коробці — 2 або 4.
Але у нас вже є стратегія знаходження кота в парних коробках, ми тільки що її описали в попередньому розділі. Значить, нам достатньо застосувати її ще раз і знову відкрити вранці коробки 2, 3 і 4, щоб точно визначити де кіт.

Навіщо тобі шукати котів?

Котів шукати абсолютно без сенсу. Але от будувати логічні алгоритми — це хліб розробників. Починайте зараз з простого, щоб потім не морочити собі голову.
Задачки