USAMO $1989$, Problema $2$

Aug 17 2020

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:

  1. Meu raciocínio é consistente, ou seja, livre de armadilhas?
  2. 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

2 cgss Aug 17 2020 at 12:31

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$$