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

[iifat]

О! Это здорово, по-моему.
Проясняется структура графа: выкинув любую вершину, соседние с ней и дуги, из них ведущие, получаем полный граф. Вот что даёт условие, а я никак не мог сообразить.

[karandash_oleg]

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

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

Все я умею рассуждать самостоятельно, причем очень даже хорошо. Другое дело, что мне бывает сложно комбинаторные вещи связно излагать (длинные логические цепочки). То есть я понять их могу и у себя в голове прокрутить, а вот написать -- сложнее, много очень времени занимает аккуратная формулировка. Да и сама обработка многоплановых задач занимает много времени, долго вникаю.
Вот я и хочу как-то прокачать себе мозг такими задачами, авось получится. Или думаете -- безнадежно?)
Вот с матанализом у меня очень даже нормально и с линейной алгеброй. С дискретной математикой (комбинаторикой, теорией графов) вечно какие-то потуги, через силу идет, но мне интересно "пробивать непробиваемое", так у меня мозги заряжаются.

Вот доказательство, вторая попытка.
Давайте знакомых соединять красных линией (теплые), незнакомых -- синей.
Нам нужно доказать, что будет найдется красный или синий треугольник.
Возьмем первого человека из 6.
Возможны 2 ситуации:
1) Если первый знаком с тремя или более:
a) Среди тех троих, с которыми знаком первый -- попарно знакомых нет. Трое незнакомцев образуют синий треугольник. чтд
б) Среди тех троих, с которыми знаком первый -- нашлась хотя бы одна пара знакомых. Если взять к этой паре первого человека, то они будут образовывать красный треугольник. чтд
2) Если первый знаком с двумя или менее, то найдутся три человека, с которыми первый незнаком.
a) Среди тех троих, с которыми первый незнаком -- все попарно знакомы. Трое знакомых образуют красный треугольник. чтд
б) Среди тех троих, с которыми первый незнаком -- нашлась хотя бы одна пара незнакомых. Если взять к этой паре первого человека, то они будут образовывать синий треугольник. чтд

[grizzly]

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

Все я умею рассуждать самостоятельно, причем очень даже хорошо.

Ну Вы сами меня спровоцировали. Впрочем, я говорил об "искусстве", а оно действительно необходимо для решения олимпиадных задач.

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

Вот я и хочу как-то прокачать себе мозг такими задачами, авось получится. Или думаете -- безнадежно?)

Нет, не думаю. Вы способны признавать ошибки -- это главное. Тренироваться можно и нужно. Но Вы допускаете глобальную ошибку, пытаясь бросаться на задачи наскоком и поверхностно. Вам нужно найти такие задачи, которые Вы сможете решать не за 10 мин., а за 3--4--5 часов, но самостоятельно. Пусть поначалу это будут простые задачи. Но потом Вы сможете решать более сложные за то же время. С Вашим подходом, как бы Вы не тренировались, Вы не научитесь решать сложные задачи. Но прожить хорошо или интерено можно и без этого -- всё зависит от Ваших целей.

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

Вот доказательство, вторая попытка.
...

Значит, можете

[Null]

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

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

Я использовал ограничение на то что нельзя разбить на 4 группы в которых все попарно знакомы.(От противного)
1. Пусть есть 2 несвязные(путем) вершины $A$ и $B$. $S_A$- знакомые $A$. $S_B$- знакомые $B$.
Если например в $S_A$ есть 2 незнакомых то добавив к ним $B$ получим противоречие условию.
Тогда $S_A \cup \{A\}$ и $S_B \cup \{B\}$ - разбиение (Противоречие).
2. Пусть $A$ - произвольный человек. $S_k$ - люди на рассоянии $k$(минимальная последовательность знакомств).
В $S_k$ и $S_l$ могут быть знакомые только если $|k-l|\le 1$ .
Если множеств $5$ или больше(включая $S_0=\{A\}$), то элементы из $S_0, S_2$ и $S_4$ дают противоречие.
Если множеств $4$, то легко доказать что в них все элементы попарно связны(для каждого множества есть элемент с ним не связанный) - получили противоречие.
Значит множеств $2$ или $3$ - расстояние между $A$ и любой вершиной не превосходит 2.

Я ни где не использовал количество людей.

[grizzly]

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

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

