Знакомые люди, незнакомые люди. Задача на док-во.

[Someone]

Можно попробовать следующий подход. Рассмотрим случай 13 человек.
Если все друг с другом знакомы, то разбить на 4 требуемые группы можно как угодно.
Пусть имеется пара человек (обозначим их $A$ и $B$), которые не знакомы друг с другом. Тогда каждый из них должен быть знаком со всеми остальными, и мы получаем граф на левом рисунке (вертикальная пунктирная линия означает, что некоторые из этих 11 могут быть знакомы между собой, а некоторые — нет).
Если все 11 человек на вертикальной линии знакомы между собой, то разбиение на 4 требуемые группы получается тривиально.
Пусть среди этих 11 имеется пара незнакомых между собой (обозначим их $C$ и $D$). Тогда каждый из них знаком со всеми остальными, и мы получаем граф на правом рисунке.

\xymatrix{ &\bullet\ar@{-}[dddddl]\ar@{-}[dddddr]\ar@{.}[dddddddddd]&& &&&&&\\ &\bullet\ar@{-}[ddddl]\ar@{-}[ddddr]&& &&\bullet\ar@{-}[dddll]\ar@{-}[dddddll]\ar@{-}[ddrr]\ar@{-}[ddddddrr]\ar@{.}[dddddddd]&&\\ &\bullet\ar@{-}[dddl]\ar@{-}[dddr]&& &&\bullet\ar@{-}[ddll]\ar@{-}[ddddll]\ar@{-}[drr]\ar@{-}[dddddrr]&&\\ &\bullet\ar@{-}[ddl]\ar@{-}[ddr]&& &&\bullet\ar@{-}[dll]\ar@{-}[dddll]\ar@{-}[rr]\ar@{-}[ddddrr]&&B\ar@{-}[dddllll]\ar@{-}[dddd]\\ &\bullet\ar@{-}[dl]\ar@{-}[dr]&& A\ar@{-}[dd]\ar@{-}[dddrrrr]&&\bullet\ar@{-}[ll]\ar@{-}[ddll]\ar@{-}[urr]\ar@{-}[dddrr]&&&\\ A&\bullet\ar@{-}[l]\ar@{-}[r]&B &&&\bullet\ar@{-}[ull]\ar@{-}[dll]\ar@{-}[uurr]\ar@{-}[ddrr]&&&\\ &\bullet\ar@{-}[ul]\ar@{-}[ur]&& C&&\bullet\ar@{-}[uull]\ar@{-}[ll]\ar@{-}[uuurr]\ar@{-}[drr]&&\\ &\bullet\ar@{-}[uul]\ar@{-}[uur]&& &&\bullet\ar@{-}[uuull]\ar@{-}[ull]\ar@{-}[uuuurr]\ar@{-}[rr]&&D\\ &\bullet\ar@{-}[uuul]\ar@{-}[uuur]&& &&\bullet\ar@{-}[uuuull]\ar@{-}[uull]\ar@{-}[uuuuurr]\ar@{-}[urr]&&\\ &\bullet\ar@{-}[uuuul]\ar@{-}[uuuur]&& &&\bullet\ar@{-}[uuuuull]\ar@{-}[uuull]\ar@{-}[uuuuuurr]\ar@{-}[uurr]&&\\ &\bullet\ar@{-}[uuuuul]\ar@{-}[uuuuur]& &&&&& }

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

[iancaple]

Someone в сообщении #1038847 писал(а):

Пусть имеется пара человек (обозначим их $A$ и $B$), которые не знакомы друг с другом. Тогда каждый из них должен быть знаком со всеми остальными

А в условии не так:

Цитата:

среди любых трех из них есть двое знакомых

[Someone]

Хм, не так понял. Жаль, хорошая была идея.

[iifat]

iancaple в сообщении #1038885 писал(а):

Пусть имеется пара человек (обозначим их $A$ и $B$), которые не знакомы друг с другом. Тогда каждый из них должен быть знаком со всеми остальными

Таки не понимаю. Если двое незнакомы, то каждый из оставшихся знаком хотя бы с одним из них — понятно. Но почему каждый из них знаком со всеми остальными?
Например: три человека $A, B, C$, $B$ и $C$ знакомы — и только. $A$ и $B$ незнакомы, при этом $A$ незнаком с $C$.

