Разделы 
Дополнительно
Задача по математике - 10451
2023-02-17 
В классе учится одинаковое число мальчиков и девочек (всего класс насчитывает не менее 4 человек). Их в различном порядке выстраивают в один ряд и смотрят, нельзя ли разделить ряд на две части так, чтобы в каждой части девочек и мальчиков было поровну.
Пусть $a$ - число случаев, когда такое разбиение ряда невозможно, a $b$ - число случаев, когда удается разбить ряд на две части с одинаковым числом девочек и мальчиков в каждой из них, но лишь одним способом.
Доказать, что $b = 2a$.
Решение:
Будем говорить, что класс построен в ряд типа $A$, если его нельзя разделить на две части так, чтобы в каждой из них девочек и мальчиков было поровну, и в ряд типа $В$, если такое разбиение возможно, но лишь одним способом.
Пусть $X$ - ученик, стоящий первым. Если $X$ - девочка, то обозначим всех девочек $X$, а всех мальчиков $Y$. Если $X$ - мальчик, то обозначим всех мальчиков $X$, а всех девочек $У$. Поскольку в классе учатся $n$ мальчиков и $n$ девочек, то любое построение класса можно записать в виде последовательности букв $X$ и $Y$, начинающейся с $X$ и содержащей $n$ букв $X$ и $n$ букв $Y$. (В дальнейшем мы будем рассматривать лишь такие последовательности. Назовем их для краткости словами.) Каждому слову соответствуют два построения класса: при одном построении $X$ означает мальчика, при другом - девочку.
Если слово принадлежит к типу $А$, то на какой бы букве (кроме последней) его ни оборвать, в укороченном слове букв $X$ окажется по крайней мере на 1 больше, чем букв $Y$. Действительно, поскольку укороченное слово начинается с $X$ и при увеличении длины слова число иксов и игреков меняется на единицу, то «перевес» игреков над иксами может быть достигнут лишь после того, как число иксов и игреков в каком-то укороченном слове станет одинаковым. Но поскольку рассматриваемое слово принадлежит типу $А$, то это невозможно.
Слово принадлежит типу $В$ тогда и только тогда, когда его можно разбить на два более коротких слова типа $А$. Первое из этих «подслов» начинается с буквы $X$, второе может начинаться и с $X$, и с $У$. Если второе под-слово типа $А$ начинается с $У$, то, заменив в нем $X$ на $Y$, а $У$ на $X$, мы получим снова слово типа $А$. Поэтому все слова типа $В$ разбиваются на пары, в каждой из которых первые подслова одинаковы, а вторые получаются указанной заменой букв. Таким образом, утверждение задачи будет доказано, если мы убедимся в том, что каждому слову типа $А$ взаимно однозначно соответствует слово типа $В$, у которого обе части типа $А$ начинаются с буквы $X$.
Требуемое соответствие можно получить, переставив букву $X$, с которой начинается вторая часть слова типа $В$ (сама вторая часть представляет собой укороченное слово типа $A$), на первое место перед всем словом.
Докажем, что полученное слово принадлежит типу $A$. Действительно, как было показано выше, оборвав первую часть (укороченное слово типа $А$) исходного слова типа $В$ на любой букве, кроме последней, мы получим новое (укороченное) слово, содержащее иксов по крайней мере на один больше, чем игреков. Обрывая слово, которое возникло после того, как перед первой буквой $X$ поставили букву $X$, с которой начиналась вторая часть типа $A$ исходного слова, на любой букве, начиная со второй, мы будем получать укороченные слова, содержащие иксов по крайней мере на два больше, чем игреков, до тех пор, пока не дойдем до последней буквы первой части. Эта буква в новом слове стоит на том месте, где в исходном слове типа $В$ стояла первая буква второй части типа $А$. Оборвав новое слово на последней букве первой части типа $А$ исходного слова, мы получим укороченное слово, которое содержит иксов по крайней мере на один больше, чем игреков. Обрывая новое слово на любой букве, начиная со второй буквы второй части типа $А$ исходного слова, мы будем получать укороченные слова, в которых соотношение иксов и игреков будет таким же, как в укороченном слове, полученном при обрыве на той же букве исходного слова типа $В$. Следовательно, в любом из укороченных слов иксов будет больше, чем игреков. «Равновесие» наступит, лишь когда мы дойдем до самой последней буквы.
Наоборот, в любом слове типа $А$ должна быть еще одна буква, кроме первой, такая, что, оборвав на ней исходное слово, мы получим укороченное слово, в котором иксов на одну букву больше, чем игреков (миновав первую букву, мы, очевидно, получаем «перевес» в одну букву для иксов). Впишем $X$ после этой буквы, а самую первую букву $X$ исходного слова зачеркнем. Новое слово начинается с буквы $X$, поскольку если бы второй буквой исходного слова была буква $У$, то, оборвав его на второй букве, мы получили бы разбиение слова типа $А$ на две части, каждая из которых содержит одинаковое число иксов и игреков (по условиям задачи исходное слово содержит не менее четырех букв), что невозможно. Зачеркнув первую букву $X$, мы уменьшили разность между числим букв $X$ и $Y$ во всех укороченных словах, правый конец которых находится не дальше вписанной буквы $X$, на 1. Для укороченного слова, кончающегося на букве, стоящей перед вписанной буквой $X$, эта разность до зачеркивания первой буквы $X$ была равна 1. Следовательно, после зачеркивания разность между числом иксов и игреков для этого слова стала равной нулю. Следовательно, оборвав получившееся слово на этой букве, но не раньше, мы разобьем его на две части, в каждой из которых букв $X$ и $Y$ будет поровну. Любое укороченное слово, конец которого находится не левее вписанной буквы $X$, будет содержать больше иксов, чем игреков, поскольку в этом слове соотношение иксов и игреков будет таким, как в укороченном слове той же длины, получающемся из исходного слова.
Итак, взаимно однозначное соответствие между словами типа $А$ и словами типа $В$, обе части типа $А$ которых начинаются с буквы $X$, установлено.
Тем самым утверждение задачи доказано.
В классе учится одинаковое число мальчиков и девочек (всего класс насчитывает не менее 4 человек). Их в различном порядке выстраивают в один ряд и смотрят, нельзя ли разделить ряд на две части так, чтобы в каждой части девочек и мальчиков было поровну.
Пусть $a$ - число случаев, когда такое разбиение ряда невозможно, a $b$ - число случаев, когда удается разбить ряд на две части с одинаковым числом девочек и мальчиков в каждой из них, но лишь одним способом.
Доказать, что $b = 2a$.
Решение:
Будем говорить, что класс построен в ряд типа $A$, если его нельзя разделить на две части так, чтобы в каждой из них девочек и мальчиков было поровну, и в ряд типа $В$, если такое разбиение возможно, но лишь одним способом.
Пусть $X$ - ученик, стоящий первым. Если $X$ - девочка, то обозначим всех девочек $X$, а всех мальчиков $Y$. Если $X$ - мальчик, то обозначим всех мальчиков $X$, а всех девочек $У$. Поскольку в классе учатся $n$ мальчиков и $n$ девочек, то любое построение класса можно записать в виде последовательности букв $X$ и $Y$, начинающейся с $X$ и содержащей $n$ букв $X$ и $n$ букв $Y$. (В дальнейшем мы будем рассматривать лишь такие последовательности. Назовем их для краткости словами.) Каждому слову соответствуют два построения класса: при одном построении $X$ означает мальчика, при другом - девочку.
Если слово принадлежит к типу $А$, то на какой бы букве (кроме последней) его ни оборвать, в укороченном слове букв $X$ окажется по крайней мере на 1 больше, чем букв $Y$. Действительно, поскольку укороченное слово начинается с $X$ и при увеличении длины слова число иксов и игреков меняется на единицу, то «перевес» игреков над иксами может быть достигнут лишь после того, как число иксов и игреков в каком-то укороченном слове станет одинаковым. Но поскольку рассматриваемое слово принадлежит типу $А$, то это невозможно.
Слово принадлежит типу $В$ тогда и только тогда, когда его можно разбить на два более коротких слова типа $А$. Первое из этих «подслов» начинается с буквы $X$, второе может начинаться и с $X$, и с $У$. Если второе под-слово типа $А$ начинается с $У$, то, заменив в нем $X$ на $Y$, а $У$ на $X$, мы получим снова слово типа $А$. Поэтому все слова типа $В$ разбиваются на пары, в каждой из которых первые подслова одинаковы, а вторые получаются указанной заменой букв. Таким образом, утверждение задачи будет доказано, если мы убедимся в том, что каждому слову типа $А$ взаимно однозначно соответствует слово типа $В$, у которого обе части типа $А$ начинаются с буквы $X$.
Требуемое соответствие можно получить, переставив букву $X$, с которой начинается вторая часть слова типа $В$ (сама вторая часть представляет собой укороченное слово типа $A$), на первое место перед всем словом.
Докажем, что полученное слово принадлежит типу $A$. Действительно, как было показано выше, оборвав первую часть (укороченное слово типа $А$) исходного слова типа $В$ на любой букве, кроме последней, мы получим новое (укороченное) слово, содержащее иксов по крайней мере на один больше, чем игреков. Обрывая слово, которое возникло после того, как перед первой буквой $X$ поставили букву $X$, с которой начиналась вторая часть типа $A$ исходного слова, на любой букве, начиная со второй, мы будем получать укороченные слова, содержащие иксов по крайней мере на два больше, чем игреков, до тех пор, пока не дойдем до последней буквы первой части. Эта буква в новом слове стоит на том месте, где в исходном слове типа $В$ стояла первая буква второй части типа $А$. Оборвав новое слово на последней букве первой части типа $А$ исходного слова, мы получим укороченное слово, которое содержит иксов по крайней мере на один больше, чем игреков. Обрывая новое слово на любой букве, начиная со второй буквы второй части типа $А$ исходного слова, мы будем получать укороченные слова, в которых соотношение иксов и игреков будет таким же, как в укороченном слове, полученном при обрыве на той же букве исходного слова типа $В$. Следовательно, в любом из укороченных слов иксов будет больше, чем игреков. «Равновесие» наступит, лишь когда мы дойдем до самой последней буквы.
Наоборот, в любом слове типа $А$ должна быть еще одна буква, кроме первой, такая, что, оборвав на ней исходное слово, мы получим укороченное слово, в котором иксов на одну букву больше, чем игреков (миновав первую букву, мы, очевидно, получаем «перевес» в одну букву для иксов). Впишем $X$ после этой буквы, а самую первую букву $X$ исходного слова зачеркнем. Новое слово начинается с буквы $X$, поскольку если бы второй буквой исходного слова была буква $У$, то, оборвав его на второй букве, мы получили бы разбиение слова типа $А$ на две части, каждая из которых содержит одинаковое число иксов и игреков (по условиям задачи исходное слово содержит не менее четырех букв), что невозможно. Зачеркнув первую букву $X$, мы уменьшили разность между числим букв $X$ и $Y$ во всех укороченных словах, правый конец которых находится не дальше вписанной буквы $X$, на 1. Для укороченного слова, кончающегося на букве, стоящей перед вписанной буквой $X$, эта разность до зачеркивания первой буквы $X$ была равна 1. Следовательно, после зачеркивания разность между числом иксов и игреков для этого слова стала равной нулю. Следовательно, оборвав получившееся слово на этой букве, но не раньше, мы разобьем его на две части, в каждой из которых букв $X$ и $Y$ будет поровну. Любое укороченное слово, конец которого находится не левее вписанной буквы $X$, будет содержать больше иксов, чем игреков, поскольку в этом слове соотношение иксов и игреков будет таким, как в укороченном слове той же длины, получающемся из исходного слова.
Итак, взаимно однозначное соответствие между словами типа $А$ и словами типа $В$, обе части типа $А$ которых начинаются с буквы $X$, установлено.
Тем самым утверждение задачи доказано.
