USAMO $1989$, Проблема $2$

Aug 17 2020

Проблема $2$ из USAMO, $1989$: The $20$ члены местного теннисного клуба расписали точно $14$игры для двух человек между собой, при этом каждый участник играет хотя бы в одной игре. Докажите, что в этом расписании должен быть набор из шести игр с$12$ отдельные игроки.

Моя попытка решения: поскольку есть$20$ игроков, каждый из которых сыграл хотя бы одну игру, наименьшее количество матчей, которые должны быть организованы таким образом, чтобы вместить всех игроков, будет $10$. В настоящее время,$4$осталось больше матчей, в которых может сыграть не более $8$ из этих $20$игроков. Таким образом, по крайней мере $12$ игроков могут играть не более $1$совпадение, и, следовательно, должен существовать набор из шести игр с$12$отдельные игроки . Я считаю, что это будет руководящим принципом строгого доказательства.

Меня омрачают следующие сомнения:

  1. Правильно ли мои рассуждения, т. Е. Свободны ли они от подводных камней?
  2. Если верно, то как сформулировать вышеприведенные рассуждения в виде математически строгого доказательства?

Изменить: как указал Бен в комментариях, заявление, выделенное курсивом, необоснованно. Кажется, я упустил из виду множество возможностей, создавая это доказательство. Таким образом, я хотел бы получить несколько подсказок, чтобы приступить к более разумным доказательствам.

Ответы

2 cgss Aug 17 2020 at 12:31

Боюсь, здесь есть ловушка. Если вы попытаетесь доказать, что есть 6 игр с 12 разными игроками среди тех, кто сыграл ровно одну игру, вы потерпите неудачу. Вот пример:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

Хотя существует 6 игр с 12 отдельными игроками, только 5 игр проводятся между игроками с ровно одной игрой.

Итак, вот подсказка: разделите игроков на две группы: тех, у кого одна игра, и тех, у кого больше. Затем объедините игроков в одну игру, после объедините игроков в одну игру с игроками с большим количеством игр и, наконец, с игроками с большим количеством игр.

РЕДАКТИРОВАТЬ : второй подход

Если каждый человек рассматривается как вершина, а каждая игра - как ребро, вопрос состоит в том, чтобы доказать, что существует соответствие размера не менее $6$. Точно так же мы можем доказать, что размер максимального соответствия$MM$ имеет размер не менее $6$. Обратите внимание, что максимальное совпадение разбивает вершины на два набора, один с ребрами в$MM$, размером $2\cdot |MM|$и один без размера $20 - 2\cdot |MM|$для нашей проблемы. Поскольку все вершины имеют степень не менее$1$, заключаем, что существует не менее $20 - 2\cdot |MM|$края между двумя перегородками. В настоящее время,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$