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

Допущение: изначально все двери на месте, в подвале дверей нет. 1. Всего в интернате 10 комнат и 10 дверей. 2. Когда житель просыпается, происходит одно из двух: - Если его дверь на месте (в комнате +1 дверь), он уносит чужую дверь в подвал (в подвале +1 дверь). - Если его двери нет (в комнате 0 дверей), он приносит любую дверь из подвала и вешает себе (в подвале -1 дверь). 3. Чтобы в подвале было как можно больше дверей, нужно, чтобы как можно больше жителей застали свои двери на месте. 4. Рассмотрим последовательность действий: - 1-й проснулся: его дверь на месте, он уносит дверь 10-го жителя в подвал. (В подвале 1 дверь). - 2-й проснулся: его дверь на месте, он уносит дверь 9-го жителя в подвал. (В подвале 2 двери). - 3-й проснулся: его дверь на месте, он уносит дверь 8-го жителя в подвал. (В подвале 3 двери). - 4-й проснулся: его дверь на месте, он уносит дверь 7-го жителя в подвал. (В подвале 4 двери). - 5-й проснулся: его дверь на месте, он уносит дверь 6-го жителя в подвал. (В подвале 5 дверей). 5. Теперь просыпаются те, чьи двери унесли: - 6-й проснулся: его двери нет, он забирает одну из подвала. (В подвале 4 двери). - 7-й проснулся: его двери нет, он забирает одну из подвала. (В подвале 3 двери). - 8-й проснулся: его двери нет, он забирает одну из подвала. (В подвале 2 двери). - 9-й проснулся: его двери нет, он забирает одну из подвала. (В подвале 1 дверь). - 10-й проснулся: его двери нет, он забирает одну из подвала. (В подвале 0 дверей). 6. Заметим, что если 1-й унесет дверь 2-го, то 2-й сразу же ее вернет. Значит, чтобы накопить двери, нужно сначала «снимать» двери тех, кто проснется позже всех. 7. Максимальное число достигается в середине процесса. Но по условию нужно количество **после того, как все проснулись**. 8. Пусть $k$ человек проснулись и застали дверь на месте, а $(10-k)$ человек застали дверь отсутствующей. - Те, кто застали дверь, добавили в подвал $k$ дверей. - Те, кто не застали, забрали из подвала $(10-k)$ дверей. - Итого в подвале: $k - (10 - k) = 2k - 10$ дверей. 9. Чтобы это число было положительным и максимальным, $k$ должно быть как можно больше. Но дверь $i$-го человека может быть в подвале только если её снял кто-то из ранее проснувшихся. Значит, количество снятых дверей $(k)$ не может превышать количество людей, у которых эти двери сняли $(10-k)$. $k \le 10 - k \Rightarrow 2k \le 10 \Rightarrow k \le 5$. 10. При $k = 5$, в подвале останется $2 \cdot 5 - 10 = 0$ дверей. Если $k < 5$, число будет отрицательным (что невозможно, так как нельзя забрать дверь из пустого подвала). **Ответ: 0**