4
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ When I first read the question, I thought that for each player X, half of X's games against masters were wins for X. But that doesn't seem to work since some players played an odd number of games against masters. So I guess that of each player's total games, half were wins against masters. (E.g., each player played 10 games in the tournament and of those 10 games, 5 were W's agains masters.) Is that right, or am I still missing the correct interpretation? $\endgroup$
    – paw88789
    Mar 30, 2021 at 9:55
  • $\begingroup$ EDIT: My bad. The question states that player wins half of their points against masters (indicating half of their wins, not the total games). $\endgroup$
    – Donkey Xot
    Mar 30, 2021 at 10:08

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Let M and G be the number of Masters and grandmasters, respectively.

Number of plays between masters only - $\binom M2$
Number of plays between grandmasters only - $\binom G2$
Number of plays between a grandmaster and a master - MG

Now, for any master, for every win against a master, it must have another against a non-master(grandmaster). Similarly, for any grandmaster, any win against a grandmaster must have another against a master.

Hence, $$ MG = \binom M2 + \binom G2 $$ $$2*MG = M(M-1) + G(G-1)$$ $$ M + G = M^2 + G^2 - 2MG$$ $$ M + G = (M-G)^2 $$ where M+G equals the total number of players.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .