Question

В классе учатся 30 учеников, у каждого из которых ровно два друга. а) Докажите, что их можно так рассадить за парты (по 2 человека за парту), что по крайней мере за 10-ю партами будут сидеть ученики, являющиеся друзьями. б) Всегда ли учеников можно рассадить за парты так, чтобы за 11-ю партами сидели ученики, являющиеся друзьями?

Answer 1

Ответ:

А) Сделаем 10 групп из трёх ребят, которые дружат между собой,

дальше берём 2 любых ученика из группы и сажаем их за парты вместе.

Б) нет, не всегда. В примере, приведённом в пункте А работает решение только для 10 парт.

Answer 2

а) Для доказательства того, что можно рассадить 30 учеников так, чтобы по крайней мере за 10-ю партами сидели ученики, являющиеся друзьями, давайте воспользуемся принципом Дирихле.

Применим принцип Дирихле к друзьям в следующем виде: представьте, что каждый ученик - это вершина в графе, и проведем ребра между вершинами, представляющими друзей. Теперь у нас есть граф, в котором каждая вершина имеет степень 2, так как у каждого ученика есть ровно два друга.

Поскольку у нас 30 учеников и каждый имеет степень 2, сумма степеней вершин в графе равна 60. Однако общее количество ребер в графе будет равно половине этой суммы, то есть 30 ребер, так как каждая дружба представляет собой одно ребро.

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

Итак, у нас есть 9 пар с по два ребра в каждой, что дает нам общее количество ребер равное 18. Тепак 18 ребер уже использовано внутри парт, и нам нужно добавить еще 12 ребер, чтобы достичь общего числа ребер в 30.

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

Таким образом, мы доказали, что можно рассадить 30 учеников за парты так, чтобы по крайней мере за 10-ю партами будут сидеть ученики, являющиеся друзьями.

б) Однако, всегда ли учеников можно рассадить за парты так, чтобы за 11-ю партами сидели ученики, являющиеся друзьями? Давайте рассмотрим этот случай.

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

Если мы рассмотрим граф, представляющий дружеские связи учеников, то каждая вершина в этом графе будет иметь степень 2. Теперь, у нас есть 30 учеников, каждый из которых имеет степень 2, что делает общую степень вершин в графе равной 60. Однако общее количество ребер в графе будет равно половине этой суммы, то есть 30 ребер.

Если у нас есть 30 учеников и 30 дружеских связей, и мы рассаживаем их за 11 партами так, чтобы за 11-ю партой не сидели ученики, являющиеся друзьями, то это означает, что каждая партa содержит максимум одного из друзей в паре. Таким образом, если ученик A сидит за одной партой, то его друг B сидит за другой партой, и они не могут быть в одной партой. Из этого следует, что за 11-ю партой тоже не будет учеников, являющихся друзьями.

Таким образом, всегда можно рассадить 30 учеников за парты так, чтобы за 11-ю партами не сидели ученики, являющиеся друзьями, и это не противоречит условию.