10
$\begingroup$

Professor Halfbrain has spent his entire weekend watching the games at the local chess tournament. As usual, every two players played exactly one game against each other. A win yields 1 point, a draw yields half a point, and a loss yields nothing. At the end of the tournament, Professor Halfbrain carefully analyzed all the games and compared them to the final tournament ranking of the players.

To his excitement, Halfbrain realized that there were games in the tournament in which the winner had reached fewer points (in the final ranking) than the loser (in the final ranking). Professor Halfbrain decided to call such games nonsensical, and to call all other games (including all the ones that ended in a draw) sensical games. The professor managed to prove the following two deep theorems on sensical and nonsensical games.

Professor Halfbrain's first theorem: In every chess tournament, at least $0$ percent of the played games are sensical.

Professor Halfbrain's second theorem: There exist chess tournaments, in which at most $100$ percent of the games are sensical.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that the "$0$ percent" in the first theorem may be replaced by "$x$ percent", and so that the "$100$ percent" in the second theorem may be replaced by "$x+1$ percent" (again yielding true statements, of course).

$\endgroup$
  • $\begingroup$ Should the statements be true for any number of players in the tournament? $\endgroup$ – ghosts_in_the_code Mar 1 '15 at 16:08
  • 1
    $\begingroup$ @ghosts_in_the_code: The first theorem should be true for EVERY chess tournament, with ANY number of players. The second theorem only needs to be true for SOME (well-chosen) chess tournament. $\endgroup$ – Gamow Mar 1 '15 at 16:13
  • $\begingroup$ @BlueRaja That's the joke. Prof. Halfbrain hasn't proven anything meaningful. $\endgroup$ – Kevin Mar 1 '15 at 19:44
  • $\begingroup$ I find the $x$ vs $x+1$ format you use for these puzzles confusing. It takes me time to perform the replacement and process the statements, which I have to hold in my head. Why not just say "What is the least/greatest (integer) value of $x$ such that [property]?" $\endgroup$ – xnor Mar 3 '15 at 3:13
4
$\begingroup$

Edited to make the first part more rigorous (and correct the value of x thanks to @mdc32).
This will be a little bit handwavy, but here goes.

x is 50, ie just less than 50% of the games can be nonsensical.

First we must show Halfbrain's first theorem for x.

Suppose at least 50% of the games are nonsensical. We can partition the points table into an upper and lower part, with m players in the top part and n in the bottom part, and no overlap in scores between the parts. Otherwise all players must have the same score and there are no nonsensical games.
There are $m(m-1)/2$ intra-group games in the top part, and $n(n-1)/2$ in the bottom part. There are $mn$ intergroup games. Suppose at least $mn/2$ of them are nonsensical. Then the average score for the top part is at most $(m-1)/2 + n/2$, and the average score for the bottom part is at least $(n-1)/2 + m/2$. That means the bottom part has an average score at least as good as the top part. So some players from the bottom part must have scores at least as good as the top part, which is a contradiction.
If 50% of the games are nonsensical, and the intergroup games cannot be 50% nonsensical, then the intragroup games must be at least 50% nonsensical for at least one of the parts. We take that part, and recursively repeat the division process. Eventually we must reach a group containing 2 or 3 players, which cannot have any nonsensical games but must have at least 50% nonsensical games. So that's a contradiction as well.
We conclude that the number of nonsensical games must be less than 50%.

Next we must show Halfbrain's second theorem for x + 1.
Step 1:

Consider a tournament with a very large number of contestants, all evenly matched. Each wins half their games and loses the other half, so all are on the same score. A late entrant turns up and plays every contestant, winning half and losing half. Now those that won that last game have one more win than those that did not; but each "winner" lost half his games played against someone in the "loser" group. Of all the games, one quarter are played between "winners", one quarter are played between "losers", and half are played between "winners" and "losers". Half of that half will be won by the player from the "loser" group, that is, a quarter will be nonsensical games.

Step 2:

We can repeat this by adding another two late contestants. The first one gets the same results as the original late contestant; the second splits both the "winner" and "loser" group in half again. Only half the games remain to be affected (one quarter in each group), and we can only turn a quarter of the affected games into nonsensical games; a total of one eighth.

Step n:

We will need $2^{n-1}$ late contestants; one will induce new splits in the existing groups, and the rest will maintain the existing splits. We will make a further $\frac{1}{2^{n+1}}$ of the games nonsensical

Desired target:

Repeat as often as you can maintain the group as "large", which will not be all that long. The total number of affected games will be 1/4 + 1/8 + 1/16 + .... which has a limit of 50% that you will never be able to reach. But you can exceed 49%, by which time you will have introduced 127 late contestants and you will have 128 groups.
Note that you don't really have to introduce new contestants, but it makes it easier to picture what's going on.

$\endgroup$
  • 1
    $\begingroup$ Shouldn't $x$ be 50 then? i.e. At least 50 percent of the games in any given tournament are sensical, and there are tournaments where at most 51 percent are sensical. $\endgroup$ – mdc32 Mar 3 '15 at 3:56
  • $\begingroup$ @mdc32 You are correct - I had the sense of x reversed. I've edited it. $\endgroup$ – Callidus Mar 3 '15 at 12:29
  • $\begingroup$ The maths seems right but this is assuming ALL of the players are PATZERS, this is not the case in most tournaments, where is a rarity to find nonsensical games. I know it is to be a bit pedantic on my part $\endgroup$ – willy ontoria May 19 '17 at 0:11
2
$\begingroup$

I used a different approach than Callidus, but ended up at exactly the same target, and made exactly the same mistake.

To get the highest possible number of nonsensical games, the ideal situation would have every player with a different final ranking, with as little difference between each as possible (1/2 point) and a maximum of 1 tie per player. This can be done with any odd number of players greater than 3 (a 3 player tournament is guaranteed to have 100% sensical games, so it is ignored).

Given this situation, the middle-most player has a ranking of $\frac{1}{2}(n-1)$.
The best player has a ranking of $\frac{3}{4}(n-1)$.
The worst player has a ranking of $\frac{1}{4}(n-1)$.

You can then set up the wins and losses such that each player loses as many games as possible to players with worse rankings.

The total number of games played is $\frac{n(n-1)}{2}$.
The maximum number of nonsensical games is $\frac{(n-1)^2}{4}$.

This gives the percentage of nonsensical games as $\frac{n-1}{2n}$

$\lim\limits_{x\to\infty}\frac{n-1}{2n}=\frac{1}{2}$

So, for the first theorem, $x=50$. For the second theorem, I can find a tournament with $51$ players where $x+1<51$.

Some interesting points:

$5$: $40\%$ non-sensical games
$25$: $48\%$ non-sensical games.
$51$: Over $49\%$ non-sensical games.
$501$: Over $49.9\%$ non-sensical games.
$5001$: Over $49.99\%$ non-sensical games.
$50001$: Over $49.999\%$ non-sensical games.
...

$\endgroup$

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.