Question

По кругу сидят 100 детей: 50 мальчиков и 50 девочек. Докажите, что найдутся мальчик и девочка, между которыми сидят ровно двое детей, причём это тоже мальчик и девочка.

Answer 1

Надо доказать, что всегда найдется хотя бы одна четверка рядом  сидящих детей вида (мдмд), (ммдд), (дмдм) или (ддмм). ("м" - мальчик, "д" - девочка). Разобьем всех детей на пары рядом сидящих. Получится 50 пар.

Пусть общее количество пар вида (мд) и (дм) равно k, тогда количество пар (мм) равно (50-k)/2. Количество пар (дд) также равно (50-k)/2 (что, кстати, означает, что k - четное). Рассмотрим все возможные случаи.
1) Если на круге вообще не оказалось пар (мм), и соответственно, пар (дд), то все пары должны быть вида (мд) или (дм), но, как легко видеть, любые 3 таких соседних пары содержат нужную четверку из условия.
2)На круге есть пары (мм), и обязательно столько же пар (дд). Тогда обязательно есть пара (мм) и пара (дд), между которыми, если и есть какие-то другие пары, то только разнополые вида (мд) или (дм). Тогда:
а) Если между (мм) и (дд) вообще нет никаких пар, т.е. имеем четверку (ммдд) или (ддмм) и они удовлетворяют условию.
б) Если между (мм) и (дд) только одна пара (мд) или (дм), то, получается шестерка (мммддд) или (ммдмдд). Очевидно, в такой шестерке есть нужная четверка из условия.
в) Если между (мм) и (дд) находятся две разнополые пары, то, в случае, если это одинаковые пары  (мд)(мд) или (дм)(дм), то они и дают нужную четверку.  Если же разные - (мд)(дм) или (дм)(мд), то получается восьмерка (мммддмдд) или (ммдммддд), которая также содержит нужную четверку из условия.
г) Если между (мм) и (дд) находится 3 или больше разнополых, то как и в пункте 1), в них обязательно есть нужная четверка.

Answer 2

Давайте докажем это утверждение методом от противного (по принципу "доказательство отсутствия").

Предположим, что между каждым мальчиком и девочкой сидит не более одного ребенка (то есть нет двух подряд мальчиков или двух подряд девочек). Это означает, что сидеть может только такие последовательности:

MFMFMFMF... (где M - мальчик, F - девочка).

В этой последовательности видно, что мальчики и девочки чередуются. Если мальчик сидит между двумя девочками (например, ...FMF...), то мальчик сидит между двумя девочками и также находится один мальчик между двумя девочками. Если мальчик сидит между двумя мальчиками (например, ...MMM...), то между ними также находится только один мальчик.

Таким образом, в любой возможной последовательности между каждой парой мальчиков и девочек всегда находится ровно один ребенок, а не двое, как требуется в задаче.

Это противоречие показывает, что предположение о том, что нет мальчика и девочки, между которыми сидят двое детей (тоже мальчик и девочка), неверно. Следовательно, найдутся мальчик и девочка, между которыми сидят ровно двое детей, и это тоже будет мальчик и девочка.