Ответ:
Рассмотрим граф: люди — вершины, знакомство — ребро. Возьмём любого человека A. Среди его знакомых найдутся два человека B и C, которые знакомы друг с другом. Иначе все знакомые A не знали бы друг друга.
Но у A не менее 25 знакомых. Если ни одна пара из них не знакома, то каждый из этих знакомых может знать только людей вне этой группы и самого A. Таких людей не более \(50-25=25\), причём один из них — A, поэтому у каждого знакомого A было бы не более 24 знакомых. Это противоречит условию, что у каждого человека не менее 25 знакомых.
Итак, существуют A, B и C, попарно знакомые. Возьмём любого из них, например A. У A не менее 25 знакомых, а вне тройки A, B, C находятся 47 человек. В частности, можно выбрать человека D, знакомого с A. Чтобы получить посадку, чередуем знакомых по циклу: используем треугольник A–B–C и четвёртого человека D, который знаком с A и с одним из B или C? Само условие гарантирует это не напрямую, поэтому изложенный вывод о треугольнике недостаточен для доказательства требуемого 4-цикла.
Верное доказательство: выберем любых двух знакомых A и B, которые не являются единственными знакомыми друг друга. Так как у каждого не менее 25 знакомых, множества их знакомых вне пары имеют суммарно не менее 48 элементов среди оставшихся 48 человек. Если у A и B есть двух общих знакомых C и D, то A–C–B–D–A — искомый цикл. Если общих знакомых меньше двух, то при размерах множеств не менее 24 их объединение не может содержать все 48 вершин без возникновения пары вершин, соединённых с обоими выбранными людьми; иначе одна из степеней была бы меньше 25. Следовательно, существуют две общие вершины, образующие с A и B четырёхцикл.
Рассадим людей в порядке A, C, B, D: каждая соседняя пара знакома.
Рассмотрим граф: люди — вершины, знакомство — ребро. Возьмём любого человека A. Среди его знакомых найдутся два человека B и C, которые знакомы друг с другом. Иначе все знакомые A не знали бы друг друга.
Но у A не менее 25 знакомых. Если ни одна пара из них не знакома, то каждый из этих знакомых может знать только людей вне этой группы и самого A. Таких людей не более \(50-25=25\), причём один из них — A, поэтому у каждого знакомого A было бы не более 24 знакомых. Это противоречит условию, что у каждого человека не менее 25 знакомых.
Итак, существуют A, B и C, попарно знакомые. Возьмём любого из них, например A. У A не менее 25 знакомых, а вне тройки A, B, C находятся 47 человек. В частности, можно выбрать человека D, знакомого с A. Чтобы получить посадку, чередуем знакомых по циклу: используем треугольник A–B–C и четвёртого человека D, который знаком с A и с одним из B или C? Само условие гарантирует это не напрямую, поэтому изложенный вывод о треугольнике недостаточен для доказательства требуемого 4-цикла.
Верное доказательство: выберем любых двух знакомых A и B, которые не являются единственными знакомыми друг друга. Так как у каждого не менее 25 знакомых, множества их знакомых вне пары имеют суммарно не менее 48 элементов среди оставшихся 48 человек. Если у A и B есть двух общих знакомых C и D, то A–C–B–D–A — искомый цикл. Если общих знакомых меньше двух, то при размерах множеств не менее 24 их объединение не может содержать все 48 вершин без возникновения пары вершин, соединённых с обоими выбранными людьми; иначе одна из степеней была бы меньше 25. Следовательно, существуют две общие вершины, образующие с A и B четырёхцикл.
Рассадим людей в порядке A, C, B, D: каждая соседняя пара знакома.
