Вроде бы простая комбинаторика

[mr.tumkan]

ИСН в сообщении #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 попарно знакомых спартанца.

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

[ИСН]

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

[mr.tumkan]

ИСН в сообщении #896468 писал(а):

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

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

[ИСН]

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

[mr.tumkan]

ИСН в сообщении #896480 писал(а):

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

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

[ИСН]

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

[General]

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

[mr.tumkan]

ИСН в сообщении #896673 писал(а):

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

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

-- 16.08.2014, 18:36 --

General в сообщении #896687 писал(а):

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

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

[General]

Да-да, цвет означает - знакомы или нет. В таком случае надо доказать, что найдётся одноцветный треугольник.

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

[ИСН]

mr.tumkan в сообщении #896688 писал(а):

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

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

[mr.tumkan]

ИСН в сообщении #896755 писал(а):

mr.tumkan в сообщении #896688 писал(а):

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

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

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

[ИСН]

Вот надо найти способ сказать это короче, убедительнее, и без картинок. Способ есть, он простой.

[mr.tumkan]

Рассмотрим 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-ая точка и три из перечисленных точек, соединенных синей линией, “образуют четырехугольник с двумя диагоналями (то есть условия задачи выполнены).

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

[ИСН]

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

[VAL]

ИСН в сообщении #898813 писал(а):

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

Предлагаю двигаться последовательно.

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

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