Question

По кругу сидят мальчики и девочки. Известно, что количество сидящих рядом пар детей одного пола равно количеству сидящих рядом пар разного пола. Докажите, что общее количество детей делится на 4.

Answer 1

Пусть мальчики и девочки образуют многоугольник (2-регулярный граф). Ребро, соединяющее две вершины, покрасим в черный, если две вершины одного пола, и белым в обратном случае. Пусть девочка закодирована числом 0, а мальчик — 1.

Нетрудно видеть, что граф разделился на чередующиеся островки белого и черного. На концах черных островков стоят одинаковые числа. Сумма концов черных островков четна. Поэтому сумма концов белых островков тоже четна. Рассмотрим два вида белых островков — те, что содержат четное количество ребер, и те, что содержат нечетное их количество. Нечетные белые островки имеют начало и конец в разных цифрах, а поскольку сумма цифр четна, то нечетных белых островков четное количество.

Пусть $w$ — суммарное количество белых островков, а $b$ — суммарное количество черных. По условию $w=b$, значит, $b$ четно. Всего $w+b$ ребер, что равно $2w$ — делится на 4. Количество ребер совпадает с количеством детей.

Answer 2

Давайте обозначим количество мальчиков как M и количество девочек как Д. Так как мальчики и девочки сидят в круге, общее количество детей равно M + Д.

Поскольку количество сидящих рядом пар детей одного пола равно количеству сидящих рядом пар разного пола, давайте рассмотрим два случая:

1. Два соседних детей одного пола сидят рядом. В этом случае можно сказать, что сначала дети сидят в группах, например, МММ...ДДД, и мы видим, что общее количество детей делится на 2 (так как каждая пара детей одного пола сидит рядом).

2. Два соседних детей разного пола сидят рядом. Теперь опять сначала дети сидят в группах, например, МДМДМ... и видим, что общее количество детей делится на 2 (по аналогии с предыдущим случаем).

Теперь объединим эти два случая. Общее количество детей делится на 2 из-за пар детей одного и разного пола, но теперь заметим, что каждая пара детей одного пола граничит с парой детей разного пола (MMDMMD... или DMDMDM...).

Из этого следует, что общее количество детей делится на 4. Таким образом, мы доказали, что если количество сидящих рядом пар детей одного пола равно количеству сидящих рядом пар разного пола, то общее количество детей делится на 4.