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