Странно, никаких сложностей. Утро вечера мудренее
Пусть 9 рёбер. Точку $A_1$ и 4-подграф оставляем за скобками. Имеем задачу деления 9 точек на 3 подграфа. Всё так же -- работаем внутри 9 точек. Два варианта.
Пусть минимальное число рёбер -- 4. За скобками полный 4-подграф. 4 точки легко делятся на 2 подграфа.
Пусть минимальное число рёбер -- 5. За скобками полный 3-подграф. Внутри 5 точек, между которыми не меньше 3 рёбер из каждой точки. Легко делятся на 2 подграфа.

Для 8 рёбер не сложнее. Вроде всё.

-- 21.07.2015, 09:50 --

Null
Спасибо! Вы действительно сказали там, что от противного -- я не сообразил насколько. Вообще вчера слишком жарко было для думать

[Skeptic]

Гости встали в круг и взялись за руки. Будем считать, два гостя, взявшиеся за руки знакомы. Условие задачи, что "среди любых трех из них есть двое знакомых", соблюдается. Любое разделение гостей на группы, будет содержать пару незнакомых между собой гостей.

[grizzly]

Skeptic в сообщении #1039150 писал(а):

Гости встали в круг и взялись за руки. Будем считать, два гостя, взявшиеся за руки знакомы. Условие задачи, что "среди любых трех из них есть двое знакомых", соблюдается.

Пусть Ваш хоровод водит 6 человек. Если у них обычные конечности, то среди тройки {1,3,5} нет держащихся за руки. (Об этом говорили раньше в теме.) Но даже если в Вашем примере только 4 человека, их можно разделить на 2 группы знакомых. Поражаюсь, как Вы можете допускать столько логических ошибок в таком коротком тексте, сколько не любой двоечник допустит грамматических.

[karandash_oleg]

Спасибо! Попробую-таки для 10 человек расписать.
Берем 6 человек из 10. Выбираем среди шести этих человек 3 попарно знакомых (а такие найдутся, потому как тройки незнакомцев не может быть по условию). Это будет первая группа.
Среди оставшихся 7 отбираем произвольно 6 человек, среди которых находим 3 попарно знакомых. Это вторая группа.
Теперь есть две группы по 3 человека, в каждой из троек все попарно знакомы.
Дальше остается два варианта разбиения четверки: $2+2$ или же $3+1$

Назовем этих людей $A,B,C,D$.

Среди тройки $A,B,C$ есть двое знакомых по условию.
Рассмотрим человека $A$.
Возможные варианты:
1) Если $A$ знаком с $B$ и при этом $C$ и $D$ тоже знакомы. Тогда у нас образовались две нужные пары.
2) Если $A$ знаком с $B$ и при этом $C$ и $D$ незнакомы. Тогда взяв тройку $A,C,D$, получаем, что $A$ знаком c $C$ или же $A$ знаком с $D$.
2.1) Первый подслучай: $A$ знаком с $B,C$, но при этом $C$ и $D$ незнакомы.
В тройке $B,C,D$ найдутся два знакомых (причем $C$ и $D$ ими быть не могут).
2.1.1) Эти знакомые -- это $B$ и $D$. Тогда у нас образовались пары знакомых $A,C$ и еще $B,D$ чтд
2.1.2) Эти знакомые -- это $B$ и $C$. Тогда $A,B,C$ попарно знакомы. Делаем разбиение первая группа $A,B,C$ и вторая $D$.
2.2) Второй подслучай: $A$ знаком с $B,D$, но при этом $C$ и $D$ незнакомы.
В тройке $B,C,D$ найдутся два знакомых (причем $C$ и $D$ ими быть не могут).
2.1.1) Эти знакомые -- это $B$ и $C$. Тогда у нас образовались пары знакомых $A,D$ и еще $B,C$, чтд
2.1.2) Эти знакомые -- это $B$ и $D$. Тогда $A,B,D$ попарно знакомы. Делаем разбиение первая группа $A,B,C$ и вторая $D$.

Все возможные варианты разобраны. Удалось разбить на четыре группы) Но правильно ли?

[grizzly]

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

Удалось разбить на четыре группы) Но правильно ли?

