Return to Answer

Added a more rigorous treatment of part 1.

Source Link

edited Mar 3, 2015 at 12:28

3.1k
1
17
17

This will be a little bit handwavy, but here goesEdited 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 4950, ie just less than 50% of the games can be nonsensical.

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

If more thanSuppose at least 50% of the games are nonsensical, then we. We can partition the points table somewhere such that contestantsinto 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 a lower averagethe same score than contestantsand 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 that'sthe 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. You can't
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 consistent points table where higher contestants are statistically likely to lose to lower contestantscontradiction 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:

This will be a little bit handwavy, but here goes.

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

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

If more than 50% of the games are nonsensical, then we can partition the points table somewhere such that contestants in the top part have a lower average score than contestants in the bottom part, and that's a contradiction. You can't have a consistent points table where higher contestants are statistically likely to lose to lower contestants.

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

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:

Source Link

created Mar 2, 2015 at 13:16

Callidus

3.1k
1
17
17

This will be a little bit handwavy, but here goes.

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

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

If more than 50% of the games are nonsensical, then we can partition the points table somewhere such that contestants in the top part have a lower average score than contestants in the bottom part, and that's a contradiction. You can't have a consistent points table where higher contestants are statistically likely to lose to lower contestants.

Next we must show Halfbrain's second theorem for x.
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.