USAMO $1989$、問題 $2$
問題 $2$ USAMOから、 $1989$： $20$ 地元のテニスクラブのメンバーは正確にスケジュールしました $14$各メンバーが少なくとも1つのゲームでプレイする2人用ゲーム。このスケジュール内に6つのゲームのセットが必要であることを証明します$12$ 異なるプレーヤー。
解決策の私の試み：あるので$20$ それぞれが少なくとも1つのゲームをプレイしたプレーヤー、すべてのプレーヤーに対応するために編成する必要のある試合の最小数は次のようになります。 $10$。さて、$4$で再生することができます残っているより多くの試合、最大で $8$ これらの $20$プレイヤー。したがって、少なくとも $12$ プレイヤーの $1$一致するため、6つのゲームのセットが存在する必要があります$12$異なるプレーヤー。これは、厳密な証明の指針となると私は信じています。
私は私の心を曇らせている次の疑問を持っています：
- 私の推論は正しいですか、つまり、落とし穴はありませんか？
- 正しければ、数学的に厳密な証明で上記の推論をどのように組み立てるのですか？
編集：コメントでベンが指摘したように、イタリック体のステートメントは不当です。この証拠を組み立てている間、私は多くの可能性を見落としたようです。したがって、より合理的な証拠を進めるためのヒントを得たいと思います。
回答
落とし穴があるのではないかと思います。正確に1つのゲームをプレイした人の中に、12人の異なるプレーヤーがいる6つのゲームがあることを証明しようとすると、失敗します。次に例を示します。
$$ 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$$
12人の異なるプレーヤーがいる6つのゲームがありますが、ちょうど1つのゲームがあるプレーヤーの間には5つのゲームしかありません。
ヒントは次のとおりです。プレーヤーを2つのグループに分けます。1つのゲームを持つグループとそれ以上のグループです。次に、1つのゲームでプレーヤーをペアリングした後、より多くのプレーヤーでプレーヤーをペアリングし、最後にさらに多くのゲームでプレーヤーをペアリングします。
編集：2番目のアプローチ
すべての人が頂点として、すべてのゲームがエッジとして見られる場合、質問は少なくともサイズの一致があることを証明するように求めます $6$。同等に、最大マッチングのサイズが$MM$ 少なくともサイズは $6$。最大マッチングにより、頂点が2つのセットに分割され、1つはエッジが$MM$、サイズの $2\cdot |MM|$、およびサイズのないもの $20 - 2\cdot |MM|$私たちの問題のために。すべての頂点は少なくとも次数であるため$1$、少なくともあると結論付けます $20 - 2\cdot |MM|$2つのパーティション間のエッジ。さて、
$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$