Найдите количество способов закрасить некоторые клетки «лесенки» так, чтобы выполнялись следующие условия:
• Ниже каждой закрашенной клетки либо нет других клеток, либо они все закрашены.
• В одном столбце закрашено 5 клеток, в другом – 4 клетки, в третьем – 3 клетки, …, в последнем – 0 клеток.
Источник задания: ВсОШ sochisirius.ru
Решение:
Ниже каждой закрашенной клетки либо нет других клеток, либо они все закрашены.
Это условие говорит о том, что нужно начинать закрашивать клетки с нижний и подряд, не пропуская клеток.
5 клеток можем закрасить, только в 2 столбцах на выбор.
4 клетки, учитывая что в одном уже закрашено 5 клеток, можем тоже закрасить в 2 столбцах на выбор.
3 клетки, учитывая, что есть столбец с 5 клетками и 4 клетками, тоже 2 способами. И так далее..
2 клетки – 2 способами.
1 клетку – 2 способами.
0 клеток – 1 способом (останется один столбец)
Тогда всего вариантов:
2·2·2·2·2·1 = 32
Ответ: 32.