Basic Math Challenge - September 2018

[PeroK]

Your conclusion is right and it's a very subtle and peculiar problem. At a glance, the solution looks complete -- I'll work through the details of your solution tomorrow I think.

I will tell you that I'm not that good at combinatiorial manipulations -- so there is in fact (at least one) much simpler way of getting at this solution.

Yes, I suspected you would have a simple solution up your sleeve.

 

[PeroK]

Your conclusion is right and it's a very subtle and peculiar problem. At a glance, the solution looks complete -- I'll work through the details of your solution tomorrow I think.

I will tell you that I'm not that good at combinatiorial manipulations -- so there is in fact (at least one) much simpler way of getting at this solution.

Spoiler

Every match under the normal rules, extended to the full $N-1$ games, has the form that Larry serves $N$ times, with $l$ holds, and Moe serves $N-1$ times with $m$ holds. The constraint, if Larry wins, is that $l > m$.

Now, take a match under the special rules. If Larry wins, then the match is of the form $l, N-l, m, N-l$, where Larry has served $N$ times (never noticed this before!) and $l > m$. The trick is to extend this match to $N-1$ games by letting Moe serve all the remaining $l-m-1$ games. This creates a match of $2N -1$ games where Larry wins iff he wins under the special rules, but is equivalent to a match under the normal rules, where Moe serves $N-1$ times. It's just that the service games are not necessarily alternating.

 

[StoneTemplePython]

Spoiler

Every match under the normal rules, extended to the full $N-1$ games, has the form that Larry serves $N$ times, with $l$ holds, and Moe serves $N-1$ times with $m$ holds. The constraint, if Larry wins, is that $l > m$.

Now, take a match under the special rules. If Larry wins, then the match is of the form $l, N-l, m, N-l$, where Larry has served $N$ times (never noticed this before!) and $l > m$. The trick is to extend this match to $N-1$ games by letting Moe serve all the remaining $l-m-1$ games. This creates a match of $2N -1$ games where Larry wins iff he wins under the special rules, but is equivalent to a match under the normal rules, where Moe serves $N-1$ times. It's just that the service games are not necessarily alternating.

This is the core of it.

There are no ties, so let them play $2N-1$ games no matter what. (In general this is a nice way to think about problems related to this as we get a binomial/normal distribution of wins.)

Under the alternating serve setup it is immediate that player one has $N$ serves and player two has $N-1$ serves.

Under the winner serves (positive feedback loop) setup we can still enforce a rule for the dummy games that are played after someone has clenched the title, such that player one has $N$ serves and player two has $N-1$ serves. (Also note that if player $1$ clinches the tournament in x games, I can infer who served for how many games -- ditto for player 2 clinching in y games.) The selection of this rule is arbitrary but convenient-- and since it only impacts dummy games, it cannot change the probability distribution of who actually wins the tournament.

Yet the resolution to the problem is then exploiting the order matters logic for the positive feedback serving scheme vs the fact that when $2N-1$ games are played, order does not matter -- a player is a winner iff said person has at least $n$ wins, period.

It's a nice but strange insight -- run the argument forward where order matters in this positive feedback loop for serving and pad the tournament with some well structured dummy games at the end, but stepping back, order doesn't matter when $2N-1$ games are played. $p_1$ always has $N$ serves and $p_2$ always $N-1$ hence whether the serves are alternating or come in runs doesn't matter.

Finally, the ordering rule chosen for serving in the dummy games is arbitrary but cannot impact the distribution of tournaments winner hence the serving schemes that Moe may choose from, don't matter.

 

[PeroK]

This is the core of it.

There are no ties, so let them play $2N-1$ games no matter what. (In general this is a nice way to think about problems related to this as we get a binomial/normal distribution of wins.)

Under the alternating serve setup it is immediate that player one has $N$ serves and player two has $N-1$ serves.

Under the winner serves (positive feedback loop) setup we can still enforce a rule for the dummy games that are played after someone has clenched the title, such that player one has $N$ serves and player two has $N-1$ serves. (Also note that if player $1$ clinches the tournament in x games, I can infer who served for how many games -- ditto for player 2 clinching in y games.) The selection of this rule is arbitrary but convenient-- and since it only impacts dummy games, it cannot change the probability distribution of who actually wins the tournament.

Yet the resolution to the problem is then exploiting the order matters logic for the positive feedback serving scheme vs the fact that when $2N-1$ games are played, order does not matter -- a player is a winner iff said person has at least $n$ wins, period.

It's a nice but strange insight -- run the argument forward where order matters in this positive feedback loop for serving and pad the tournament with some well structured dummy games at the end, but stepping back, order doesn't matter when $2N-1$ games are played. $p_1$ always has $N$ serves and $p_2$ always $N-1$ hence whether the serves are alternating or come in runs doesn't matter.

Finally, the ordering rule chosen for serving in the dummy games is arbitrary but cannot impact the distribution of tournaments winner hence the serving schemes that Moe may choose from, don't matter.

The critical point, which I originally missed, is that Larry cannot win the match by serving more than $N$ times. If you had rules where, say, Larry could win 12-7, having served in 13 games, then there would be no way to extend the match to a 12-11 serving pattern. E.g. if they tossed a coin before each game to see who serves (*).

I was focusing on the number of service holds and service breaks and missed this key factor: that if Larry wins, he has, in fact, served in exactly 12 games. That then allows the extension of dummy games to a 12-11 serving pattern.

(*) To follow this line of thought: in this case you would have to stop the coin tossing when Larry had served 12 times, or Moe 11 times, and then, as appropriate, one or other would serve out the remaining games. And, in general, whatever the rules, if you stop under these conditions (whether the match is decided or not!) and move on to the second phase of one player serving out the remaining games, then all you have done is rearranged the order of the 12-11 serves.

The point about the puzzle is that stopping after Larry has served 12 times is not explicit, but is an implicit consequence of the rules. Incidentally, therefore, it is just another way to have Larry serve precisely 12 times (or Moe 11 times) before moving on to the second phase, which in this case happen to be dummy games.

This, then, is another case where seeing the specific rules in a wider context makes the whole solution rather trivial and obvious!