[Someone]

iifat в сообщении #1038893 писал(а):

Но почему каждый из них знаком со всеми остальными?

Это я неправильно понял условие.

[iifat]

iancaple в сообщении #1038800 писал(а):

Определение чисел Рамсея

Я немного не о том. Пусть в нашем графе есть полный подграф из пяти вершин. Мы можем взять его одной группой, а можем двумя.

Null в сообщении #1038813 писал(а):

расстояние между любой парой вершин не превосходит 2

Что-то я сомневаюсь. Берём два полных графа, объединяем в один (с двумя компонентами связности) — и получаем удовлетворяющий условию граф, в котором некоторые из вершин имеют расстояние $\infty$, не?

[grizzly]

iifat в сообщении #1038910 писал(а):

Null в сообщении #1038813 писал(а):

расстояние между любой парой вершин не превосходит 2

Что-то я сомневаюсь. Берём два полных графа, объединяем в один (с двуья компонентами связности) — и получаем удовлетворяющий условию граф, в котором некоторые из вершин имеют расстояние $\infty$, не?

Это да, но это вырожденный случай, для которого решение задачи становится тривиальным. Если можно что-то доказать для невырожденного случая, это тоже интересно. Хорошо бы Null поделился своими идеями.

[iifat]

(Оффтоп)

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

Нам ведь ни то, ни другое не помогает

Естественно, не помогает. Чтобы помочь, надо знать решение. Не мой случай

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

это вырожденный случай

В каком смысле? Граф знакомств может состоять из одной либо двух компонент связности, это я понимаю. Чем случай двух компонент проще (вырожденнее?) — пока не очень.

-- 21.07.2015, 00:11 --

Ну, вот. Я процитировал, вы убрали и у меня цитата ниоткуда. Хотите, чтоб я тоже убрал?

[grizzly]

iifat в сообщении #1038914 писал(а):

Ну, вот. Я процитировал, вы убрали и у меня цитата ниоткуда. Хотите, чтоб я тоже убрал?

Нет-нет, пусть будет. Я сам виноват -- надо думать до, а не после

iifat в сообщении #1038914 писал(а):

Чем случай двух компонент проще (вырожденнее?) — пока не очень.

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

Но если соединить 2 компоненты связности одним ребром, то расстояние между некоторыми вершинами станет 3. Так что да -- Null или ошибся или рассматривал отдельные случаи.

[iifat]

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

Если граф разбит на 2 компоненты, то отсюда следует, что каждая из компонент обязательно полный граф

Действительно. Да, вы правы, это вырожденный случай.

[karandash_oleg]

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

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

Подкачался немного.
Теперь могу доказать, что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых.
Теперь могу доказать, что среди любых 9 человек есть либо трое попарно знакомых, либо четверо попарно незнакомых.
Теперь могу доказать, что среди любых 18 человек есть либо четверо попарно знакомых, либо четверо попарно незнакомых.
(стоит ли писать здесь доказательства?)
Но боюсь, что это здесь не поможет. Если воспользоваться тем, что "что среди любых 6 человек есть либо трое попарно знакомых, либо трое попарно незнакомых". У нас из условия задачи сразу же следует, что среди 6 найдутся 3 попарно знакомых. Но боюсь, что это не поможет. Исходя из содержания этой темы, мне начинает казаться, что задача совсем сложная...

[grizzly]

karandash_oleg в сообщении #1038930 писал(а):

стоит ли писать здесь доказательства?

Все не стоит. Приведите первое. Два других не могут пригодиться в этой задаче. Теперь Вы можете решить задачу для меньшего числа человек? Хотя бы для 10 (разбиваем на те же 4 группы)? Если можете -- приведите, это уже плюс и польза. Можете больше -- ещё лучше. Если для 10 самостоятельно не сможете, лучше забыть пока о первоначальной задаче -- от безуспешных попыток решения непосильных задач пользы не будет.

karandash_oleg в сообщении #1038930 писал(а):

Исходя из содержания этой темы, мне начинает казаться, что задача совсем сложная...

Может и сложная. Точно, что нетривиальная, раз несколько человек посмотрели и с ходу никто не решил. Не исключено также, что она просто неудобная для решения в уме.

[karandash_oleg]

