Putting Santul through his paces

Santul completes two 20 mile training runs with different pace profiles:

1) A constant 9 minute mile pace (which is impressive both physically and for its consistency); and

2) His pace starts at 10 minutes per mile and then linearly decreases to 8 minutes per mile over the course of the race. So for instance, when Santul is halfway done with the race (in time, not distance), his pace is 9 minutes per mile.

The question is: which run did he complete faster and what were the two times?

Santul's 9 minute mile run will complete in $9 \,\text{min} \, / \, \text{mile}\, \cdot 20 \,\text{miles} = 180 \,\text{minutes}.$

Let's now look at the second run. Let $$p(t) = a + bt$$ be the linear function of Santul's pace at time $t$. From the initial data we know that $$p(0) = a = 10$$ and that if $T$ is that time that Santul finishes his second run, then $$p(T) = 10 + b T = 8.$$ So $a = 10$ and $b = -\frac{2}{T}.$

We can convert Santul's pace into distance by integrating as follows $d(s) = \int_0^t \,\frac{ds}{p(s)},$ so given the 20 mile course was finished in $T$, we have $$20 = \int_0^T \,\frac{ds}{10 - \frac{2t}{T}} = -\frac{T}{2} \ln (\frac{8}{10}).$$ Solving for $T$ we get $$T = \frac{40}{\ln 1.25} = 179.256804709...$$ which is just a shade under the constant pace time.

Von Neumann's fair coin simulator

For any $p \in (0,1)$, von Neumann showed that an unfair coin which shows heads with probability $p$ can be used to simulate a fair coin by flipping twice, ignoring/redrawing for HH or TT and associating HT with T and TH with H. The issue is that depending on the value of $p,$ one might need to ignore/redraw for HH and TT outcomes for a very large number of tries before getting either TH or HT and exiting.

For what values of $p \in (0,1)$ is it possible to simulate a fair coin in at most $N$ flips?

While the phrasing on the question is a bit vague, I will assume two main frameworks for what "possible" means:

1) For what values of $p \in (0,1)$ is the expected number of flips needed to exit less than or equal to $N$?; or

2) Given some value of $q \in (0,1),$ for what values of $p \in (0,1)$ does the probability that the simulation exists in less than or equal to $N$ exceed $q$?

Let $T$ be the number of flips of the van Neumann simulator needed to exit. The probability that the van Neumann simulator exits after in one flip is $\mathbb{P}\{T = 1\} = 2p(1-p).$ The probability for $k > 1$ that it exits in $k$ flips is $\mathbb{P}\{ T = k \} = 2p(1-p) \cdot (1 - 2p(1-p))^{k-1}.$ So the average is $$\begin{align*}\mathbb{E}[T] &= \sum_{k=1}^\infty k \mathbb{P} \{ T = k \} = \sum_{k=1}^\infty k 2p(1-p) (1 - 2p(1-p))^{k-1}\\ &= 2p(1-p) \frac{1}{(1 - (1-2p(1-p)))^2} = \frac{1}{2p(1-p)}.\end{align*}$$

So under framework 1, the question becomes solving for $p \in (0,1)$ such that $$\mathbb{E}_p [T] = \frac{1}{2p(1-p)} \leq N.$$ Thus the solution is $$p \in \left[\frac{1 - \sqrt{1-2/N}}{2}, \frac{1 + \sqrt{1 - 2/N}}{2} \right].$$

Under framework 2, the question becomes for some $q \in (0,1),$ solving for $p \in (0,1)$ such that $$\mathbb{P}_p \{ T \leq N \} = \sum_{k=1}^N 2p(1-p) (1 - 2p(1-p))^{k-1} = 1 - (1 - 2p(1-p))^N \geq q.$$ Since $2p(1-p) \in [0,0.5]$ for all $p \in (0,1),$ if $q > 1-2^{-N},$ then $\mathbb{P}_p \{T \leq N \} \lt q,$ for all $p \in (0,1).$ But for any $q \in [0, 1-2^{-N}],$ then $\mathbb{P}_p \{T \leq N \} \geq q$ for $$p \in \left[ \frac{1 - \sqrt{2 \sqrt[N]{1-q} - 1}}{2}, \frac{1 + \sqrt{ 2 \sqrt[N]{1-q} - 1}}{2} \right].$$

A Game of Hot Pumpkin, or How I Was Left Holding the Chinese Remainder

In a game of Hot Pumpkin with $61$ people, the players count off clockwise upward from $1$ to $N$, eliminating the $N$th player and then then beginning again with the player to the left of the most recently eliminated. The integer value of $N$ is mutually agreed upon prior to beginning the game.

I start and say $1$, with the first eliminated player sitting $18$ spots to my left. Then Ricky starts up the next round and the person $31$ spots to her left is eliminated next. Zach both begins and is eliminated in the third round.

Based on the first three eliminations, what is the smallest value of $N$?

This game sets up as an example of the Chinese remainder theorem, which states that the system of congruences involved in this game, namely $$\begin{align*} N & \equiv 19 \mod 61 \\ N & \equiv 32 \mod 60 \\ N & \equiv 1 \mod 59,\end{align*}$$ has a single unique solution in $\mathbb{Z}_{59 \cdot 60 \cdot 61} = \mathbb{Z}_{215940}.$

For any two congruences, $N \equiv a_1 \mod n_1$ and $N \equiv a_2 \mod n_2,$ with $\text{gcd}(n_1,n_2) = 1,$ we can use Euclidean algorithm to calculate the integer solution to $$m_1 n_1 + m_2 n_1 = 1$$ that is asserted by B\'{e}zout's identity. From here, we note that $$N = a_1 m_2 n_2 + a_2 m_1 n_1 \mod n_1 \cdot n_2$$ is a solution to both congruences.

So in particular, we see that $(m_1, m_2) = (1, -1)$ is a solution to $61m_1 + 60m_2 = 1$ and hence $$N = 19 \cdot (-1) \cdot 60 + 32 \cdot 1 \cdot 61 \mod 61 \cdot 60 = 812 \mod 3660$$ is a solution to the first two congruences of our game of Hot Pumpkin.

Continuing onward, we can use the extended Euclidean algorithm to find that the solution to $3660m_1 + 59m_2 = 1$ is $(m_1, m_2) = (-29, 1799).$ This gives the smallest possible solution to all three congruences as $$\begin{align*}N &= 812 \cdot 1799 \cdot 59 + 1 \cdot (-29) \cdot 3660 \mod 3660 \cdot 59\\ &= 86080352 \mod 215940 \equiv 136232.\end{align*}$$