Задача на комбинаторику

[Marucmp]

Всем доброго времени суток.

Имеется следующая задача: Доказать, что трех футбольных матчей между двумя командами одного клуба (тренировка) достаточно для того, чтобы нашлись такие два футболиста, которые ни одной игры не сыграли вместе.

Решал методом от противного. Т.е. для начала предположил отрицание конечного утверждения, а именно "предположим, что любые два футболиста сыграли вместе". Получаем $\frac{21\cdot(1+21)}{2}=231$ пар футболистов, которые должны вместе сыграть. После этого нужно получить противоречие с тем, что эти пары невозможно разместить в 6 множеств, представляющих игры. Но каждое из них обеспечивает "контейнер" для $\frac{10\cdot(1+10)}{2}=55$ таких пар. В каком направлении двигаться, чтобы получить "недостаток" футболистов для противоречия и решения задачи, или есть другой способ решения?

Большое спасибо!

[pcyanide]

Вот другая идея.

AAA - подмножетсво игроков, которые все матчи сыграли в команде A, AAB - подмножество игроков, которые первые два матча сыграли в команде A, а последний в команде B и т.п. Таким образом вся совокупность подмножеств игроков разделяется на следующие пары: (AAA-BBB), (AAB-BBA), (ABA-BAB), (ABB-BAA), каждая из которых соответствует игрокам ни разу не сыгравшим вместе. Надо показать, что хотя бы одна из них содержит два непустых множества. Попробуем от противного. Заметим, что $AAA\bigcup AAB \bigcup ABA \bigcup ABB$ составляет множество всех игравших за А в первом матче, поэтому одно из них непустое. Аналогично одно из $BBB, BBA, BAB, BAA$ непусто. Таким образом либо два левых и два правых пусты, либо с одной стороны три пустых.

(У нас пол-первого ночи. Отосплюсь и надеюсь продолжу.).

[Gagarin1968]

Marucmp
Какая-то кривая формулировка задачи:

Marucmp в сообщении #1255647 писал(а):

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

Вообще-то достаточно одного матча.для того, чтобы нашлись такие два футболиста, которые ни одной игры не сыграли вместе.
Мне думается, что правильная формулировка звучала бы так: "Доказать, что трех футбольных матчей между двумя командами одного клуба недостаточно для того, чтобы каждый из $22$ игроков клуба сыграл бы вместе с каждым.

[pcyanide]

pcyanide в сообщении #1271950 писал(а):

Вот другая идея.

AAA - подмножетсво игроков, которые все матчи сыграли в команде A, AAB - подмножество игроков, которые первые два матча сыграли в команде A, а последний в команде B и т.п. Таким образом вся совокупность подмножеств игроков разделяется на следующие пары: (AAA-BBB), (AAB-BBA), (ABA-BAB), (ABB-BAA), каждая из которых соответствует игрокам ни разу не сыгравшим вместе. Надо показать, что хотя бы одна из них содержит два непустых множества. Попробуем от противного. Заметим, что $AAA\bigcup AAB \bigcup ABA \bigcup ABB$ составляет множество всех игравших за А в первом матче, поэтому одно из них непустое. Аналогично одно из $BBB, BBA, BAB, BAA$ непусто. Таким образом либо два левых и два правых пусты, либо с одной стороны три пустых.

Никак не спится, поэтому продолжаю.

1. Пусть где-то есть три пустых, например слева (т.е. из тех, кто сыграл первый матч за A). Можно считать, что AAA - единственное непустое из левых, так как в противном случае команды в 2м и 3м матчах можно переименовать. Получается, что все кто начинали за А не меняли команды (и полностью ее заполняли), поэтому игроки B обязаны были оставаться в своей команде, поэтому ни одна пара из A и B никогда не играла вместе.

2. Пусть два пустых слева и два пустых справа. Можно считать, что первое непустое это AAA, а второе непустое это AAB, ABA или ABB.

