РЕШУ ОЛИМП — математика

Задания

В треугольном доме в первом подъезде 1 этаж, во тором подъезде  — 2 этажа, в третьем  — 3, ..., в девятом  — 9. Всего в доме 45 квартир  — на каждом этаже в каждом подъезде находится ровно одна квартира. Известно, что если в квартире кто-нибудь живёт, то в квартире на этаж выше в том же подъезде тоже кто-нибудь живет, и квартира на том же этаже, но в следующем по номеру подъезде тоже заселена. Сколько существует таких способов заселить квартиры?

Пример заселения изображен на рисунке, заселённые квартиры отмечены серым. При подсчёте способов заселения каждая квартира считается либо заселённой, либо нет; кто именно в ней живёт, неважно. Случай, когда все квартиры остались пустыми, включается в подсчёт.

Решение. Докажем, что если подъездов n, то способов заселения 2ⁿ: будем рассуждать индукцией по n. База $n=0$ очевидна.

Пусть утверждение доказано для дома из $n минус 1$ подъезда; докажем его для дома из n подъездов. Рассмотрим квартиру на первом этаже последнего подъезда. Она либо заселена, либо нет.

В первом случае мы можем выкинуть последний подъезд; ясно, что о ставшиеся $n минус 1$ подъезд могут быть заселены произвольно согласно правилам задачи, то есть $2 в степени левая круглая скобка n минус 1 правая круглая скобка$ способами. Во втором случае мы можем выкинуть первый этаж изо всех подъездов; ясно, что оставшиеся этажи могут быть заселены, опять-таки, $2 в степени левая круглая скобка n минус 1 правая круглая скобка$ способами.

Эти два случая, очевидно, не пересекаются и исчерпывают возможности. Суммируя их, получаем 2ⁿ.

Ответ: 512.

Приведем другое решение.

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

Длина этой линии (измеренная в рёбрах сетки) равна количеству подъездов; при этом каждое её ребро может идти либо влево, либо вверх. Следовательно, количество способов её провести равно соответствующей степени двойки.

№ п/п	№ задания	Ответ
1	5986	512.

Ключ