2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Вроде бы простая комбинаторика
Сообщение15.08.2014, 15:09 


28/11/11
260
ИСН в сообщении #896304 писал(а):
Я не буду Вам больше говорить, сколько человек лучше взять для начала. Вообще бросьте эту задачу. У Вашего ружья согнулся ствол, и оно стреляет за угол. Ничего понять нельзя.

Ой, теперь понял -- что за числа 6 и 3. Только сейчас дошло. (Извините, что туплю)
Давайте пронумеруем их 1,2,3,4,5,6

Если никто попарно не знаком, то условия задачи удовлетворяются.

Если только 1 и 2 спартанец попарно знакомы, то условия задачи удовлетворяются.

Если только 1 и 2 и 3 спартанец попарно знакомы, то условия задачи удовлетворяются (3-4, 4-5, 5-6, 1-6 попарно не знакомы).

Если только 1 и 2 и 3 и 4 спартанец попарно знакомы, то условия задачи удовлетворяются (4-5, 5-6, 1-6 попарно не знакомы).

Если только 1 и 2 и 3 и 4 и 5 спартанец попарно знакомы, то условия задачи удовлетворяются (5-6, 1-6, 2-6, 3-6 попарно не знакомы).

Если только 1 и 2 и 3 и 4 и 5 и 6 спартанец попарно знакомы, то условия задачи удовлетворяются, так как нашлись 3 попарно знакомых спартанца.

Остальные варианты получаются переобозначением номеров, верно ли?

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


18/05/06
13435
с Территории
Примерно так. Только обычно находят способ записать это намного короче. Ещё Вы пропускаете мимо большую часть вариантов, а ещё ищете не то, что спрашивают в условии. А всё остальное верно.

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение15.08.2014, 16:32 


28/11/11
260
ИСН в сообщении #896468 писал(а):
Примерно так. Только обычно находят способ записать это намного короче. Ещё Вы пропускаете мимо большую часть вариантов, а ещё ищете не то, что спрашивают в условии. А всё остальное верно.

Спасибо.
То есть так? Если менее трех спартанцев попарно знакомы, то найдутся как минумум три поапарно не знакомых спартанца. Если если три и более попарно знакомы, то условия задачи удовлетворяются. Верно будет так?

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


18/05/06
13435
с Территории
Первая часть этого утверждения, хотя по сути и верная, далека от очевидности, и кроме того, сформулирована в неоднозначных терминах.

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение16.08.2014, 13:20 


28/11/11
260
ИСН в сообщении #896480 писал(а):
Первая часть этого утверждения, хотя по сути и верная, далека от очевидности, и кроме того, сформулирована в неоднозначных терминах.

Просто не получается двинуться с мертвой точки, то есть ввести удобные обозначения, чтобы начать расписывать случаи... Уже 3 день не могу придумать...

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


18/05/06
13435
с Территории
Стандартное начало такое: у нас либо есть хотя бы один персонаж, знакомый по крайней мере с тремя другими, либо нет. Если есть, то посмотрим на этих трёх и рассмотрим варианты, возникающие при различной конфигурации их взаимных знакомств. Если нет, то...

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение16.08.2014, 18:17 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Попробуйте взять такую аналогию:
Есть 6 точек, каждые 2 из которых соединены или красной или синей линией...

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение16.08.2014, 18:28 


28/11/11
260
ИСН в сообщении #896673 писал(а):
Стандартное начало такое: у нас либо есть хотя бы один персонаж, знакомый по крайней мере с тремя другими, либо нет. Если есть, то посмотрим на этих трёх и рассмотрим варианты, возникающие при различной конфигурации их взаимных знакомств. Если нет, то...

Спасибо,! Если есть персонаж, знакомый с тремя другими, то условия задачи выполнены. Если такого нет такого персонажа, то есть тут несколько вариантов:
1) Есть персонаж, знакомый с двумя другими. Потенциальные ситуации:
а) Есть только один персонаж, знакомый с 2 другими. Берем две пары без этого персонажа (они удовлетв. условиям задачи, так как попарно не знакомы)
б) Есть только два персонажа, знакомых с 2 другими Берем две пары без этих 2 персонажей персонажа (они удовлетв. условиям задачи, так как попарно не знакомы)
в) Есть только 3 персонажа, знакомых с 2 другими (тут не ясно)
г) Есть только 4 персонажа, знакомых с 2 другими (тут не ясно)
д) Есть только 5 персонажей, знакомых с 2 другими (тут не ясно)
е) Есть 6 персонажей, знакомых с 2 другими (тут не ясно)
2) Есть персонажи знакомые либо с одним, либо ни с кем. Тут очевидно, что любая тройка попарно не знакома.

-- 16.08.2014, 18:36 --

General в сообщении #896687 писал(а):
Попробуйте взять такую аналогию:
Есть 6 точек, каждые 2 из которых соединены или красной или синей линией...

Цвет линии означает -- знакомы или нет? Я так уже пробовал делать, но все равно много очень вариантов получалось...

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение16.08.2014, 20:05 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Да-да, цвет означает - знакомы или нет. В таком случае надо доказать, что найдётся одноцветный треугольник.

Возьмём любую точку - всегда ли из неё будет выходить 3 линии одного цвета?

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


18/05/06
13435
с Территории
mr.tumkan в сообщении #896688 писал(а):
Если есть персонаж, знакомый с тремя другими, то условия задачи выполнены.

Каким образом они выполнены? Напоминаю, мы ищем либо трёх таких, которые попарно знакомы, либо трёх таких, которые попарно незнакомы. Что из этого мы тут нашли, и где именно?

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение17.08.2014, 14:09 


28/11/11
260
ИСН в сообщении #896755 писал(а):
mr.tumkan в сообщении #896688 писал(а):
Если есть персонаж, знакомый с тремя другими, то условия задачи выполнены.

Каким образом они выполнены? Напоминаю, мы ищем либо трёх таких, которые попарно знакомы, либо трёх таких, которые попарно незнакомы. Что из этого мы тут нашли, и где именно?

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

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение17.08.2014, 14:13 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Вот надо найти способ сказать это короче, убедительнее, и без картинок. Способ есть, он простой.

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение23.08.2014, 16:52 


28/11/11
260
Рассмотрим 2 случая:

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

Но как быть с 18 и 4? Там куда больше вариантов и пунктов. Начинать нужно также?

Рассмотрим два случая:

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

Верно ли начало?

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


18/05/06
13435
с Территории
Ну вот, случай "3 из 6" Вы добили.
Что касается "4 из 18", там всё пропорционально сложнее и я его на память не помню.

 Профиль  
                  
 
 Re: Вроде бы простая комбинаторика
Сообщение23.08.2014, 21:26 
Заслуженный участник


27/06/08
4058
Волгоград
ИСН в сообщении #898813 писал(а):
Ну вот, случай "3 из 6" Вы добили.
Что касается "4 из 18", там всё пропорционально сложнее и я его на память не помню.
Предлагаю двигаться последовательно.

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

Для этого сначала ответьте на вопрос: может ли у каждого из спартанцев быть ровно по три знакомых?

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

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



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

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


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

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