2a. AAA и ААB не пусты, АВВ и АВА пусты. Это значит, что во втором матче игроки А оставались в своей команде, и так же должны были поступать игроки из В. Поэтому ВВА или ВВВ не пусто. В первом случае пара (ААВ-ВВА) не пустая, во втором (ААА, ВВВ) не пустая.

2б ААА и АВА не пусты, АВВ и ААВ пусты. Поменяв местами 2-й и 3-й матчи, приходим к 2а

2в ААА и АВВ не пусты, ААВ и АВА пусты. Если ВАА или ВВВ не пусто, то пара (АВВ-ВАА) или (ААА-ВВВ) искомая. Таким образом все игроки, первоначально игравшие за В должны быть в BAB или BBA. В первом матче команда А формировалась из ААА и АВВ Пусть в ААА $n$ игроков, тогда в ABB $11-n$ игроков. Во втором матче команда A формировалась из AAA и ВАВ, следовательно в ВАА $11-n$ игроков, аналогично в BBA $n$ игроков. В третьем матче команда А формировалась из ААА и ВВА, в каждой из которых n игроков, таким образом $2n=11$, что невозможно!

Finita la comédia и можно поспать без проблем.

[pcyanide]

Gagarin1968 в сообщении #1271971 писал(а):

Вообще-то достаточно одного матча.для того, чтобы нашлись такие два футболиста, которые ни одной игры не сыграли вместе.

Действительно, утверждение верно в случае двух матчей, причем количество игроков в команде даже не существенно. Рассуждаем так: если АА и АВ оба непусты, то поскольку из ВА и ВВ одно непустое, получаем либо АА-ВВ либо АВ-ВА. Если одно из АА, АВ — пустое, то пусть непустое будет АА (иначе во втором команды переименуем). Тогда все из В останутся в В и будут в обоих матчах против А.

Однако это не распространяется на 3 матча, так как после третьего матча те, кто в обоих матчах играли в разных командах могут оказаться в одной. Я бы только убрал в условии задачи слово «достаточно».

Интересно, а верно ли утверждение для любого количества матчей? Вряд ли.

PS Выше описка (возможно не единственная). Не в ВАА, а в ВАВ $11-n$ игроков. Впрочем, sapienti sat est.

[llpu3pak]

Дано: 22 игрока, разделенные на две команды. Они играют три игры разными составами.
Задача состоит в том, чтобы доказать, что есть по крайней мере одна пара игроков, которые ни в одном из матчей не играли в одной команде.
Условие задачи можно сформулировать немного иначе: необходимо доказать, что есть по крайней мере один игрок, который не играл со всеми другими 21 игроками. Наличие пары, на мой взгляд, очевидно.

Рассмотрим более простую игру 3х3 и докажем, что даже в ней за 3 матча найдется пара игроков, которые все 3 матча играли против друг друга.
Обозначим игроков как $A_1,A_2,A_3,B_1,B_2,B_3$. Они сыграли первый матч составами A против B. У каждого из игроков осталось по 3 человека, с которыми он не играл в одной команде. Если во втором матче они все поменяются местами или останутся в прежнем составе, то ничего не изменится и они будут играть A против B. Смена одной пары игроков равносильна смене двух пар. В обоих случаях получим, что в одной команде 2 A игрока и 1 B, соответственно в другой команде - 2 B и 1 A. Таким образом получается, что 4 из 6 игроков сыграли с 3 разными игроками (т.е. осталось 2), а еще 2 с 4. Рассмотрев третий матч, мы прийдем к выводу, что как минимум 4 игрока не сыграли со всеми другими.
Подобные рассуждения можно перенести на любое другое число игроков, и в случае игры 11х11 получить результат, что как минимум 12 человек не сыграли со всеми другими игроками.

pcyanide в сообщении #1272077 писал(а):

Интересно, а верно ли утверждение для любого количества матчей? Вряд ли.

Нет. Для игр c нечетным числом игроков в командах возможна схема из 5 матчей, при которой они все могут друг с другом поиграть в одной команде. Что интересно, если бы в командах было четное число игроков, то можно уложиться и в 3 матча.