Prove que todo participante de um torneio joga com cada um dos outros participantes exatamente uma vez. Após o torneio cada jogador faz uma lista ...

Para provar que todo participante de um torneio joga com cada um dos outros participantes exatamente uma vez, podemos usar o princípio da contagem. Suponha que o torneio tenha n participantes. Na primeira rodada, cada jogador joga contra n-1 jogadores. Na segunda rodada, cada jogador já jogou com um adversário, então ele joga com n-2 jogadores. Continuando assim, na última rodada, cada jogador joga com apenas um adversário. Portanto, cada jogador jogou exatamente n-1 partidas. Agora, para provar que existe um jogador cuja lista possui o nome de todos os outros jogadores, podemos usar o princípio da casa dos pombos. Suponha que nenhum jogador tenha uma lista com o nome de todos os outros jogadores. Então, cada jogador tem uma lista com no máximo n-1 nomes. Como há n jogadores, há no máximo n(n-1) nomes nas listas de todos os jogadores. Por outro lado, cada partida resulta em um nome na lista de um jogador. Como cada jogador joga exatamente n-1 partidas, há exatamente n(n-1) nomes nas listas de todos os jogadores. Portanto, se nenhum jogador tem uma lista com o nome de todos os outros jogadores, então há no máximo n-1 nomes em cada lista, o que é uma contradição. Portanto, existe um jogador cuja lista possui o nome de todos os outros jogadores.