Question

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

Answer 1

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

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

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

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

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