25 мальчиков и 25 девочек

*

Сложность: 

25 мальчиков и 25 девочек сидят за круглым столом. Докажите, что у кого-то оба соседа — девочки.

Подсказка

Нужно воспользоваться соображениями чётности. Если бы мальчиков и девочек было по 24, то задача не имела бы смысла.

Решение

Будем доказывать утверждение от противного. Предположим, что 25 мальчиков и 25 девочек удалось рассадить за круглым столом так, что у каждого ребёнка хотя бы один из соседей — мальчик.

Разобьём всех сидящих за столом детей на максимально возможные непрерывные группы, состоящие только лишь из одних мальчиков или только лишь из одних девочек (непрерывность группы означает, что все её участники сидят подряд, без разрывов). Ясно, что группы, содержащие только мальчиков, и группы, содержащие только девочек, чередуются между собой (иначе не будет выполнено требование максимальной непрерывности каждой группы). Кроме того, так как дети сидят по кругу, то групп одного типа должно быть ровно столько же, сколько групп второго типа.

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

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

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




Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.