Basic Math Challenge - September 2018

[QuantumQuest]

The hint in problem (1) uses that fff must be twice differentiable, so shouldn't this be added to the hypothesis?

No. The hints are just some steps of a proposed route, in order to give some help to the potential solver(s). In order for the problem to be what is intended to, its wording is the one originally given.

 

[StoneTemplePython]

In this problem, we want to find times for which the two hands' positions can be interpreted as being for two different times. These times I called t₁ and t₂. Let us call one of the hands h₁ and the other one h₂. At time t₁, h₁ is the hour hand and h₂ is the minute hand, and at time t₂, h₁ is the minute hand and h₂ is the hour hand.

belatedly I'll mention your original post was quite close -- the question asked for the result with 24 hours in a day but your answer didn't address this... I meant to say this much earlier but was on the road for a while at the beginning of the month and this slipped my mind.

 

[PeroK]

6. Two Tennis players have a match that consists of just one set. Larry will serve in the first game and the first player to get $12$ games wins the match (whether ahead by only $1$ game or $2+$ games - either way wins the match).
Larry, and Moe have chances of $0.75$ and $0.70$, respectively, of winning when they serve. Since Moe doesn't serve in the very first game, he gets to choose: should the servers alternate game by game or should the winner of a given game serve in the next game. What's the best choice for Moe?

Spoiler

I'll call the match where they serve alternately "normal" rules and the match where the winner of the previous game serves "special" rules.

First, an observation that under the special rules the better server is more likely to serve on a given game and so the overall probability of winning a given game must go up for him. In general, therefore, in terms of points/games won the special rules must favour the better server.

But, interestingly, it makes no difference to the likelihood of being first to a set number of games. So, the answer is that neither choice is better than the other for Moe.

Lets take $p$ as the probability Larry holds serve and $q$ the probability that Moe holds serve. And, imagine it's first to $N$ games.

First, I'll calculate the probability of Larry winning under normal rules. To do this, I'll extend the match to $2N - 1$ games, if necessary, so that Larry serves $N$ times and Moe $N-1$ times. The only criterion is that Larry holds serve more often than Moe. If Larry holds serve $l$ times and Moe $m$ times, then we have the probability that Larry wins the match:
$$P_a = \sum_{l=1}^N \binom{N}{l} p^l (1-p)^{N-l} \sum_{m=0}^{l-1} \binom{N-1}{m} q^m (1-q)^{N-1-m}$$
Note that for $l =N$ we have:
$$P_a (l = N) = p^N \sum_{m=0}^{N-1} \binom{N-1}{m} q^m (1-q)^{N-1-m} = p^N (q + 1-q)^{N-1} = p^N$$
Which gives us a slightly revised format for comparison with the second case.

