USAMO $1989$, Problema $2$
Problema $2$ da USAMO, $1989$: O $20$ membros de um clube de tênis local agendaram exatamente $14$jogos de duas pessoas entre si, com cada membro jogando pelo menos um jogo. Prove que dentro desta programação deve haver um conjunto de seis jogos com$12$ jogadores distintos.
Minha tentativa de solução: uma vez que existem$20$ jogadores, cada um dos quais jogou pelo menos um jogo, o menor número de partidas que devem ser organizadas para acomodar todos os jogadores seria $10$. Agora,$4$mais partidas faltam, que podem ser jogadas por no máximo $8$ destes $20$jogadoras. Assim, pelo menos $12$ dos jogadores podem jogar não mais do que $1$partida e , portanto, deve haver um conjunto de seis jogos com$12$jogadores distintos . Este, creio, será o princípio orientador de uma prova rigorosa.
Tenho as seguintes dúvidas nublando minha mente:
- Meu raciocínio é consistente, ou seja, livre de armadilhas?
- Se correto, como enquadrar o raciocínio acima em uma prova matematicamente rigorosa?
Edit: Conforme apontado por Ben nos comentários, a declaração em itálico é injustificada. Eu negligenciei muitas possibilidades enquanto elaborava esta prova, ao que parece. Assim, gostaria de obter algumas dicas para prosseguir com uma prova mais razoável.
Respostas
Receio que haja uma armadilha. Se você tentar provar que existem 6 jogos com 12 jogadores distintos entre aqueles que jogaram exatamente 1 jogo, você irá falhar. Aqui está um exemplo:
$$ 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$$
Embora existam 6 jogos com 12 jogadores distintos, apenas 5 jogos estão entre os jogadores com exatamente um jogo.
Então aqui vai uma dica: divida os jogadores em dois grupos, aqueles com um jogo e aqueles com mais. Em seguida, emparelhe jogadores com um jogo, depois emparelhe jogadores com um jogo com jogadores com mais e, finalmente, jogadores com mais jogos.
EDIT : Segunda abordagem
Se cada pessoa é vista como um vértice e cada jogo como uma borda, a questão pede para provar que há uma correspondência de pelo menos tamanho $6$. De forma equivalente, podemos provar que o tamanho da correspondência$MM$ é de tamanho pelo menos $6$. Observe que um máximo de correspondência divide os vértices em dois conjuntos, um com arestas no$MM$, do tamanho $2\cdot |MM|$, e um sem, de tamanho $20 - 2\cdot |MM|$para o nosso problema. Uma vez que todos os vértices são de pelo menos grau$1$, concluímos que há pelo menos $20 - 2\cdot |MM|$bordas entre as duas partições. Agora,
$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$