1
$\begingroup$

Recently I encountered the following puzzle:

Consider a game for two players which can only result in a win of one of the players (no ties). Now $n$ players decided to play this game each with each; $n(n-1)/2$ games total, $n\geq 3$. For each won game a player gets $1$ primary point. After the tournament the score of each player is calculated as the sum of primary points of all the players he've beaten. Turned out that everyone have the same score. Is it possible that amount of primary points wasn't the same for everyone?

I brainstormed this one several times in the past month but haven't come up with anything useful. Hypothetically the answer is no, checked for $n\leq 6$.

$\endgroup$
3
$\begingroup$

This is not possible. As is commonly a good approach, let us suppose that the least number of primary points anyone gets is $m$ and the most is $M$. We have that someone who earned $m$ primary points can earn no more than $mM$ total points, which occurs if they beat only players with $M$ primary points. Conversely, someone who earned $M$ primary points can earn no less than $mM$ total points, which occurs if they beat only players with $m$ primary points.

Thus, to make the total points equal, we conclude that those who scored $M$ primary points only beat players who scored $m$ primary points and vice versa. Now, consider a player who scored $M$ points. We can easily see that if $n\geq 4$ then $M\geq 2$, so this player beat at least two others. Thus, there are at least two distinct players who scored $m$ points each. They played a game against each other. The winner of that game had $m$ points, and players with $m$ points only beat players with $M$ points, as previously established. Thus, the loser had $M$ points, so $m=M$ and thus all the players had equally many points.

$\endgroup$
3
  • $\begingroup$ Wow, that's amazing! It is not an easy puzzle, you know... How did you crack it so fast? $\endgroup$
    – Glinka
    Jul 24 '16 at 0:11
  • $\begingroup$ @Glinka It reminded me of a similar "king chicken" puzzle, which basically has the same setup as this one, but then asks, "Is there a player who, for every other player, either directly beat that player, or beat another person who beat the given player." It turns out that the player who beats the most people also beats someone who beat anyone who beat him. So the trick of, "look for interesting behavior in maximal/minimal examples" occurred quickly to me, and the solution followed. $\endgroup$ Jul 24 '16 at 0:54
  • $\begingroup$ I see. Okey, thank you! $\endgroup$
    – Glinka
    Jul 24 '16 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.