Как в офисе обойти всех программистов по одному разу
hard

Как в офисе обойти всех программистов по одному разу

Задача на логику и математику

Любите математику?
Это для вас
Попробуйте бесплатный тренажёр «Основы математики для цифровых профессий».
Попробовать бесплатно
Любите математику? <br data-lazy-src="https://thecode.media/wp-content/uploads/2023/07/b54-mob.png"><noscript><img width="537" height="164" class=

А вот вам четверговая логическая и математическая задачка. 

В одной ИТ-компании офис разбили так, чтобы у 15 программистов и менеджера было по своему кабинету. Для этого офис разделили на 16 помещений и сделали сквозные двери в каждом кабинете. Менеджер сидит в первом офисе, а общий вход и выход — через кабинет №16:

Как в офисе обойти всех программистов по одному разу

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

Математическая теория говорит про это так: невозможно в такой конфигурации обойти каждый кабинет только один раз, чтобы выйти из кабинета №16. Чтобы это доказать наглядно, раскрасим кабинеты как шахматную доску:

Как в офисе обойти всех программистов по одному разу

Каждый шаг между кабинетами — это перемещение с белой клетки на чёрную и наоборот. Нам нужно пройти 15 кабинетов, а значит — сделать 15 ходов. Если количество ходов нечётное, то старт и финиш будут на клетках разного цвета:

  • один ход: с белой на чёрную;
  • два хода: белая → чёрная → белая;
  • три хода: белая → чёрная → белая → чёрная и так далее.

Но у нас клетки 1 и 16 одного цвета, а значит, дойти до финиша без повторений и возвратов не получится. Такая теория, кстати, работает для всех шахматных досок с размерностью N×N, где N — чётное число.

Получается, что у этой задачи нет решения даже в теории и менеджеру придётся заглянуть к кому-то дважды.

Хитрость в том, что в задаче нас просят не обойти каждый кабинет один раз, а встретиться с каждым программистом один раз :-) Это сразу меняет дело, следите за руками:

1. Менеджер переходит в кабинет 2 и встречается там с программистом.

2. После этого он возвращается в свой кабинет, который пустой — там никого нет, поэтому менеджер там никого не встретит. Это ключевой момент решения: пустой кабинет позволяет нам увеличить количество шагов на единицу, чтобы обойти ограничение теории из предыдущего раздела. Таким способом мы делаем 16 шагов, и это значит, что первая и последняя клетка должна быть одного цвета, как нам и нужно.

Как в офисе обойти всех программистов по одному разу

3. После этого менеджер обходит остальные 14 кабинетов и заходит в каждый по одному разу. Всего таких маршрутов будет 4:

Как в офисе обойти всех программистов по одному разу
Как в офисе обойти всех программистов по одному разу
Как в офисе обойти всех программистов по одному разу
Как в офисе обойти всех программистов по одному разу

Текст:

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

Редактор:

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

Художник:

Алексей Сухов

Корректор:

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

Вёрстка:

Кирилл Климентьев

Соцсети:

Аня Соколова

Любите математику? Это для вас
Попробуйте бесплатный тренажер «Основы математики для цифровых профессий». Это все необходимые знания, чтобы закрыть пробелы в математике для айтишника.
Попробовать бесплатно
Любите математику? Это для вас Любите математику? Это для вас Любите математику? Это для вас Любите математику? Это для вас
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
hard