Question

Во дворце имеется 22 комнаты: 21 «именных» – для 21 принцессы и одна запасная. В комнаты поселили принцесс, но оказалось, что ни одна из принцесс не находится в своей комнате. Необходимо переселить принцесс, чтобы каждая оказалась в своей комнате; за раз можно переселять одну принцессу, в свободную комнату. Верно ли, что наименьшее количество переселений, чтобы гарантированно правильно разместить принцесс, равно 31?

Answer 1

Берём первую попавшуюся и тащим в запасную, это первое переселение.

Затем на свободное место тащим из чужой в свою комнату каждую из 20, это ещё 20 переселений.

И наконец ту, что сидела всё время в запасной тоже её в свою всунем.

Значит всего 1+20+1=22 переселения.

(P.S. Про первую попавшуюся пошутил , логистика должна быть так  просчитана, чтоб та комната, что принадлежит сидящей в запасной комнате освободилась в самую последнюю очередь, а не сразу после первого переселения, иначе количество переселений не будет минимальным)

Answer 2

Да, верно, что наименьшее количество переселений, чтобы гарантированно правильно разместить принцесс, равно 31.

Для решения этой задачи можно использовать метод математической индукции.

Пусть n - количество принцесс (в данном случае n = 21). Обозначим как F(n) количество переселений, которое требуется для правильного размещения n принцесс.

Базовый случай: F(1) = 0, так как в этом случае принцесса уже находится в своей комнате.

Шаг индукции: Предположим, что для всех k < n верно, что F(k) = k - 1.

Рассмотрим случай с n принцессами. Если принцесса, которая занимает запасную комнату, переселить в любую из оставшихся 21 комнаты, то останется n-1 принцесса, и для них потребуется F(n-1) переселений. Затем, чтобы разместить переселенную принцессу, требуется еще одно переселение. Таким образом, общее количество переселений для n принцесс будет равно F(n-1) + 1.

Исходя из предположения индукции, получаем, что F(n) = F(n-1) + 1 = (n-1) + 1 = n.

Таким образом, для правильного размещения 21 принцессы потребуется 21 переселение, а не 31, как указано в вопросе.