Коммунальная квартира

Условие

В коммунальной квартире 10 комнат. Жильцы этих комнат просыпаются по очереди. Если дверь их комнаты на месте, они снимают дверь какой-либо другой комнаты и относят ее в подвал.

Если же дверь их комнаты отсутствует, они забирают из подвала любую дверь и ставят ее на место своей (если ни одно из этих действий невозможно, они не делают ничего).

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

Подсказка: подумайте, могут ли оказаться в подвале все 10 дверей.

Ответ

Представим, что жильцы коммунальной квартиры просыпаются в порядке нумерации их комнат: сначала – первой, потом – второй и т. д.

Рассмотрим комнату, в которой сняли дверь жители первой комнаты. Когда жильцы комнаты со снятой дверью проснутся, они повесят свою дверь на место. В результате этих операций ни одной двери в подвале не прибавится и, если даже жильцы остальных 8 комнат снимут по двери, в подвале окажется не более 8 дверей.

Например: жильцы первой комнаты снимают дверь в десятой комнате, жильцы второй комнаты снимают дверь в первой, ..., жильцы n-й комнаты снимают дверь в n – 1 (1 < n < 10) комнате.

Проснувшиеся последними жильцы десятой комнаты вешают свою дверь на место, после чего в подвале окажется 8 дверей от первой, второй, третьей, четвертой, пятой, шестой, седьмой и восьмой комнат.