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

[karandash_oleg]

Добрый день! Не получается разобраться с задачей, хотелось бы идею понять.

На вечеринку пришло а) 13; б) 14 гостей, причем среди любых трех из них есть двое знакомых. Докажите, что гости могут
разбиться на 4 группы, в каждой из которых все попарно знакомы.

Сразу вопрос -- что значит "есть двое знакомых". Это значит ровно двое знакомых или же хотя бы два знакомых?

а) Возьмем одного человека $a_0$. Подумаем -- со сколькими он может быть знаком. Если для любых трех есть двое знакомых, то разобьем оставшихся $a_1,a_2,...,a_{12}$ на пары. Пусть пары таковы, что четные номера знакомы с нечетными. Эти пары и берем.
Если $a_0$ брать в тройку к каждой из этих пар, тогда условие "среди любых трех из них есть двое знакомых" не будет выполняться, так как если $a_0$ не знаком ни с кем, то если взять $a_0,a_1,a_3$ то там не найдутся двое знакомых. Если нашелся хотя бы один человек, который знаком с $a_0$, то если взять его и его пару + $a_0$, то там будет более двух знакомых.
Значит нельзя построить биекцию из множества $A$ из 6 незнакомых между собой человека в другое множество $B$ из шести незнакомых между собой человека в рамках этой задачи. Но здесь получается слишком много вариантов. Как искать подход к такой задаче?

[atlakatl]

Предположим, что среди 13-ти человек 12 знают каждый каждого, а 13-й не знает никого из них - и для остальных он незнаком. Условие

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

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

в этом случае выполняется. Но "разбиться на 4 группы, в каждой из которых все попарно знакомы" не получится: 13-го нельзя включить ни в одну из групп.
Думаю, что задача неверно изложена.

[grizzly]

atlakatl в сообщении #1038557 писал(а):

Но "разбиться на 4 группы, в каждой из которых все попарно знакомы" не получится: 13-го нельзя включить ни в одну из групп.

А что, по-Вашему, в этом примере не подойдёт деление {1--10, 11, 12, 13}?

[atlakatl]

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

А что, по-Вашему, в этом примере не подойдёт деление {1--10, 11, 12, 13}?

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

[iancaple]

Интересно, а для 9-ти человек и разбиения на 3 группы это верно? тогда отсюда следовало бы сразу решение задачи б)

[grizzly]

atlakatl в сообщении #1038590 писал(а):

Считаю, что выражение "попарно знакомы" подразумевает, что группа состоит минимум из двух субъектов.

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

-- 19.07.2015, 16:43 --

atlakatl
Хм.. Подумав лучше, я понял, что не могу считать корректной фразу: "передо мной сидит 3 группы людей -- в одной 3 человека, а в двух других ни одного" Пожалуй да, лучше специально оговаривать формальные границы применимости бытовых понятий.

[karandash_oleg]

Жаль, что ни на один вопрос из стартпоста не ответили

[grizzly]

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

Жаль, что ни на один вопрос из стартпоста не ответили

Пожалуйста.

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

Сразу вопрос -- что значит "есть двое знакомых". Это значит ровно двое знакомых или же хотя бы два знакомых?

Хотя бы двое.

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

здесь получается слишком много вариантов. Как искать подход к такой задаче?

Подумайте, что нужно изменить в условии задачи, чтобы она стала проще. Измените условие и попробуйте решить более простую задачу. (Это один из общих советов, а данную задачу я ещё не решал.)

[karandash_oleg]

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

Пусть будет $4$ гостя. Рассмотрим первого гостя и всевозможные тройки с ним.

$1,2,3$, $1,2,4$, $1,4,3$.

В каждой из троек есть хотя бы два знакомых.

Если в первой тройке знакомы $1,2$ (если знакомы $1,3$, то рассматривается аналогично), то они же знакомы во второй тройке. Чтобы выполнить условия задачи, в третьей тройке есть три варианта знакомых.

Только вот не понято, как в этом случае следует переформулировать условие задачи.

[grizzly]

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

Только вот не понято, как в этом случае следует переформулировать условие задачи.

Вот видите, значит Ваша проблема была не в том, что

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

здесь получается слишком много вариантов.

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

[iancaple]

A000791 Число Рамсея $R(3,5)=14$, это значит, что из 14 человек можно выбрать либо 3 попарно незнакомых, либо 5 попарно знакомых. Первое условием запрещено, значит, первая группа из 5 человек есть, отбросим ее, останется задача о разбиении 9 человек на 3 группы. А вот дальше такая рекурсия "в лоб" не работает: $R(3,4)=9$, группу из 4 человек отделить можно, останется задача о разбиении 5 человек на 2 группы, но она не всегда разрешима (5 человек на окружности, и каждый знаком только с двумя соседями) Вывод: отделить-то 4 человек в качестве 2-й группы можно, но не стоит это делать так уж произвольно.

[grizzly]

iancaple
Банальное, но забавное наблюдение. Пусть есть всего 4 человека с теми же правилами. Их завсегда можно разбить на 2 группы. Но если связей минимум (2--3, 1--4) это делается однозначно и без ошибок жадным алгоритмом. А если добавить связь 1--2, то ситуация вместо чтоб упроститься, наоборот, усложняется: жадный алгоритм старается ошибиться (1--2 на первом шаге).

Это я к тому, что не всегда можно просто применить даже весьма тяжёлую артиллерию Рамсея.
(А над задачей подумать так и не дошли руки сегодня. Кто знает, может решить её было быстрее, чем разглагольствовать -- надеюсь, что нет :)

[iifat]

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

первая группа из 5 человек есть

Одна группа? Или две, из двух и трёх человек?

[iancaple]

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

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

первая группа из 5 человек есть

Одна группа? Или две, из двух и трёх человек?

Определение чисел Рамсея (частный случай двух аргументов).Пусть полный граф с $R$ вершинами обладает таким свойством: При любой раскраске его ребер в 2 цвета, либо можно выделить полный подграф порядка $m$ с ребрами 1-го цвета, либо полный подграф порядка $n$ с ребрами 2-го цвета. Теорема Рамсея утверждает, что для любых $m,n$ такое $R$ найдется. Тогда можно взять нижнюю грань таких $R$, называемую числом Рамсея $R(m,n)$
Вот мы и взяли 1-й цвет, когда незнакомы, 2-й когда знакомы.

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

не всегда можно просто применить даже весьма тяжёлую артиллерию Рамсея.

Именно это и произошло, на 1м шаге можно отбросить 5 человек, так как утверждение для 9 человек и 3 групп осталось верным. На 2-м шаге я отбросил условно 4 человек, и если оставшихся 5 человек нельзя разбить на 2 группы, то известно, как среди этих 5 человек знакомства устроены, можно исправить отброшенную группу...
Судя по тому, что это условие (без решения) встретилось в

Цитата:

Кружок "Математика, обратная сторона". Второй год обучения.
2009-2010 учебный год.
http://www.kazan-math.info/

- решаема и без ссылок на работы известных математиков

[Null]

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