Давайте знакомых соединять красных линией (теплые), незнакомых -- синей. Занумеруем людей цифрами 1,2,..,6.
Возьмем первого человека из 6. Если 1 знаком с тремя или более (например 2,3,4), то если среди троих 2,3,4 попарно знакомых нет, то они образуют синий треугольник, а если есть (например, 2,3), то 1,2,3 будут образовывать красный треугольник. Если первый знаком менее чем с двумя, то найдутся три человека, с которыми первый не знаком. Эта ситуация рассматривается аналогично (нужно лишь синий заменить красным, красный -- синим).

Попробую для 10 человек. Возьмем в первую группу 6 человек. Там найдутся трое знакомых, пусть будут 1,2,3 (если номера другие, переобозначим). Пусть они образуют первую категорию. Из 3,4,5,6,7,8 найдутся трое знакомых. Пусть это будут 3,4,5 (если другие номера, переобозначим как 3,4,5). Уже есть две группы по три попарно знакомых человека. Возьмем 6,7,8,9,10. До шести человек не хватает одного. Отщепнем от второй категории номер 5. Для 5,6,7,8,9,10 делаем тоже самое, что и для 1,2,3,4,5,6.
Среди 8,9,10 найдутся двое знакомых.
Получаем 4 категории попарно знакомых людей|1,2,3|4,5|6,7,8|9,10|
Только что-то мне кажется, что не так с этими переобозначениями!

-- 20.07.2015, 21:18 --

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

Если для 10 самостоятельно не сможете, лучше забыть пока о первоначальной задаче -- от безуспешных попыток решения непосильных задач пользы не будет.

А что имеет смысл порешать тогда?

[grizzly]

karandash_oleg в сообщении #1038983 писал(а):

Если первый знаком менее чем с двумя, то найдутся три человека, с которыми первый не знаком. Эта ситуация рассматривается аналогично (нужно лишь синий заменить красным, красный -- синим).

Вы уверены, что понимаете это "аналогично"? Я в этом сомневаюсь.

karandash_oleg в сообщении #1038983 писал(а):

Там найдутся трое знакомых, пусть будут 1,2,3 (если номера другие, переобозначим). Пусть они образуют первую категорию. Из 3,4,5,6,7,8 найдутся трое знакомых. Пусть это будут 3,4,5 (если другие номера, переобозначим как 3,4,5). Уже есть две группы по три попарно знакомых человека...

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

karandash_oleg в сообщении #1038983 писал(а):

А что имеет смысл порешать тогда?

Может кто-то другой даст Вам совет. Я правда не знаю, что посоветовать по вышеизложенным причинам.

-- 20.07.2015, 21:38 --

karandash_oleg в сообщении #1038983 писал(а):

Только что-то мне кажется, что не так с этими переобозначениями!

А вот наличие правильных сомнений -- это хороши знак. Правда.

[grizzly]

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

Итак, всего 14 точек. Пусть $A_1$ -- точка с минимальным количеством рёбер. Число этих рёбер не может быть слишком мало, иначе все точки кроме соседских образуют большой полный подграф. Но это число не может быть и слишком велико по обратным причинам. Остаётся рассмотреть от 7 до 10 рёбер. Крайние 7 и 10 рассмотрим для тренировки.

Пусть 7 рёбер идут из т. $A_1$ в $A_2-A_8$. Тогда $A_9-A_{14}$ образуют полный 6-подграф (что очевидно после соединения каждой пары его точек с $A_1$). 7 точек $A_2-A_8$ легко разбить на 3 подграфа (отделить тройку и разделить 4 на $2+2$ или $3+1$); $A_1$ присоединяем к любому из них.

Пусть теперь 10 рёбер из т. $A_1$ в $A_2-A_{11}$. Тогда $A_{12}-A_{14}$ образуют полный 3-подграф. Проводя по 8 рёбер из точек этого подграфа на множество $A_2-A_{11},$ легко находим там точку (в пересечении), которой можно дополнить 3-подграф до 4-подграфа. Тогда обрезав пуповину новой точки с $A_1$, сведём задачу к варианту "9 рёбер".

Если кому-то ещё этот путь понравится, можно придумать что-то похитрее для случаев 8 и 9 рёбер. Уже длинно, конечно, но пока тривиально просто.