Задача
Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (ни в порядке возрастания, ни в порядке убывания). Сколько неправильных шеренг можно построить из 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 шеренги).
Во втором случае (AB*) имеем 6 шеренг: C, D и E можно ставить произвольно.
Итого имеем 8 шеренг типа A+–, а всех неправильных шеренг – в 4 раза больше.
Ответ
а) 10 шеренг; б) 32 шеренги.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь