I got stuck at solving one problem in combinatorics recently. It goes as following:
Masters and grandmasters play in chess tournament, such that total number of players is $N$. Prove that $N$ is a perfect square if every plater won exactly half of their games against masters. (Every player faced every other player).
My reasoning goes like this:
Let $P$ be number of grandmasters.
Let $Q$ be number of masters.
The total number of wins masters got against masters is equal to the number of pairs of masters that faced each other – $Q\choose 2$
The total number of wins grandmasters got against masters is equal to the total number of their wins – the total number of their wins against grandmasters. This is $K – {P\choose2}$, but I got stuck at figuring out K. I've tried doing $P * (N – 1)$, but that obviously fails, as that includes wins of masters over grandmasters.
How would you approach calculating $K$, or suggesting another approach to the problem?
UPDATE: Fixed the type in question (Q and P are now assigned proprely)
Best Answer
Since half of anyone's wins have been in front of a master, the total number of master's losses is half of all games played so there have totally been $\frac{\binom{N}{2}}{2}$ master's losses. On the other hand exactly half of master's wins have been in front of another master so there have totally been $2\times\binom{M}{2}$ master wins. Hence total number of games that all masters have participated in is :$$\frac{N(N-1)}{4}+M(M-1)=M(N-1)$$ $$\iff N^2-N+4M^2-4M=4MN-4M$$ $$\iff (2M-N)^2=4M^2-4MN+N^2=N$$ So $N$ is a perfect square and we're done.