|
|
 |
Условие
Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (ни в порядке возрастания, ни в порядке убывания). Сколько неправильных шеренг можно построить из n солдат разного роста, если
а) n = 4;
б) n = 5?
Решение
Поставим между соседними солдатами "+", если правый выше левого, и "–" – в противном случае. По условию плюсы и минусы в неправильной шеренге должны чередоваться. Ясно, что количество шеренг, начинающихся с плюса, равно количеству шеренг, начинающихся с минуса.
а) Найдём количество шеренг типа *+*–*+*. Обозначим солдат буквами A, B, C и D в порядке уменьшения роста. В шеренге указанного типа A может стоять на втором или четвёртом местах (после плюса).
В шеренге *A*+* солдат B может стоять на первом или четвёртом месте. В первом случае имеем одну шеренгу – BADC, во втором – две: C и D можно ставить на оставшиеся места произвольно.
В шеренге *+*–*A солдат B может стоять только на втором месте. Таких шеренг снова две.
Итого имеем 5 шеренг типа *+*–*+*, а всех неправильных шеренг – вдвое больше.
б) Найдём количество шеренг типа *+*–*+*–*. Обозначим солдат буквами A, B, C, D и E в порядке уменьшения роста. И здесь A может стоять на втором или четвёртом месте. Но эти случаи симметричны, поэтому достаточно рассмотреть только первый: *A*+*–*. При этом B может стоять на первом или четвёртом месте.
В первом случае (BA*+*–*) C может стоять только на четвёртом месте, а D и E можно ставить на оставшиеся места произвольно (2 шеренги).
Во втором случае (*A*B*) имеем 6 шеренг: C, D и E можно ставить произвольно.
Итого имеем 8 шеренг типа *A*+*–*, а всех неправильных шеренг – в 4 раза больше.
Ответ
а) 10 шеренг; б) 32 шеренги.