Now, under the special rules (note that here I'll consider the match ending when a player gets to $N$ games) if Larry wins then he wins the last game and, therefore, both players must break serve an equal number of times. I.e. every time Larry loses serve, he must break back at some stage to win the match.

A typical Larry win then looks like $l, m, N-l$, where $N-l$ is the number of breaks of serve each. First we consider the case where $m=0$. Here we have $N-l$ pairs of games of the form $ML$ where $M$ is a Moe service break and $L$ is Larry immediately breaking back (as Moe never holds serve when $m =0$). In addition we have another $l$ service holds. The probability, therefore, of a match of the form $l, 0, N-l$ is:
$$P_b(m=0;l) = \binom{N}{l} p^l (1-p)^{N-l} (1-q)^{N-l}$$
Now, if Larry wins we have the constraint that $m < l$. And, for $m \ne 0$ we have $m$ Moe service holds that we can distribute along with any of the $N-l$ pairs of service breaks. E.g. if $N = 5$ and $l = 3$, then we have $2$ pairs of games $ML$ in a typical Larry win with $m = 0$. For $m=2$ we can place another two $M$'s along with any of these pairs to give a sequence $MML$ or $MMML$ etc.

The number of ways of distributing $m$ games into $N-l$ "buckets" is $\binom{N-l-1+m}{m}$.

Note that the case where Larry holds serve throughout is a degenerative case, where Moe never serves and has a probability of $p^N$.

This gives us the total probability of Larry winning under the special rules as:
$$P_b = p^N + \sum_{l=1}^{N-1} \binom{N}{l} p^l (1-p)^{N-l} \sum_{m=0}^{l-1} \binom{N-l-1+m}{m} q^m (1-q)^{N-l}$$
We can compare this with the revised formula above:
$$P_a = p^N + \sum_{l=1}^{N-1} \binom{N}{l} p^l (1-p)^{N-l} \sum_{m=0}^{l-1} \binom{N-1}{m} q^m (1-q)^{N-1-m}$$
To show these two are equal, we need the following binomial identity (for $l = 1 \dots N-1$):
$$\sum_{m=0}^{l-1} \binom{N-l-1+m}{m} q^m (1-q)^{N-l} = \sum_{m=0}^{l-1} \binom{N-1}{m} q^m (1-q)^{N-1-m}$$
I have a slightly tedious proof by induction of this, which I can post if required.

Otherwise, we can see that Moe's chances of winning the match are the same with each set of rules.

 

[PeroK]

Supplement for question 6:

Spoiler

We need the following binomial identity (for $l = 1 \dots N-1$):
$$\sum_{m=0}^{l-1} \binom{N-l-1+m}{m} q^m (1-q)^{N-l} = \sum_{m=0}^{l-1} \binom{N-1}{m} q^m (1-q)^{N-1-m}$$
To simplify this slightly, we let $n = N-1, k = l-1$ and take out a common factor of $(1-q)^{N-l}$, to give the required identity:
$$B(k) = \sum_{m=0}^{k} \binom{n-k+m-1}{m} q^m = \sum_{m=0}^{k} \binom{n}{m} q^m (1-q)^{k-m} = A(k)$$
We can see that $A(0) = B(0) = 1$ and $A(1) = B(1) = 1 + (n-1)q$

For the inductive step we have:
$$A(k+1) = \sum_{m=0}^{k+1} \binom{n}{m} q^m (1-q)^{k+1-m} = (1-q)A(k) + \binom{n}{k+1} q^{k+1}$$
And:
$$B(k+1) = \sum_{m=0}^{k+1} \binom{n-k-1+m-1}{m} q^m = 1 + \sum_{m=1}^{k} \binom{n-k-1+m-1}{m} q^m + \binom{n-1}{k+1} q^{k+1}$$
$$ = 1 + \sum_{m=1}^{k} \binom{n-k+m-1}{m}q^m - \sum_{m=1}^{k} \binom{n-k-1+m-1}{m-1} q^m + \binom{n-1}{k+1} q^{k+1}$$
$$ = B(k) - \sum_{m=0}^{k-1} \binom{n-k-1+m}{m} q^{m+1} + \binom{n-1}{k+1} q^{k+1}$$
$$ = B(k) - q\sum_{m=0}^{k} \binom{n-k-1+m}{m} q^{m} + \binom{n-1}{k}q^{k+1} + \binom{n-1}{k+1} q^{k+1}$$
$$\therefore B(k+1) = (1-q)B(k) + \binom{n}{k+1}q^{k+1}$$
Hence, assuming $A(k) = B(k)$, we have $A(k+1) = B(k+1)$. QED

 

[StoneTemplePython]

I'll call the match where they serve alternately "normal" rules and the match where the winner of the previous game serves "special" rules.

First, an observation that under the special rules the better server is more likely to serve on a given game and so the overall probability of winning a given game must go up for him. In general, therefore, in terms of points/games won the special rules must favour the better server.

But, interestingly, it makes no difference to the likelihood of being first to a set number of games. So, the answer is that neither choice is better than the other for Moe.

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.

 

[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!