In a volleyball tournament for the Euro-African cup, there were nine more teams from Europe than from Africa. Each pair of teams played exactly once and the Europeans teams won precisely nine times as many matches as the African teams, overall. What is the maximum number of matches that a single African team might have won?
Problem
Source: 2006 MOP Homework Red Comb.3
Tags: combinatorics
31.05.2021 06:55
Can someone check this solution: Let the number of teams from Africa be $n$, so the number of teams from Europe is $n+9$ meaning $2n+9$ teams were there overall. Therefore the total amount of games were ${2n+9 \choose 2}$. Thus the total amount of wins the African teams had in total is ${2n+9 \choose 2}/9$. To maximize a single African teams wins we give the rest of the African teams 0 wins and one team ${2n+9 \choose 2}/9$ wins.
31.05.2021 07:39
mathlete5451006 wrote: Can someone check this solution: Let the number of teams from Africa be $n$, so the number of teams from Europe is $n+9$ meaning $2n+9$ teams were there overall. Therefore the total amount of games were ${2n+9 \choose 2}$. Thus the total amount of wins the African teams had in total is ${2n+9 \choose 2}/9$. To maximize a single African teams wins we give the rest of the African teams 0 wins and one team ${2n+9 \choose 2}/9$ wins. It should be $\frac{\binom{2n+9}{2}}{10}$. Also this is only valid when $n < 6$ because: The maximum games won by a single African team is $(n+9) + (n-1)$ because it can only win $n+9$ games max with other European teams and $n-1$ with other African teams. So $\frac{\binom{2n+9}{2}}{10} \leq n+9+n-1=2n+8 \implies 2n+9 \leq 20 \implies n \leq 5$
13.04.2023 23:04
huh why am i getting something different from everyone else above We claim that the answer is 11. Let $n$ be the number of African teams. Let $k$ be the number of games in which a European team defeated an African team. Then, the condition states that $${n+9\choose 2}+k=9({n\choose 2}+(n(n+9)-k)).$$After expanding everything, this becomes $$13n^2+68n=10k+36.$$Clearly, $k\leq n(n+9),$ so $$10k+36\leq 10n^2+90n+36.$$Thus, $$13n^2+68n\leq 10n^2+90n+36.$$This implies that $n\leq 8$ since $n$ is an integer. Note that $$k=\frac{13n^2+68n-36}{10}.$$Testing $n$ from 1 to 8 gives that only $n=6$ and $n=8$ give integer $k$, which give $k=84$ and $k=134$ respectively. If $n=6$ and $k=84$, there are 6 African teams and 15 European teams, and there are 6 games in which an African team beat a European team. To maximize the number of wins of one African team, have all 6 of these wins be attributed to the same African team. Since they have can have up to 5 more wins (from other African teams), the maximum possible is 11. In the other case of $n=8$ and $k=134$, the maximum is $7+2=9$, which is not as high. Thus, the answer is 11, achieved when: -There are 15 European teams and 6 African teams. -One of the African teams wins against all 5 other African teams. -That same African team beats 6 out of the 15 European teams. All other games between African and European teams results in a win for the European team. This clearly works since ${15\choose 2}+84=189=9({6\choose 2}+6)$ so we are done