Задача по комбинаторике В классе учится одинаковое количество мальчиков и девочек (всего в классе не менее 4 человек). Их в различном порядке выстраивают в один ряд и смотрят, нельзя ли разделить ряд на две части так, чтобы в каждой части девочек и мальчиков было поровну. Пусть a — количество случаев, когда такое разбиение ряда невозможно, а b — количество случаев, когда удаётся разбить ряд на две такие части лишь одним способом. Докажите, что b=2a.

Предыдущий
вопрос Следующий
вопрос

Пусть всего в классе ( n ) мальчиков и ( n ) девочек. Так как всего в классе не менее 4 человек, то ( n \geq 2 ).

Рассмотрим случай, когда нельзя разделить ряд на две части, чтобы в каждой части девочек и мальчиков было поровну. В этом случае второй по порядку ученик в ряду не может быть таким же пола, как и первый, иначе ряд можно будет разделить. Таким образом, для каждого мальчика в начальной позиции (или девочки) можем найти только один способ построения ряда, где это условие выполняется. То есть, всего у нас ( n ) способов.

Теперь рассмотрим случай, когда удаётся разбить ряд на две части лишь одним способом. Для этого возможны два варианта: либо в начале ряда стоит мальчик и тогда за ним будет стоять девочка, либо в начале ряда стоит девочка и за ней будет стоять мальчик. В каждом из случаев у нас будет один способ построения ряда. Таким образом, всего у нас ( 2n ) способов.

Таким образом, ( b = 2a ), что и требовалось доказать.