Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.

Здравствуйте, nikholas, Вы писали:

N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.

Попарно знакомых — то есть, если есть люди A, B, C и D, то:

A знаком с B, C, D
B знаком с A, C, D
C знаком с B, A, D
D знаком с B, C, A

Соответственно, попарно незнакомые — значит, что среди A, B, C, D никто друг с другом не знаком?

Я правильно понял?

Здравствуйте, nikholas, Вы писали:

N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых."

Это доказали Greenwood & Gleason в статье Combinatorial Relations and Chromatic Graphs в 1955 году.

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, nikholas, Вы писали:

N>>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых."

N>Это доказали Greenwood & Gleason в статье Combinatorial Relations and Chromatic Graphs в 1955 году.

Так же не интересно! А решить на коленке?

Здравствуйте, nikholas, Вы писали:

N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.
Принцип Дирихле.

Здравствуйте, demi, Вы писали:

D>Принцип Дирихле.

Стратегия филина.

Поясни, как воспользоваться здесь принципом Дирихле, иначе это ни о чём.

Здравствуйте, nikholas, Вы писали:


N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых."
N>Так же не интересно! А решить на коленке?

задачу нужно свести к такой:

есть 18 вершин графа
все вершины соединины рёбрами, которые могут быть двух цветов.
Доказать, что есть подграф из 4-вершин, которые соединины рёбрами одного цвета.

Здравствуйте, nikholas, Вы писали:

N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.

Зуб даю, так и есть!

Здравствуйте, nikholas, Вы писали:

N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.

Доказать, что среди любых 9 человек есть либо трое попарно знакомых, либо четверо попарно незнакомых.

Здравствуйте, nikholas, Вы писали:

N>Доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.

Задача довольно простая, но много писанины

Лемма 1: Среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
Док-во: Возьмем любого человека из этой шестерки. По принципу Дирихле из оставшихся 5 человек у него будет либо трое знакомых, либо трое незнакомых.
Без ограничения общности будем считать, что имеется трое знакомых. Если среди этих троих есть двое, которые знакомы,
то они вместе с выбранным человеком дадут тройку попарно знакомых. Иначе эти трое будут попарно незнакомы. Что и требовалось доказать.

Лемма 2: Среди любых 9 человек есть либо трое попарно знакомых, либо четверо попарно незнакомых.
Док-во:
Возможны только следующие случаи:
1) Существует человек A у которого есть по крайней мере 4 знакомых.
2) Существует человек A у которого менее двух знакомых
3) У каждого человека ровно три знакомых.

Покажем, что в кажом случае выполнено утверждение леммы.
В самом деле.
В первом случае, если среди четверых знакомых есть двое, которые знакомы,
то они вместе с человеком A дадут тройку попарно знакомых. Иначе эти четверо будут попарно незнакомы.

Во втором случае, если рассмотреть людей, с которыми A не знаком, то их будет 6 человек.
По лемме 1 среди этих 6-ти будут либо трое попарно знакомых ( что дает нам искомую тройку ), либо трое попарно незнакомых.
Но эти трое попарно незнакомых также не знакомы и с A. Т.е вместе с ним дадут четверку попарно незнакомых.

В третьем случае возьмем любого человека и обозначим его A. У A будет ровно три знакомых. Обозначим их A1, A2, A3.
Оставшихся людей обозначим B1, B2, B3, B4, B5. Никто из {B1, B2, B3, B4, B5} не знаком с A.
Если среди A1, A2, A3 есть двое знакомых, то они вместе с A образуют искомую тройку попарно знакомых.

Остается случай, когда A1, A2, A3 попарно незнакомы. Но каждый из них имеет по три знакомых. Один из них A.
Значит, остальные два среди {B1, B2, B3, B4, B5}. Тогда, по приницпу Дирихле, кто то из {B1, B2, B3, B4, B5}
имеет по крайней мере двух знакомых среди {A1, A2, A3}. Без ограничения общности пусть это B1.
Но тогда B1 имеет по крайней мере трех незнакомых среди {B2, B3, B4, B5}.
Без ограничения общности пусть это {B2, B3, B4}.
Тогда возможно два случая
3.1 {B2, B3, B4} тройка попарно знакомых
3.2 {B2, B3, B4} не тройка попарно знакомых. Без ограничения общности считаем, что B2 и B3 не знакомы.
Тогда {A, B1, B2, B3} будет четверкой попарно незнакомых.
Что и требовалось доказать

Доказательство основной задачи: среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.

Выберем любого человека. По принципу Дирихле у него будет либо 9 знакомых, либо девять незнакомых.
Без ограничения общности будем считать, что у него будет 9 знакомых. Тогда по лемме 1 возможно два случая
1) среди этих 9 будет тройка попарно знакомых. Тогда эта тройка и выбранный нами человек образуют четверку попарно незнакомых
2) среди этих 9 будет четверка попарно незнакомых. Это и будет искомая четверка
Что и требовалось доказать