Дружный класс

[Ktina]

В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Может ли оказаться так, что у каждого из учеников -
не более 12 друзей?

[zhekas]

Разделим класс на две группы. В первой 13 человек. Во второй - 12.

В первой и второй группе каждый дружит с каждым. При этом ученики из разных групп не дружат.

Все условия выполняются.

[Ktina]

zhekas
Большое спасибо!
Можно даже менее абстрактно - не просто на две группы по 12 и 13, а представить, что в классе 12 мальчиков и 13 девочек. Все мальчики дружат друг с другом и не дружат с девочками, а все девочки дружат друг с дружкой и не дружат с мальчиками. Так и задумывалась задача.
А вот не более 11 друзей у каждого быть, кстати, не может. Знаете, почему?

[zhekas]

Ktina в сообщении #1265257 писал(а):

zhekas
А вот не более 11 друзей у каждого быть, кстати, не может. Знаете, почему?

Возьмём одного ученика - $a$. Он дружит максимум с 11 учениками (множество $A$). Из оставшихся 13-и выберем ещё одного $b$. Он тоже дружит максимум с одинадцатью учениками (множество $B$). Объединение $a \cup A \cup b \cup B $ даёт максимум $1+11+1+11=24$ ученика. Таким образом остаётся как минимум один ученик $c$, который не дружит ни с $a$ ни с $b$. Тройка $a,b,c$ не удовлетворяет условию задачи.

[grizzly]

zhekas в сообщении #1265287 писал(а):

Из оставшихся 13-и выберем ещё одного $b$. Он тоже дружит максимум с одинадцатью $B$. Объединение $a \cup A \cup b \cup B $ даёт максимум $1+11+1+11=24$ ученика.

Почему $A$ и $B$ не пересекаются? Теперь ведь нет оснований считать, что в $A$ каждый дружит с каждым.

[zhekas]

grizzly в сообщении #1265289 писал(а):

Почему $A$ и $B$ не пересекаются? Теперь ведь нет оснований считать, что в $A$ каждый дружит с каждым.

А кто сказал, что $A$ и $B$ не пересекаются? Они вполне могут пересекаться. Но если они пересекаются, то объединение даёт меньше 24 учеников. И, следовательно, на роль $c$ у нас остаётся выбор из большего количества учеников.

[grizzly]

zhekas
Да, точно.