OBM2022 – Nível 1 – Problema 4

OBM2022 – Nível 1 – Problema 4

Em clima de Copa do Mundo de Futebol, apresentaremos uma possível solução para o problema 4 do nível 1 da OBM 2022.

Solução. Sabemos que há \(\frac{8\times7}{2}=28\) jogos nesse torneio. Além disso, veja que se somarmos o número de vitórias que cada time obteve, isso é igual à soma do número de derrotas que cada time obteve. Vamos expressar isso da seguinte forma: \( \sum v = \sum d \). Além disso, a soma do número de vitórias, com o número de derrotas com o número de empates de cada time é 7. Pois cada time perdeu, venceu ou empatou cada um dos sete jogos que participou. Portanto, \[ \sum v+\sum d + \sum e = 8\times 7 = 56. \]

(a) Se esse cenário fosse possível, então \(\sum v \ge 3+7\times4=31\). Consequentemente, \(\sum d \ge 31\). Com isso, \(\sum v+\sum d \ge 62\). Absurdo.

(b) Vamos considerar uma possível situação na qual um time tem 2 vitórias e todos os outros têm 3 vitórias ou mais vitórias. Neste caso, \(\sum v \ge 2+7\times3 \ge 23\). Como \( \sum v = \sum d \), então \( \sum e \le 56-46=10 \). Portanto, se essa situação for possível, há no máximo cinco empates. Mais ainda, o time (que chamaremos de X) que teve duas vitórias pode ter pontuação máxima igual a 6+5=11. Dentre os demais times com três vitórias, alguns deles empataram com X. Isso significa que eles fizeram pelo menos 3+3+3+1=10 pontos. Assim, se essa situação for possível, X deve ter exatamente 2 vitórias e exatamente 5 empates. No grupo de times diferentes de X, a situação é a seguinte:

Há cinco times com três vitórias, três derrotas e um empate cada um deles.

• Há dois times com três vitórias e quatro derrotas cada um deles.

Agora vamos mostrar que há um exemplo. Sejam A, B, C, D, E, F e G os demais times diferentes de X. Suponha que A ganha de B, C, D; Que B ganha de C, D, E; Que C ganha de D, E, F; D ganha de E, F, G; E ganha de F, G, A; F ganha de G, A, B; G ganha de A, B, C.
(c) Agora suponha que o time X com menos vitória só ganhou uma partida. Então, esse time pode chegar a no máximo 3+6=9 pontos. Isso também significa que nenhum time teve três vitórias. Assim, todos os outros tiveram exatamente duas vitórias. Assim, cada um dos outro sete times fez pelo menos 6 pontos. Isso significa que X teve pelo menos 4 empates, para ter pelo menos 7 pontos. Sejam A, B, C e D os times que empataram com X. Note que cada um desses times terá pelo menos 3+3+1=7 pontos. Assim, X deve ter pelo menos cinco empates. Seja E o quinto time que também empatou com X.

Agora vamos mostrar que há um exemplo. Sejam A, B, C, D, E, F e G os demais times diferentes de X. Suponha que A ganha de B, C, D; Que B ganha de C, D, E; Que C ganha de D, E, F; D ganha de E, F, G; E ganha de F, G, A; F ganha de G, A, B; G ganha de A, B, C. (c) Agora suponha que o time X com menos vitória só ganhou uma partida. Então, esse time pode chegar a no máximo 3+6=9 pontos. Isso também significa que nenhum time teve três vitórias. Assim, todos os outros tiveram exatamente duas vitórias. Assim, cada um dos outro sete times fez pelo menos 6 pontos. Isso significa que X teve pelo menos 4 empates, para ter pelo menos 7 pontos. Sejam A, B, C e D os times que empataram com X. Note que cada um desses times terá pelo menos 3+3+1=7 pontos. Assim, X deve ter pelo menos cinco empates. Seja E o quinto time que também empatou com X. Suponha que X venceu G. Observe que cada um dos times {A,B,C,D,E} tem duas vitórias e um empate (contra X). Portanto, cada um tem pelo menos 7 pontos. Se um desses times tiver um empate contra G (ou algum empate entre os times de {A,B,C,D,E}) fará pelo menos 8 pontos e com isso, X deverá ter empatado com um sexto time F. Caso contrário, todos os jogos entre os times {A,B,C,D,E,G} não terminaram em empate. Se isso acontecer, foram distribuídos \(3 \times \left(\frac{6 \times 5}{2}\right) = 45 \) pontos.

Assim, algum time deve ter feito pelo menos 8 pontos apenas no grupo {A,B,C,D,E,G}. Portanto, algum time diferente de X fez pelo menos 9 pontos. Absurdo! Portanto, X empatou com os times A,B,C,D,E,F e venceu de G. Neste caso, X tem exatamente 9 pontos. Agora considere apenas o sub-torneio formado entre os times {A,B,C,D,E,F,G}. Cada um tem duas vitórias. Assim, \( \sum v = \sum d = 14 \) . Nesse sub-torneio vale que \( \sum v+\sum d + \sum e = 7\times 6 = 42. \) Logo, \( \sum e = 42- 2\times14=14 \). Ou seja, foram 7 empates e 21-7=14 jogos que não terminaram em empates. Logo, foram distribuídos \(3\times14+2\times7=56\) pontos.

Por outro lado, cada time {A,B,C,D,E,F} pode obter no máximo 7 pontos nesse sub-torneio e G pode obter no máximo 8 pontos nesse sub-torneio, para não obter uma pontuação maior do que ou igual a de X no torneio completo. Mas isso significa que a soma da pontuação obtida por esses times nesse sub-torneio é no máximo \(6\times7+8=50\). Absurdo. Então é impossível que o time com maior pontuação tenha apenas uma vitória e os demais tenham duas ou mais vitórias.