Да, это то решение, которое я от Вас ожидал.
На этот раз Подслучай 2.2) можно было и не разбирать -- при разборе случая 2.1) можно было сказать: "$A$ знаком с кем-то из $C,D$. Пусть с $C$ (случай с $D$ рассматривается аналогично)". Но пока у Вас нет уверенности в таких подстановках, лучше расписать лишнее, чем рисковать.

Задача для 10, конечно, проще. Но я уверен, что пользы от её самостоятельного решения больше.

[karandash_oleg]

Хорошо, спасибо большое. А аналогичным подходом получится ли решить исходную задачу?
Уже попробовал разбивать на тройки, как и в задаче, где 10 человек, но пока что не получается.

[grizzly]

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

А аналогичным подходом получится ли решить исходную задачу?

Нет, не получится. Троек, сами понимаете, там уже недостаточно -- нужны четвёрки и пятёрки. А доказывать, что "из 14 можно выбрать 5" таким же способом, как "из шести три" -- Вы не одну клавиатуру до дыр истопчете.

[karandash_oleg]

С учетом того, что задача для 7 класса, вряд ли подразумевается, что здесь какой-то тяжелый матаппарат нужен)

-- 21.07.2015, 19:25 --

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

Я использовал ограничение на то что нельзя разбить на 4 группы в которых все попарно знакомы.(От противного)
1. Пусть есть 2 несвязные(путем) вершины $A$ и $B$. $S_A$- знакомые $A$. $S_B$- знакомые $B$.
Если например в $S_A$ есть 2 незнакомых то добавив к ним $B$ получим противоречие условию.
Тогда $S_A \cup \{A\}$ и $S_B \cup \{B\}$ - разбиение (Противоречие).
2. Пусть $A$ - произвольный человек. $S_k$ - люди на рассоянии $k$(минимальная последовательность знакомств).
В $S_k$ и $S_l$ могут быть знакомые только если $|k-l|\le 1$ .
Если множеств $5$ или больше(включая $S_0=\{A\}$), то элементы из $S_0, S_2$ и $S_4$ дают противоречие.
Если множеств $4$, то легко доказать что в них все элементы попарно связны(для каждого множества есть элемент с ним не связанный) - получили противоречие.
Значит множеств $2$ или $3$ - расстояние между $A$ и любой вершиной не превосходит 2.

Я ни где не использовал количество людей.

Спасибо. Я прекрасно понял пункт 1, а вот пункт 2 совсем не понял. Подскажите, пожалуйста, -- что значит "люди на расстоянии" и "последовательность знакомств" в данном контексте?

[grizzly]

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

Я ни где не использовал количество людей.

Интересно, что мы делали похожие шаги, но я -- комбинаторным способом, Вы -- скажем так, теоретико-множественным. Только я доказываю чуть больше: либо расстояние между любыми точками равно 2, либо можно разбить на 3 полных подграфа. Я сейчас переведу основную свою идею на язык Вашего подхода, чтобы объяснить, о чём я говорю.

Забудем про 14 человек. Пусть будет $N$.

На первом шаге я выберу произвольную точку $A=S_0$. На втором шаге я строю множество $S_1.$ На третьем шаге я рассмотриваю множество оставшихся точек $S$ -- очевидно, полный граф (иначе существует треугольник с $A$). Докажем, что $S=S_2$ или существует разбиение на 3 полных подграфа. Пусть в $S$ есть точка $M,$ расстояние от которой до $A$ больше 2. Это в точности значит, что $M$ не соединена ни с одной точкой множества $S_1$. Тогда либо $S_1$ тоже полный граф (имеем разбиение на 3 подграфа), либо найдём треугольник, противоречащий условию.

Мне пока лень додумать это в Ваших терминах, но надеюсь, что на самом деле там результат аналогичный (или расстояние 2 или можно разбить на 3 группы). Или это я где-то ошибаюсь?

Остаётся смутное ощущение, что эти идеи можно ещё сколько-то развить и поэксплуатировать в плане других задач. Хорошо бы ещё сообразить, нет ли тут более глубокой связи с Рамсеем.

[Skeptic]

Графическое решение

[iifat]

Skeptic в сообщении #1039278 писал(а):

Графическое решение

Не помешало бы доказательство, что граф для 13 и 14 вершин определяется условием с точностью до изоморфизма. Ну, либо ещё несколько (сот?) таких рисунков. И да, от доказательства этот метод не освобождает.