2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 13:24 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Можно попробовать следующий подход. Рассмотрим случай 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 группы строится очень легко.
В противном случае нужно попробовать продолжить рассуждения в том же духе.

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 15:02 
Аватара пользователя


29/06/15
277
[0,\infty )
Someone в сообщении #1038847 писал(а):
Пусть имеется пара человек (обозначим их $A$ и $B$), которые не знакомы друг с другом. Тогда каждый из них должен быть знаком со всеми остальными

А в условии не так:
Цитата:
среди любых трех из них есть двое знакомых
:cry:

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 15:09 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Хм, не так понял. Жаль, хорошая была идея.

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 15:16 
Заслуженный участник


16/02/13
4105
Владивосток
iancaple в сообщении #1038885 писал(а):
Пусть имеется пара человек (обозначим их $A$ и $B$), которые не знакомы друг с другом. Тогда каждый из них должен быть знаком со всеми остальными
Таки не понимаю. Если двое незнакомы, то каждый из оставшихся знаком хотя бы с одним из них — понятно. Но почему каждый из них знаком со всеми остальными?
Например: три человека $A, B, C$, $B$ и $C$ знакомы — и только. $A$ и $B$ незнакомы, при этом $A$ незнаком с $C$.

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 15:36 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
iifat в сообщении #1038893 писал(а):
Но почему каждый из них знаком со всеми остальными?
Это я неправильно понял условие.

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 16:42 
Заслуженный участник


16/02/13
4105
Владивосток
iancaple в сообщении #1038800 писал(а):
Определение чисел Рамсея
Я немного не о том. Пусть в нашем графе есть полный подграф из пяти вершин. Мы можем взять его одной группой, а можем двумя.
Null в сообщении #1038813 писал(а):
расстояние между любой парой вершин не превосходит 2
Что-то я сомневаюсь. Берём два полных графа, объединяем в один (с двумя компонентами связности) — и получаем удовлетворяющий условию граф, в котором некоторые из вершин имеют расстояние $\infty$, не?

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 16:59 
Заслуженный участник
Аватара пользователя


09/09/14
6328
iifat в сообщении #1038910 писал(а):
Null в сообщении #1038813 писал(а):
расстояние между любой парой вершин не превосходит 2
Что-то я сомневаюсь. Берём два полных графа, объединяем в один (с двуья компонентами связности) — и получаем удовлетворяющий условию граф, в котором некоторые из вершин имеют расстояние $\infty$, не?

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 17:08 
Заслуженный участник


16/02/13
4105
Владивосток

(Оффтоп)

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


-- 21.07.2015, 00:11 --

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 17:23 
Заслуженный участник
Аватара пользователя


09/09/14
6328
iifat в сообщении #1038914 писал(а):
Ну, вот. Я процитировал, вы убрали и у меня цитата ниоткуда. Хотите, чтоб я тоже убрал?

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

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

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

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 17:27 
Заслуженный участник


16/02/13
4105
Владивосток
grizzly в сообщении #1038915 писал(а):
Если граф разбит на 2 компоненты, то отсюда следует, что каждая из компонент обязательно полный граф
Действительно. Да, вы правы, это вырожденный случай.

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 18:27 


04/06/13
203
grizzly в сообщении #1038744 писал(а):
Следующий совет общего плана: потратьте больше времени на обдумывание задачи. Если всё равно не будет никаких идей, можно отвлечься на несколько дней, сменив род деятельности. Потом снова вернитесь к обдумыванию. Если совсем беспросветно, попробуйте "подкачаться" на задачах попроще.

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 19:58 
Заслуженный участник
Аватара пользователя


09/09/14
6328
karandash_oleg в сообщении #1038930 писал(а):
стоит ли писать здесь доказательства?

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

karandash_oleg в сообщении #1038930 писал(а):
Исходя из содержания этой темы, мне начинает казаться, что задача совсем сложная...

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 21:10 


04/06/13
203
Давайте знакомых соединять красных линией (теплые), незнакомых -- синей. Занумеруем людей цифрами 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 самостоятельно не сможете, лучше забыть пока о первоначальной задаче -- от безуспешных попыток решения непосильных задач пользы не будет.

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение20.07.2015, 21:36 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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 писал(а):
Только что-то мне кажется, что не так с этими переобозначениями!

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

 Профиль  
                  
 
 Re: Знакомые люди, незнакомые люди. Задача на док-во.
Сообщение21.07.2015, 00:31 
Заслуженный участник
Аватара пользователя


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

Итак, всего 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 рёбер. Уже длинно, конечно, но пока тривиально просто.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group