Sure, a bullseye is a bullseye, but what's the average?

Suppose each point on the dartboard is equally likely to be hit by a dart. On average, what score would you expect a single dart to earn?

Let $E = \mathbb{E} [ S ]$ be the average score of a single dart. Based on the setup of the Apollonian gasket, we see that there are infinitely many circles which are only contained within the unit circle. Let's say that we enumerate the radii as $r_n, n \in \mathbb{N},$ say with $r_0 = 1$, $r_1 = r_2 = \frac{1}{2},$ etc. One important point is that the smaller circles entirely contained within the unit eventually mutually exclusively cover the entirety of the unit circle, so however we enumerate them we must have $$\sum_{n=1}^\infty r_n^2 = 1.$$ Additionally, we see that the Apollonian gasket is symmetric about the $x$-axis and about the $y$-axis, so as we are filling things up we can focus on say just enumerating all of the cicles in say the first quadrant and then using symmetrical arguments to fill in the rest.

Additionally, since each circle with radius, say $r_n,$ is then filled with a scaled copy of the Apollonian gasket we see that $$\mathbb{E} [ S \mid r_n ] = \pi + r_n^2 E,$$ since in addition to the scaled copy of the expectation the only other circle that adds to the score is the unit circle. From a law of total expectation, since $$\mathbb{P} [ r_k ] = \frac{\pi r_n^2}{\pi} = r_n^2,$$ we have $$E = \sum_{n=1}^\infty r_n^2 \left( \pi + r_n^2 E \right) = \pi + E \sum_{n=1}^\infty r_n^4,$$ or equivalently $$E = \frac{\pi}{1 - \sum_{n=1}^\infty r_n^4}.$$

Actually, with all of that setup out of the way, let's speak in terms of curvatures $k_n = \frac{1}{r_n}, n \in \mathbb{N},$ where $k_0 = -1$ (since it is encompassing all of the other circles of the gasket). From Descartes' theorem -- or from Soddy's The Kiss Precise, whichever format speaks to your soul best -- we see that if you have three mutually tangent circles, with curvatures $k_\ell$, $k_m,$ $k_n$ then you can find two circles which are mututally tangent to the other three with curvatures $k_\pm,$ satisfying the equation $$(k_\ell + k_m + k_n + k_\pm)^2 = 2 \left( k_\ell^2 + k_m^2 + k_n^2 + k_\pm^2 \right).$$ In particular, we have $$k_\pm = k_\ell + k_m + k_n \pm 2 \sqrt{ k_\ell k_m + k_\ell k_n + k_m k_n }.$$ In particular, if we start with smaller curvatures (bigger radii) and work our way smaller and smaller, we can focus on just the solution $k_+$ since $k_-$ will have already been enumerated. In this way we can enumerate the first $N=84$ largest circles, once symmetry is taken into account, which correspond to the $20$ smallest curvatures. Note that the next largest circle has a curvature of $m_N = \min_{n \geq N+1} k_n = 62.$

Now we see that $$\theta_N = \sum_{n=1}^N r_n^2 \approx 0.955398049382331\dots$$ and $$\phi_N = \sum_{n=1}^N r_n^4 \approx 0.153282259694304\dots.$$ We additionally have $$\sum_{n=N+1}^\infty r_n^4 \leq \left(\max_{n \geq N+1} r_n^2 \right) \left( \sum_{n=N+1}^\infty r_n^2 \right) = \frac{1 - \theta_N}{m_N^2} \approx 0.0000116030048433062\dots.$$ Therefore, we have $$ 1.181031 \pi \approx \frac{\pi}{1-\phi_N} \leq E \leq \frac{\pi}{1 - \phi_N - \frac{1-\theta_N}{m_N^2}} \approx 1.181047 \pi.$$ Therefore, despite the fact that I could do a lot more enumeration and even get some good infinite sequences going based on the recursion formulae above, we see that the expected value of the score of one dart is approximately $$ E \approx 1.1810 \pi \approx 3.7103\dots.$$

A bullseye is a bullseye is a bullseye

You are playing darts with your friend, Apollonius, who has brought his own dartboard. However, this dartboard is somewhat … different. Instead of being a circle divided into concentric rings and sectors, the dartboard is a unit circle (i.e., with radius 1) that’s divided via an Apollonian gasket. In particular, this gasket is defined by two horizontally adjacent, congruent circles with radius 1/2.

But that’s not all! Every circle on the dartboard, no matter how small, is also its own Apollonian sub-gasket. Like the larger circle, every gasket, sub-gasket, sub-sub-gasket, etc., are defined by two horizontally adjacent, congruent circles with radii that are half the radius of their outer circle.

Now, when you throw a dart at this board, your score is the sum of the areas of every circle for which the dart lies inside or on the circumference. (Remember, the entire board is a unit circle.) What is the most a single dart can score?

Well as long as you hit the board at all you score $\pi$, so that's good. We note that if our dart hits the circumference of some circle, say with radius $r$, then there must be at lest some other circle, and in fact due to the nested Apollonian gaskets, infinitely many other circles of which this point is on the circumference. In particular, by recursion, if the dart lands at the point $z_0 + r_0 e^{i\theta}$ for some center, $z_0$, such that $\|z_0\|_2 \lt 1,$ and radius $r_0 \lt 1$, then there are infinitely many more circles $z_k + r_k e^{i\theta},$ where $r_k \leq \frac{1}{2^k}r_0,$ since all of the subcircles in the gasket have radius less than half of their outer circle, for some center $z_k$ satisfying $\|z_k - z_0\|_2 \lt r_0.$ Let's assume that the dart lands at the point of intersection between a circle of radius $r_1$ and a circle of radius $r_2,$ and that the smallest circle in the nested Apollonian gaskets that contains both of these circles is the unit circle, then the total score is $$S(r_1,r_2) \leq \pi + \sum_{n=0}^\infty \frac{\pi r_1^2}{4^n} + \sum_{m=0}^\infty \frac{\pi r_2^2}{4^m} = \pi \left( 1 + \frac{4}{3} \left( r_1^2 + r_2^2 \right) \right).$$

If we take any radii $r_1$, $r_2$ that appear in the Apollonian subgasket, then we get $$ \max S(r_1,r_2) \leq \max_{r_1, r_2} \pi \left( 1 + \frac{4}{3} \left(r_1^2 + r_2^2\right) \right) = \frac{5\pi}{3},$$ since $r_1, r_2 \leq \frac{1}{2}.$ On the other hand, if we get a bullseye, which sits exactly at the origin, then this sits in the circles indexed with centers at $z_k = (\textsf{sgn}(k) \frac{1}{2^{|k|}}, 0 )$ and radii $r_k = \frac{1}{2^{|k|}},$ for all $k \in \mathbb{Z}.$ So the score at the origin is $$S_0 = \sum_{k \in \mathbb{Z}} \pi \frac{1}{4^{|k|}} = \pi + 2\pi \sum_{k=1}^\infty \frac{1}{4^k} = \pi + 2\pi \frac{\frac{1}{4}}{1 - \frac{1}{4}} = \frac{5\pi}{3}.$$ Therefore, the bound is sharp and we must have that the maximum possible score of the dart, which occurs at a bullseye, is $\frac{5\pi}{3} \approx 5.235987756\dots.$

Sure, but I think Hotter Ones would prefer you buy all 100

You’re prepping for a new show, “Hotter Ones,” which has spices ranked from 1 to 100. Let $N$ be the minimum number of spices needed to generate all the numbers from 1 to 100. For how many sets of $N$ spice numbers is it possible to generate all the numbers from 1 to 100 using each spice at most once?

Ok, well at this point, we definitely should not be playing around with searching $\binom{100}{N}$ for ever higher values of $N$ until we get to some subset that actually works. So instead, we will lean on the Lemma that we laid out in the Classic problem, along with an observation below.

The observation is that for each $n \in \mathbb{N},$ the set $B_n = \{1, 2, 4, \dots, 2^{n-1} \} \in \mathcal{B}$ and in particular $\sigma(B_n) = 2^n - 1.$ We have already seen for $n = 1, 2, 3, 4$ that $\{1\},$ $\{1,2\},$ $\{1,2,4\},$ and $\{1,2,4,8\} \in \mathcal{B}.$ To prove the general case, we see that based on our lemma, if $B_n \in \mathcal{B}$ for some $n \geq 1,$ then since $2^n = \sigma(B_n) + 1,$ so $B_n \cup \{ 2^n \} = B_{n+1} \in \mathcal{B}.$ Note that these sets essentially are equivalent to using binary notation, since any number from $1 to 2^n-1$ can be represented by up to an $n$-digit binary representation. One further observation is that in fact for each $n \geq 1$, $B_n \in \mathcal{B}$ is the optimizer of the problem $\varsigma_n = \max \{ \sigma(A) \mid A \in \mathcal{B}, |A| \leq n \} = 2^n - 1.$

Since $2^6 = 64 \lt 100 \lt 2^7 = 128$ we see that $N = 7$ in this case. Even knowing this information I still don't want to test all $\binom{100}{7} = 16,007,560,800$ possible unique 7-tuples to see which ones work. We have already applied our Classic Fiddler lemma up to size $|A|=4,$ so let's just keep churning the crank a few more times. We see that \begin{align*}\mathcal{B}_5 &= \Biggl\{ \{1,2,3,4,5\}, \{1,2,3,4,6\}, \{1,2,3,4,7\}, \{1,2,3,4,8\},\Biggr. \\ &\quad\quad \{1,2,3,4,9\}, \{1,2,3,4,10\}, \{1,2,3,4,11\},\\ &\quad\quad \{1,2,3,5,6\}, \{1,2,3,5,7\}, \{1,2,3,5,8\}, \{1,2,3,5,9\},\\ &\quad\quad \{1,2,3,5,10\}, \{1,2,3,5,11\}, \{1,2,3,5,12\}, \\ &\quad\quad \{1,2,3,6,7\}, \{1,2,3,6,8\}, \{1,2,3,6,9\}, \{1,2,3,6,10\},\\ &\quad\quad \{1,2,3,6,11\}, \{1,2,3,6,12\}, \{1,2,3,6,13\}, \\ &\quad\quad \{1,2,3,7,8\}, \{1,2,3,7,9\}, \{1,2,3,7,10\}, \{1,2,3,7,11\},\\ &\quad\quad \{1,2,3,7,12\}, \{1,2,3,7,13\}, \{1,2,3,7,14\}, \\ &\quad\quad \{1,2,4,5,6\}, \{1,2,4,5,7\}, \{1,2,4,5,8\}, \{1,2,4,5,9\},\\ &\quad\quad \{1,2,4,5,10\}, \{1,2,4,5,11\}, \{1,2,4,5,12\}, \{1,2,4,5,13\}, \\ &\quad\quad \{1,2,4,6,7\}, \{1,2,4,6,8\}, \{1,2,4,6,9\}, \{1,2,4,6,10\},\\ &\quad\quad \{1,2,4,6,11\}, \{1,2,4,6,12\}, \{1,2,4,6,13\}, \{1,2,4,6,14\}, \\ &\quad\quad \{1,2,4,7,8\}, \{1,2,4,7,9\}, \{1,2,4,7,10\}, \{1,2,4,7,11\},\\ &\quad\quad \{1,2,4,7,12\}, \{1,2,4,7,13\}, \{1,2,4,7,14\}, \{1,2,4,7,15\}, \\ &\quad\quad \{1,2,4,8,9\}, \{1,2,4,8,10\}, \{1,2,4,8,11\}, \{1,2,4,8,12\},\\ &\quad\quad \{1,2,4,8,13\}, \{1,2,4,8,14\}, \{1,2,4,8,15\}, \{1,2,4,8,16\} \Biggr\}\end{align*} Now from $|\mathcal{B}_4| = 8$ to $|\mathcal{B}_5| = 60,$ we a 650% growth, so doing this two more times might not be that interesting, or efficient. But let's use our Lemma to trim some of the branches.

We see that for any particular $A \in \mathcal{B}_5,$ the maximum possible value of any $A^\prime \supset A$ with $A^\prime \in \mathcal{B}_6$ is $\sigma(A^\prime) \leq 2\sigma(A) + 1.$ Similarly, for any $\tilde{A} \in \mathcal{B}_7$ with $\tilde{A} \supset A^\prime \supset A,$ we see that $$\sigma(\tilde{A}) \leq 2 \sigma(A^\prime) + 1 \leq 4 \sigma(A) + 3.$$ So since we are ultimately searching for $\mathcal{B}^*_7 = \{ A \in \mathcal{B}_7 \mid \sigma(A) \geq 100 \},$ we can focus on $$A \in \mathcal{B}^*_5 = \{ A \in \mathcal{B}_5 \mid \sigma(A) \geq 25 \},$$ since if $\sigma(A) \leq 24,$ then $\sigma(\tilde{A}) \leq 4 \sigma(A) + 3 \leq 99.$ From inspection, this therefore knocks us down to a much more reasonable set of twenty candidates to search \begin{align*}\mathcal{B}^*_5 &= \Biggl\{ \{1,2,3,6,13\}, \{1,2,3,7,12\}, \{1,2,3,7,13\}, \{1,2,3,7,14\}, \Biggr.\\ &\quad\quad \{1,2,4,5,13\}, \{1,2,4,6,12\}, \{1,2,4,6,13\}, \{1,2,4,6,14\}, \\ &\quad\quad \{1,2,4,7,11\}, \{1,2,4,7,12\}, \{1,2,4,7,13\}, \{1,2,4,7,14\}, \\ &\quad\quad \{1,2,4,7,15\}, \{1,2,7,8,10\}, \{1,2,4,8,11\}, \{1,2,4,8,12\}, \\ &\quad\quad \Biggl.\{1,2,4,8,13\}, \{1,2,4,8,14\}, \{1,2,4,8,15\}, \{1,2,4,8,16\} \Biggr\}\end{align*}

Here again, as we step from $\mathcal{B}^*_5$ to $\mathcal{B}^*_6$ we can focus only on those $A \in \mathcal{B}_6$ with $\sigma(A) \geq 50,$ but this time we can do it from the get go. So we arrive at the somewhat unwieldy 104 candidates to search in \begin{align*}\mathcal{B}_6^* &= \Biggl\{ \{1,2,3,6,13,25\}, \{1,2,3,6,13,26\}, \{1,2,3,7,12,25\}, \{1,2,3,7,12,26\}, \Biggr.\\ &\quad\quad \{1,2,3,7,13,24\}, \{1,2,3,7,13,25\}, \{1,2,3,7,13,26\}, \{1,2,3,7,13,27\}, \\ &\quad\quad \{1,2,3,7,14,23\}, \{1,2,3,7,14,24\}, \{1,2,3,7,14,25\}, \{1,2,3,7,14,26\}, \\ &\quad\quad \{1,2,3,7,14,27\}, \{1,2,3,7,14,28\}, \{1,2,4,5,13,25\}, \{1,2,4,5,13,26\}, \\ &\quad\quad \{1,2,4,6,12,25\}, \{1,2,4,6,12,26\}, \{1,2,4,6,13,24\}, \{1,2,4,6,13,25\}, \\ &\quad\quad \{1,2,4,6,13,26\}, \{1,2,4,6,13,27\}, \{1,2,4,6,14,23\}, \{1,2,4,6,14,24\}, \\ &\quad\quad \{1,2,4,6,14,25\}, \{1,2,4,6,14,26\}, \{1,2,4,6,14,27\}, \{1,2,4,6,14,28\}, \\ &\quad\quad \{1,2,4,7,11,25\}, \{1,2,4,7,11,26\}, \{1,2,4,7,12,24\}, \{1,2,4,7,12,25\}, \\ &\quad\quad \{1,2,4,7,12,26\}, \{1,2,4,7,12,27\}, \{1,2,4,7,13,23\}, \{1,2,4,7,13,24\}, \\ &\quad\quad \{1,2,4,7,13,25\}, \{1,2,4,7,13,26\}, \{1,2,4,7,13,27\}, \{1,2,4,7,13,28\}, \\ &\quad\quad \{1,2,4,7,14,22\}, \{1,2,4,7,14,23\}, \{1,2,4,7,14,24\}, \{1,2,4,7,14,25\}, \\ &\quad\quad \{1,2,4,7,14,26\}, \{1,2,4,7,14,27\}, \{1,2,4,7,14,28\}, \{1,2,4,7,14,29\}, \\ &\quad\quad \{1,2,4,8,10,25\}, \{1,2,4,8,10,26\}, \{1,2,4,8,11,24\}, \{1,2,4,8,11,25\}, \\ &\quad\quad \{1,2,4,8,11,26\}, \{1,2,4,8,11,27\}, \{1,2,4,8,12,23\}, \{1,2,4,8,12,24\}, \\ &\quad\quad \{1,2,4,8,12,25\}, \{1,2,4,8,12,26\}, \{1,2,4,8,12,27\}, \{1,2,4,8,12,28\}, \\ &\quad\quad \{1,2,4,8,13,22\}, \{1,2,4,8,13,23\}, \{1,2,4,8,13,24\}, \{1,2,4,8,13,25\}, \\ &\quad\quad \{1,2,4,8,13,26\}, \{1,2,4,8,13,27\}, \{1,2,4,8,13,28\}, \{1,2,4,8,13,29\}, \\ &\quad\quad \{1,2,4,8,14,21\}, \{1,2,4,8,14,22\}, \{1,2,4,8,14,23\}, \{1,2,4,8,14,24\}, \\ &\quad\quad \{1,2,4,8,14,25\}, \{1,2,4,8,14,26\}, \{1,2,4,8,14,27\}, \{1,2,4,8,14,28\}, \\ &\quad\quad \{1,2,4,8,14,29\}, \{1,2,4,8,14,30\}, \{1,2,4,8,15,20\}, \{1,2,4,8,15,21\}, \\ &\quad\quad \{1,2,4,8,15,22\}, \{1,2,4,8,15,23\}, \{1,2,4,8,15,24\}, \{1,2,4,8,15,25\}, \\ &\quad\quad \{1,2,4,8,15,26\}, \{1,2,4,8,15,27\}, \{1,2,4,8,15,28\}, \{1,2,4,8,15,29\}, \\ &\quad\quad \{1,2,4,8,15,30\}, \{1,2,4,8,15,31\}, \{1,2,4,8,16,19\}, \{1,2,4,8,16,20\}, \\ &\quad\quad \{1,2,4,8,16,21\}, \{1,2,4,8,16,22\}, \{1,2,4,8,16,23\}, \{1,2,4,8,16,24\}, \\ &\quad\quad \{1,2,4,8,16,25\}, \{1,2,4,8,16,26\}, \{1,2,4,8,16,27\}, \{1,2,4,8,16,28\}, \\ &\quad\quad \Biggl.\{1,2,4,8,16,29\}, \{1,2,4,8,16,30\}, \{1,2,4,8,16,31\}, \{1,2,4,8,16,32\} \Biggr\} \end{align*} Rather than exhaustively write out all of the elements of $\mathcal{B}_7^*,$ we only need to enumerate the number of elements in that set, which we can do by just knowing the various qualities of the elements of $\mathcal{B}_6^*.$

In particular, we see that if some $A \in \mathcal{B}^*_6$ then there are exactly $2\sigma(A)-98$ distinct elements $A^\prime \in \mathcal{B}^*_7$ with $A^\prime \supset A$, so since the histogram of $\sigma$ values in $\mathcal{B}^*_6$ is shown in the table below, we can directly calculate that there are a total of $1,014$ sets of $N=7$ spice numbers that can generate all the numbers from $1$ to $100$ using each spice at most once.

$\sigma(A)$	$2\sigma(A) -98$	count
50	2	20
51	4	20
52	6	14
53	8	14
54	10	10
55	12	10
56	14	6
57	16	6
58	18	4
59	20	4
60	22	2
61	24	2
62	26	1
63	28	1

Sure, but I think Hot Ones would prefer you buy all 10

You have been invited on as a guest and want to prepare for the show. However, you don’t feel like purchasing all 10 sauces in advance. Your plan is to purchase fewer sauces, and then to combine sauces together for any you are missing. For example, if you are missing sauce #7, then you can instead simultaneously consume sauces #3 and #4, since $3 + 4 = 7$. (I know the spiciness of the sauces isn’t linear, but for the purposes of this puzzle, let’s assume it is.)

After some pencil-and-paper scratch work, you realize you only need four spices. For example, here’s how you can generate all the values from 1 to 10 using the spices #1, #2, #3, and #4 at most once:

• $1=1$
• $2=2$
• $3=3$
• $4=4$
• $5=1+4$
• $6=2+4$
• $7=3+4$
• $8=1+3+4$
• $9=2+3+4$
• $10=1+2+3+4$

Including this particular set of four spices (i.e., #1 through #4), for how many sets of four spice numbers is it possible to generate all the numbers from 1 to 10 using each spice at most once?

The brute force way of doing this would be to check all $\binom{10}{4} = 210$ sets of four spice numbers with no repeats and check whether they are able to generate all the numbers from $1$ to $10$ while using each spice at most one. But that seems tiresome, so let's instead try to work on the general solution that we will use for the Extra Credit problem.

Let $[n] := \{ 1, 2, \dots, n \} \subset \mathbb{N}.$ For some subset $A \subseteq \mathbb{N},$ let's define the $$\Sigma(A) = \{ n \in \mathbb{N} \mid \exists ! i_1, \dots, i_k \in A, n = i_1 + \dots + i_k \},$$ whereas we will let $\sigma(A) = \sum_{a \in A} a$ and $M(A) = \max \{ a \in A \}.$ Let's define $$\mathcal{B} = \{ A \subseteq \mathbb{N} \mid [\sigma(A)] = \Sigma(A) \}.$$ For the Classic problem, we then want to find all $A \in \mathcal{B}$ with $|A| = 4$ and $\sigma(A) \geq 10.$

It will help to have one additional lemma of sorts: If $A \in \mathcal{B},$ then, for any $\ell \in \{ M(A)+1, \dots, \sigma(A) + 1 \},$ $A \cup \{\ell\} \in \mathcal{B}$ as well. To prove this point, since obviously $[\sigma(A)] = \Sigma(A) \subset \Sigma(A \cup \{\ell\}),$ we need to show that $$[\sigma(A) + \ell] \setminus [\sigma(A)] = \{\sigma(A)+1, \dots, \sigma(A)+\ell \} \subset \Sigma(A \cup \{\ell\}).$$ Let's take any $q \in [\sigma(A) + \ell] \setminus [\sigma(A)],$ then $q - \ell \lt \sigma(A),$ so $\exists ! i_1, i_2, \dots i_k \in A$ such that $i_1 + \dots + i_k = q - \ell,$ for some $k = 1, \dots, |A|.$ Furthermore, $\ell \gt M(A),$ so $i_j \ne q,$ for $j = 1, \dots, k,$ so $i_1, i_2, \dots, i_k,$ and $\ell$ are all unique elements of $A \cup \{\ell\}$ and sum to $q.$ Thus, $[\sigma(A) + \ell] \setminus [\sigma(A)] \subset \Sigma(A \cup \{\ell\}),$ therefore if $A \in \mathcal{B}$ then $A \cup \{\ell\} \in \mathcal{B}$ as well for $\ell \in \{M(A) + 1, \dots, \sigma(A) + 1 \}.$

Now let's start by indentifying all $A \in \mathcal{B}$ with $|A| = 4,$ well, er, ... I guess let's start a bit before that. Clearly, $\{1\} \in \mathcal{B}.$ From our lemma, we then see that $\{1,2\} \in \mathcal{B}.$ Using the lemma again gives the two members of $\mathcal{B}$ with cardinality of $3,$ that is $\{1,2,3\}$ and $\{1,2,4\}.$ Therefore, with one additional application of the lemma, we get \begin{align*}\mathcal{B}_4 = \{ A \in \mathcal{B} \mid |A| = 4 \} &= \Biggl\{ \{1,2,3,4\}, \{1,2,3,5\}, \{1,2,3,6\}, \{1,2,3,7\},\Biggr. \\ &\quad\quad\quad \Biggl. \{1,2,4,5\}, \{1,2,4,6\},\{1,2,4,7\}, \{1,2,4,8\}\Biggr\}.\end{align*} Since by inspection $\sigma(A) \geq 10$ for each $A \in \mathcal{B}_4,$ we conclude that there are 8 sets of four spice numbers where all the numbers from 1 to 10 can be generated using each spice at most once.

An N person class?! Now that's really deranged!

If there are $N$ students in the class, where $N$ is some large number, how likely is it that they form a single loop that includes the entire class, in terms of $N$?

In the classic problem, we actually went through the various types of assignments that could work, but even there we showed roughly enough to know that the number of single loop gift exchange assignments is $(N-1)!$. The somewhat trickier piece is for the total number of all acceptable gift exchange assignments. Here, if you were paying attention to the titles of these posts, you might have been alerted to the fact that an acceptable gift exchange assignment, that is a permutation where no number is assigned to itself, is called a derangement. The number of derangements of $N$ elements is sometimes called the sub-factorial, denoted $!N,$ which can be shown to have the formula $$!N = N!\sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Thus, we see that the probability of having a single loop for some large number $N$ students is $$\frac{(N-1)!}{N! \sum_{i=0}^N \frac{(-1)^i}{i!} } \approx \frac{e}{N}$$ as $N \to \infty,$ since $\sum_{i=0}^\infty \frac{(-1)^i}{i!} = e^{-1}.$

You know, it honestly takes a smidgeon of the fun out of knowing the solution, rather than doing much work for it. So, I dunno, maybe let's derive the formula $$!N = N! \sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Let $U$ be the set of all inappropriate gift exchange assignments, that is where someone receives themselves as the giftee. In particular, for each $k = 1, \dots, N,$ let $U_k$ be the set of assignments where $k$ receives herself as the giftee. Using the inclusion/exclusion principle, we have \begin{align*}|U| = |U_1 \cup U_2 \cup \dots \cup U_N| &= \sum_{i=1}^N |U_i| -\sum_{1 \leq i \lt j \leq N} |U_i \cap U_j| \\ &\quad\quad\quad+ \sum_{1 \leq i \lt j \lt k \leq N} |U_i \cap U_j \cap U_k | + \dots \\ &\quad\quad\quad\quad+ (-1)^{N+1} |U_1 \cap U_2 \cap \dots \cap U_N|.\end{align*} Now the $k$ summand in the above formula, e.g., $|U_{i_1} \cap U_{i_1} \cap \dots \cap U_{i_k}|$ counts all permutations where $i_1 \lt i_2 \lt \dots \lt i_k$ receive themselves as giftees leaving the other $N-k$ students free to explore all possible permutations. Therefore, we have $|U_{i_1} \cap \dots \cap U_{i_k}| = (N-k)!$, which is coupled with the fact that there are $\binom{N}{k}$ ways of choosing $i_1, \dots, i_k.$ So we have \begin{align*}|U| &= \binom{N}{1} (N-1)! - \binom{N}{2} (N-2)! + \dots + (-1)^{N+1} 0! \\ &= \sum_{i=1}^N (-1)^{i+1} \binom{N}{i} (N-i)! \\ &= N! \sum_{i=1}^N \frac{(-1)^{i+1}}{i!}.\end{align*} Since the number of total derangements would be the number of all permutations minus the non-derangements, we get $$!N = N! - |U| = N! \left(1 - \sum_{i=1}^N \frac{(-1)^{i+1}}{i!}\right) = N! \left( 1 + \sum_{i=1}^N \frac{(-1)^i}{i!} \right) = N! \sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Pretty neat, if not anticlimactic, I guess.

A five person class! That's deranged!

You are participating in a holiday gift exchange with your classmates. You each write down your own name on a slip of paper and fold it up. Then, all the students place their names into a single hat. Next, students pull a random name from the hat, one at a time. If at any point someone pulls their own name from the hat, the whole class starts over, with everyone returning the names to the hat.

Once the whole process is complete, each student purchases a gift for the classmate whose name they pulled. Gifts are handed out at a big holiday party at the end of the year. At this party, you observe that there are “loops” of gift-giving within the class. For example, student A might have gotten a gift for B, who got a gift for C, who got a gift for D, who got a gift for A. In this case, A, B, C and D would form a loop of length four. Another way to have a loop of length four is if student A got a gift for C, who got a gift for B, who got a gift for D, who got a gift for A. And of course, there are other ways.

If there are a total of five students in the class, how likely is it that they form a single loop that includes the entire class?

For this particular case, we can just go through all of the possible outcomes. Let's first enumerate all of the possible single loops for all five students. Let's use the permutation notation $(ABCDE)$ stand for the loop where $A \to B \to C \to D \to E \to A.$ It doesn't necessarily matter where on this loop you start, so let's always assume that we start with $A$. Then we are free to choose any ordering of $B,$ $C$, $D,$ and $E$ to form a loops, so there are $4! = 24$ such loops.

On the other hand, since we cannot ever have a one person loop, where a person receives themselves as the giftee, the only other acceptable assingments for our gift exchange is that there is a combination of a 2-loop and a 3-loop. Here we see that there are $\binom{5}{2} = 10$ ways of choosing the two students to be in the 2-loop. By analogy, we see that there are $2 = (3-1)!$ ways of arranging the remaining members of our 3-loop. So there are a total of $\binom{5}{2} 2! = 20$ other acceptable gift exchange assignments.

Therefore, the probability that all of the giftees form a single loop when there are $5$ students is $$\frac{24}{24+20} = \frac{6}{11} = 54.5454545454\dots\%.$$

Millions of Peaches, Peaches for Free, .... or at least for Extra Credit

As before, your assistant intends to pick two random points along the circumference of the garden and run a hose straight between them.

This time, you’ve decided to contribute to the madness yourself by picking a random point inside the garden to plant a second peach tree. On average, how far can you expect this point to be from the nearest part of the hose?

Here let's again assume that the assistant's hose starts at $(1,0)$ and ends at $(\cos \theta, \sin \theta)$ for some uniform random $\theta \sim U(0,2\pi).$ Here however, we assume that there is a peach tree at the random point $(u,v)$ for some uniformly random point with $$f(u,v) = \frac{1}{\pi}\chi ( u^2+v^2 \leq 1 ).$$ We can again use the line $y = x\tan \frac{\theta}{2},$ which is the perpendicular bisector of the chord traces by the hose, or more precisely we will use parallel copies of it. Let's subdivide the circular area into three different spaces: \begin{align*}\Omega_1(\theta) &= \left\{ (u,v) \mid u^2 + v^2 \leq 1, \left| v - u \tan \frac{\theta}{2} \right| \leq \tan \frac{\theta}{2} \right\} \\ \Omega_2(\theta) &= \left\{ (u,v) \mid u^2 + v^2 \leq 1, v - u\tan \frac{\theta}{2} \geq \tan \frac{\theta}{2} \right\} \\ \Omega_3(\theta) &= \left\{ (u,v) \mid u^2 + v^2 \leq 1, v - u \tan \frac{\theta}{2} \leq - \tan \frac{\theta}{2} \right\}.\end{align*}

In general we get \begin{align*}\lambda^*(u,v,\theta) & = \arg\max \left\{ \| ( 1 - \lambda + \lambda \cos \theta - u, \lambda \sin \theta - v ) \|_2 \mid 0 \leq \lambda \leq 1 \right\} \\ &= \arg \max \left\{ (1-u)^2 + v^2 - 2 \lambda ( (1-u)(1-\cos \theta) + v\sin \theta ) \right.\\&\quad\quad\quad\quad\quad\quad\quad\quad \left.+ 2(1-\cos \theta) \lambda^2 \mid 0 \leq \lambda \leq 1 \right\} \\ &= \begin{cases} \frac{1}{2} \left( 1 - u + v \cot \frac{\theta}{2} \right), & \text{ if $(u,v) \in \Omega_1(\theta)$; } \\ 0, &\text{ if $(u,v) \in \Omega_2(\theta)$;} \\ 1, &\text{if $(u,v) \in \Omega_3(\theta).$}\end{cases}\end{align*} Plugging this back in we see that we have $$d(u,v,\theta) = \begin{cases} \frac{ \left| (1-u) \sin \theta + v(1-\cos \theta) \right| }{ 2 \sin \frac{\theta}{2} }, &\text{if $(u,v) \in \Omega_1(\theta)$;} \\ \sqrt{ (u-1)^2 + v^2 }, &\text{if $(u,v) \in \Omega_2(\theta)$;} \\ \sqrt{ (u- \cos \theta)^2 + (v - \sin \theta)^2 }, &\text{ if $(u,v) \in \Omega_3(\theta).$}\end{cases}$$

Let's first attack $A(\theta) = \iint_{\Omega_1(\theta)} d(u,v,\theta) f(u,v) \,du\,dv.$ We see that, so long as $0 \leq \theta \leq \pi$, by rotating the plane counterclockwise about the origin by $\frac{\pi-\theta}{2}$ that the chord is now parallel to the $x$-axis and stretches from $(-\sin \frac{\theta}{2}, \cos \frac{\theta}{2})$ to $(\sin \frac{\theta}{2}, \cos \frac{\theta}{2}).$ In this case, it is clear to see that the distance $d(u^\prime, v^\prime, \theta) = |v^\prime - \cos \frac{\theta}{2}|.$ So the transformed integral is \begin{align*}A(\theta) &= \frac{2}{\pi} \int_0^{\sin \theta/2} \int_{-\sqrt{1-x^2}}^{\sqrt{1-x^2}} \left|y - \cos \frac{\theta}{2}\right| \,dy \,dx \\ &= \frac{2}{\pi} \int_0^{\sin \theta/2} \left( \int_{-\sqrt{1-x^2}}^{\cos \theta/2} \left(\cos \frac{\theta}{2} - y \right)\,dy + \int_{\cos \theta/2}^{\sqrt{1-x^2}} \left( y - \cos \frac{\theta}{2} \right) \,dy \right) \,dx \\ &= \frac{2}{\pi} \int_0^{\sin \theta/2} \left(1 + \cos^2 \frac{\theta}{2} - x^2\right) \,dx \\ &= \frac{2}{\pi} \sin \frac{\theta}{2} \left( 1 + \cos^2 \frac{\theta}{2} \right) - \frac{2}{3\pi} \sin^3 \frac{\theta}{2} \\ &= \frac{4}{3\pi} \sin \frac{\theta}{2} \left( 1 + 2 \cos^2 \frac{\theta}{2} \right).\end{align*}

We see from symmetry that $\iint_{\Omega_2(\theta)} d(u,v,\theta) f(u,v)\,du\,dv = \iint_{\Omega_3(\theta)} d(u,v,\theta) f(u,v) \,du\,dv,$ so let's let \begin{align*}B(\theta) = \frac{2}{\pi} \iint_{\Omega_2(\theta)} d(u,v,\theta)\,du\,dv &= \frac{2}{\pi} \int_{-\cos \theta}^1 \int_{-\sqrt{1-x^2}}^{\tan \frac{\theta}{2} (x - 1)} \sqrt{ (x-1)^2 + y^2 }\,dy\,dx \\& = \frac{2}{\pi} \int_{\pi + \theta/2}^{3\pi/2} \int_0^{-2\cos \phi} \rho^2 \,d\rho \,d\phi,\end{align*} where the final change of variables represents the transformation $(u,v)$ into $(1 + \rho \cos \phi, \rho \sin \phi)$ for $\phi \in ( \pi + \theta/2, 3\pi/2)$ and $0 \leq \rho \leq -2\cos \phi.$ Therefore, we see that $$B(\theta) = \frac{2}{\pi} \int_{\pi + \theta/2}^{3\pi/2} \left(-\frac{8}{3} \cos^3 \phi\right) \,d\phi = \frac{2}{\pi} \left(\frac{16}{9} - \frac{8}{3} \sin \frac{\theta}{2} + \frac{8}{9} \sin^3 \frac{\theta}{2}\right).$$

Putting these two together we see that the average distance from the random point $(u,v)$ to the chord from $(1,0)$ to $(\cos \theta, \sin \theta)$ is given by $d(\theta) = A(\theta) + B(\theta).$ Therefore, through symmetry, we see that the average distance is given by $$\hat{d} = \frac{1}{\pi} \int_0^\pi d(\theta) \,d\theta = \frac{1}{\pi} \int_0^\pi A(\theta) \,d\theta + \frac{1}{\pi} \int_0^\pi B(\theta)\, d\theta.$$ We have \begin{align*}\frac{1}{\pi} \int_0^\pi A(\theta) \,d\theta &= \frac{4}{3\pi^2} \int_0^\pi \sin \frac{\theta}{2} \left( 1 + 2 \cos^2 \frac{\theta}{2} \right)\,d\theta \\ &= \frac{8}{3\pi^2} \left.\left( -\cos \frac{\theta}{2} - \frac{2}{3} \cos^3 \frac{\theta}{2} \right)\right|_0^\pi = \frac{40}{9\pi^2}.\end{align*} Similarly, we have \begin{align*}\frac{1}{\pi} \int_0^\pi B(\theta) \,d\theta &= \frac{2}{\pi^2} \int_0^\pi \left(\frac{16}{9} - \frac{8}{3} \sin \frac{\theta}{2} + \frac{8}{9}\sin^3 \frac{\theta}{2} \right) \,d\theta \\ &= \frac{2}{\pi^2} \left.\left( \frac{16}{9} \theta + \frac{32}{9} \cos \frac{\theta}{2} + \frac{16}{27} \cos^3 \frac{\theta}{2} \right)\right|_0^\pi = \frac{96\pi - 224}{27\pi^2}.\end{align*} Combining these together gives the average distance between the randomly place hose and your randomly placed peach tree at a slightly larger $$\hat{d} = \frac{40}{9\pi^2} + \frac{96\pi - 224}{27\pi^2} = \frac{96\pi - 104}{27\pi^2} \approx 0.741494295364\dots$$ furlongs.

Peaches, peaches, peaches, peaches, peaches … I likely won’t water you

You and your assistant are planning to irrigate a vast circular garden, which has a radius of 1 furlong. However, your assistant is somewhat lackadaisical when it comes to gardening. Their plan is to pick two random points on the circumference of the garden and run a hose straight between them.

You’re concerned that different parts of your garden—especially your prized peach tree at the very center—will be too far from the hose to be properly irrigated.

On average, how far can you expect the center of the garden to be from the nearest part of the hose?

Without loss of generality, let's assume that we choose a coordinate system such that one end of the hose is located at the point $(1,0)$ and the other end is located at $(\cos \theta, \sin\theta)$ for some uniformly random $\theta \sim U(0,2\pi).$ The minimal distance from the origin, where the prized peach tree is, and the chord traced by the hose occurs along the ray that perpendicularly bisects the chord. We can arrive here either by calculus and finding $$\lambda^* = \arg\max \{ \| (1-\lambda + \lambda \cos \theta, \lambda \sin \theta ) \|_2 \mid 0\leq \lambda \leq 1 \} = \frac{1}{2}$$ or by spatial reasoning about Lagrange multipliers and optimizers occurring when contours and contraints are normal to one another or by any other means, I suppose. Whichever Feynman-esque path we take to arrive at the perpendicular bisector, we then see through some trigonometry that this minimal distance is this $$d(\theta) = \left| \cos \frac{\theta}{2}\right|,$$ as a function of the random $\theta.$

So, the average distance between the randomly placed hose and your precious peach tree is \begin{align*}\bar{d} &= \frac{1}{2\pi} \int_0^{2\pi} d(\theta) d\theta \\ &= \frac{1}{\pi} \int_0^\pi \cos \frac{\theta}{2} \,d\theta \\ &= \frac{2 \sin \frac{\pi}{2} - 2 \sin 0}{\pi} = \frac{2}{\pi}\approx 0.636519772\dots\end{align*} furlongs, which is about 420.3 feet. This doesn't seem too terribly bad, but given that the spread of an average peach tree is only about 20 feet (according to a quick Googling), your assistant's method is not expected to provide a large amount of water to your peaches.

Even more so, seems like an actual uniform generator would be simpler…

Randy has an updated suggestion for how the button should behave at door 2. What hasn’t changed is that if a contestant at door 2 and moves to an adjacent door, that new door will be 1 or 3 with equal probability.

But this time, on the first, third, fifth, and other odd button presses that happen to be at door 2, there’s a 20 percent the contestant remains at door 2. On the second, fourth, sixth, and other even button presses that happen to be at door 2, there’s a 50 percent chance the contest remains at door 2.

Meanwhile, the button’s behavior at doors 1 and 3 should in no way depend on the number of times the button has been pressed.

As the producer, you want the chances of winding up at each of the three doors—after a large even number of button presses— to be nearly equal. If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?

In this case, let $q$ be the probability of remaining at door 1 (or at door 3), then we can treat the two different behaviors at door 2 sequentially in order to come with the two-step transition matrix \begin{align*}Q & = \begin{pmatrix} q & 1-q & 0 \\ 0.4 & 0.2 & 0.4 \\ 0 & 1-q & q \end{pmatrix} \begin{pmatrix} q & 1-q & 0 \\ 0.25 & 0.5 & 0.25 \\ 0 & 1-q & q \end{pmatrix} \\ & = \begin{pmatrix} q^2 -\frac{1}{4}q +\frac{1}{4} & -q^2 + \frac{1}{2} q +\frac{1}{2} & -\frac{1}{4}q + \frac{1}{4}\\ \frac{2}{5}q + \frac{1}{20} & -\frac{4}{5}q + \frac{9}{10} & \frac{2}{5}q + \frac{1}{20}\\ -\frac{1}{4}q + \frac{1}{4} & -q^2 + \frac{1}{2} q + \frac{1}{2} & q^2 -\frac{1}{4}q + \frac{1}{4}\end{pmatrix}.\end{align*}

We will lean upon our own great (?) shoulders from the Classic problem to show that we need to solve for $q$ that makes the transition matrix symmetric. In this case, that requirement yields $$\frac{2}{5}q + \frac{1}{20} = -q^2 + \frac{1}{2} q + \frac{1}{2},$$ or equivalently, $$q^2 -\frac{1}{10} q - \frac{9}{20} = 0.$$ Solving this quadratic for the positive root (since after all we need $q\in[0,1]$ as a probability), gives that the appropriate probability to remain at door 1 in this even more complicated Markov scheme is $$q=\frac{ \frac{1}{10} + \sqrt{ \frac{1}{100} + 4 \frac{9}{20} } }{2} = \frac{1+\sqrt{181}}{20} \approx 0.722681202354\dots$$

Seems like an actual uniform generator would be simpler…

You are a producer on a game show hosted by Randy “Random” Hall (no relation to Monty Hall). The show has three doors labeled 1 through 3 from left to right, and behind them are various prizes.

Contestants pick one of the three doors at which to start, and then they press an electronic button many, many times in rapid succession. Each time they press the button, they either stay at their current door or move to an adjacent door. If they’re at door 2 and move to an adjacent door, that new door will be 1 or 3 with equal probability.

Randy has decided that when a contestant presses the button while at door 2, there should be a 20 percent chance they remain at door 2.

As the producer, you want the chances of a contestant ultimately winding up at each of the three doors to be nearly equal after many button presses. Otherwise, mathematicians will no doubt write you nasty letters complaining about how your show is rigged.

If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?

Firstly, so true ... if there were a meaningful bias in the supposedly uniformly random process of selecting which door, I would take notice. Though rather than calling to complain I would be more likely to try to get on the show to exploit this bias, but I guess potato-potato.

Moving on, per Randy's specifications and your desire for the appearance of uniform randomness, we have a three state Markov chain setup where the transition matrix $$P= \begin{pmatrix} p & 1-p & 0 \\ 0.4 & 0.2 & 0.4 \\ 0 & 1-p & p \end{pmatrix}$$ and we are wondering for which values of $p$ will $P^n \to U,$ as $n\to \infty$, where the limiting matrix $U$ is the $3\times 3$ matrix where each entry is $\frac{1}{3}.$

There are many ways to solve for $p$ here. For instance, though we would obviously start with some specific position, e.g., $\pi_0 = (1,0,0)$, if $P^n \to U,$ as $n\to \infty$, then we would necessarily need to have $u=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ satisfy $uP=u$. We could obviously just solve here and get three linear equations (that hopefully collapse well since there is only one unknown), but instead let's math out!

Since $P$ is a transition matrix its rows sum to one, so we see that $Pu^T=u^T,$ which if we combine with $uP=u$ implies the $$Pu^T= u^T = (uP)^T = P^Tu^T.$$ So $P$ must be symmetric $(P=P^T)$, which leaves the much easier linear equation $1-p=0.4,$ that is, in order to provide the illusion of a uniform distibution of the door's landing spot through this elaborate Markov scheme you must have the probability of remaining on door 1 when the button is pressed be $p=60\%.$

Of course, armed with the knowledge that we have a symmetric transition matrix, we can then justify that this works by using the Spectral Theorem. We have already seen that $\lambda=1$ and $u^T$ is an eigenpair. We could certainly additionally calculate the other two eigenpairs as well, or simply argue that the eigenvalues must have absolute value less than $1$ and that the eigenvectors can be chosen to be an orthonormal basis of $\mathbb{R}^3$, such that $P=VDV^T,$ where $D = diag(1, \lambda_2, \lambda_3)$ and $$V= \begin{pmatrix} \sqrt{3}/3 & v_{12} & v_{13} \\ \sqrt{3}/3 & v_{22} & v_{23} \\ \sqrt{3}/3 & v_{32} & v_{33} \end{pmatrix}$$ satisfies $V^TV=VV^T=I.$ Since this $V$ represents an orthonormal basis we can change bases and represent any initial $\pi_0$ in $V$-coordinates, where the first coordinate is also $\sqrt{3}/3$ whenever $\pi_0$ sums to $1.$ Let's generically assume that $\pi_0 v_2 = c_2 \in \mathbb{R}$ and $\pi_0 v_3 = c_3 \in \mathbb{R}.$ Then we see that \begin{align*}\pi_n = \pi_{n-1} P &= \pi_{n-1} VDV^T \\ &= \cdots = \pi_0 V D^n V^T \\ &= u + c_2 \lambda_2^n v_2^T + c_3 \lambda_3^n v_3^T\end{align*} Since $|\lambda_2|, |\lambda_2| \lt 1,$ we see that for any value of $\pi_0$ we get $\pi_n \to u,$ as desired.

Extra Credit swinging the probabilities, or ... Hey, how'd the Catalan numbers show up here???

Instead of a best-of-seven series, now suppose the series is much, much longer. In particular, the first team to win $N$ games wins the series, so technically this is a best-of-($2N−1$) series, where $N$ is some very, very large number.

In the limit of large $N$, what is the probability swing for Game 1 in terms of $N$?

Applying the same logic used in the Classic Fiddler problem, we want to first find $p_{1,N} = \mathbb{P} \{ \text{win best of (2N-1) series} \mid \text{win game 1} \},$ from which we get the probability swing of game 1 in a best of $(2N-1)$ series as $\Delta_N = 2p_{1,N} - 1.$ Again following in the Classic Fiddler's solution's footsteps, if you win games $1$ and $k$, then there are $\binom{k-2}{N-2}$ ways of arranging another $N-2$ wins in the other $k-2$ games, so $$p_{1,k,N} = \mathbb{P} \{ \text{winning a best of $(2N-1)$ series in $k$ games} \mid \text{win game 1} \} = \binom{k-2}{N-2} \frac{1}{2^{k-1}}.$$ Summing over all possible values of $k = N, N+1, \dots, 2N-1,$ we get $$p_{1,N} = \sum_{k=N}^{2N-1} \binom{k-2}{N-2} \frac{1}{2^{k-1}}.$$ We could try to go further and define some generating function f_N, but this would lead to some escalating number of derivatives, that gets messy fast.

Instead let's set up a recursive formula. We note that $p_{1,1} = 1,$ which makes sense since it is a winner-takes-all one game playoff. For some $N \geq 1,$ let's take a look at $$p_{N+1} = \sum_{k=N+1}^{2N+1} \binom{k-2}{N-1} \frac{1}{2^{k-1}}.$$ The standard binomial coefficient recursion formula (which comes from the Pascal triangle) gives $$\binom{k-2}{N-1} = \binom{k-3}{N-1} + \binom{k-3}{N-2},$$ so we have \begin{align*} p_{N+1} & = \sum_{k=N+1}^{2N+1} \left(\binom{k-3}{N-1} + \binom{k-3}{N-2} \right) \frac{1}{2^{k-1}} \\ &= \left( \sum_{k=N}^{2N} \binom{k-2}{N-1} \frac{1}{2^k} \right) + \left( \sum_{k=N}^{2N} \binom{k-2}{N-2} \frac{1}{2^k} \right) \\ &= \frac{1}{2} \left( \sum_{k=N+1}^{2N} \binom{k-2}{N-1} \frac{1}{2^{k-1}} \right) + \frac{1}{2} \left( \sum_{k=N}^{2N-1} \binom{k-2}{N-2} \frac{1}{2^{k-1}} \right) + \binom{2N-2}{N-2} \frac{1}{2^{2N}} \\ &= \frac{1}{2} p_{1,N+1} - \binom{2N-1}{N-1} \frac{1}{2^{2N+1}} + \frac{1}{2} p_{1,N} + \binom{2N-2}{N-2} \frac{1}{2^{2N}}.\end{align*} Pulling the copy of $\frac{1}{2}p_{1,N+1}$ back onto the lefthand side and then multiplying by 2, we get the recursion formula \begin{align*} p_{1,N+1} &= p_{1,N} + \binom{2N-2}{N-2} \frac{1}{2^{2N-1}} - \binom{2N-1}{N-1} \frac{1}{2^{2N}} \\ &= p_{1,N} + \binom{2N-2}{N-2} \frac{1}{2^{2N-1}} - \left( \binom{2N-2}{N-1} + \binom{2N-2}{N-2} \right) \frac{1}{2^{2N}} \\ &= p_{1,N} - \frac{1}{4^N} \left( \binom{2N-2}{N-1} - \binom{2N-2}{N-2} \right) \\ &= p_{1,N} - \frac{1}{4^N} C_{N-1}, \end{align*} where $C_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1},$ for $n \in \mathbb{N}$ is the standard Catalan number.

Since we start with $p_{1,1} = 1,$ we then see that $$p_{1,N} = 1 - \sum_{k=1}^{N-1} \frac{C_{k-1}}{4^k} = 1 - \frac{1}{4} \sum_{k=0}^{N-2} \frac{C_k}{4^k}, \,\, \forall N \in \mathbb{N}.$$ We can rely on the fact that the generation function of the Catalan numbers is $$c(x) = \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1-4x}}{2x},$$ so that $$\frac{1}{4} \sum_{k=0}^\infty \frac{C_k}{4^k} = \frac{1}{4} c(\frac{1}{4}) = \frac{1}{4} \frac{1 - \sqrt{1 - 4 \cdot \frac{1}{4}}}{2 \cdot \frac{1}{4}} = \frac{1}{2}.$$ Therefore, we see that $$p_{1,N} = 1 - \frac{1}{4} \sum_{k=0}^{N-2} \frac{C_k}{4^k} = 1 - \frac{1}{4} \sum_{k=0}^\infty \frac{C_k}{4^k} + \frac{1}{4}\sum_{k=N-1}^\infty \frac{C_k}{4^k} = \frac{1}{2} + \frac{1}{4} \sum_{k=N-1}^\infty \frac{C_k}{4^k},$$ for all $N \in \mathbb{N}.$ Now when $k$ is large we have $$C_k \sim \frac{4^k}{k^{3/2} \sqrt{\pi}},$$ from repeated applications of Stirling's approximation, so when $N$ is sufficiently large we have $$\frac{1}{4} \sum_{k=N-1}^\infty \frac{C_k}{4^k} \approx \frac{1}{4\sqrt{\pi}} \sum_{k=N-1}^\infty k^{-3/2} \approx \frac{1}{2\sqrt{\pi (N-1)}},$$ where the last approximation is due to the fact that $\sum_{k=N}^\infty k^{-p} \sim \int_N^\infty x^{-p} \,dx.$ Therefore, in a fairly concise way, we have $$p_{1,N} \approx \frac{1}{2} + \frac{1}{2\sqrt{\pi(N-1)}},$$ when $N$ is large, so the probability swing of winning the first game is $$\Delta_N = 2p_{1,N} -1 \approx \frac{1}{\sqrt{\pi(N-1)}}$$ when $N$ is large.

Swinging the probabilities

You and your opponent are beginning a best-of-seven series, meaning the first team to win four games wins the series. Both teams are evenly matched, meaning each team has a 50 percent chance of winning each game, independent of the outcomes of previous games.

As the team manager, you are trying to motivate your team as to the criticality of the first game in the series (i.e., “Game 1”). You’d specifically like to educate them regarding the “probability swing” coming out of Game 1—that is, the probability of winning the series if they win Game 1 minus the probability of winning the series if they lose Game 1. (For example, the probability swing for a winner-take-all Game 7 is 100 percent.)

What is the probability swing for Game 1?

Let's break this down as follows. Let $p_1 = \mathbb{P} \{ \text{win series} \mid \text{win game 1} \}.$ In order to win the series, you must win it in $k$ games for some $k=4, 5, 6, 7,$ so let's further let $$p_{1,k} = \mathbb{P} \{ \text{win series in $k$ games} \mid \text{win game 1} \},$$ where here we see that $p_1 = \sum_{k=4}^7 p_{1,k}.$ Now, the total number of ways to win the first and $k$th games and two others somewhere in games $2$ through $k-1$ is given by $\binom{k-2}{2}$ and the overall probability of any particular combination of $k$ games is $\frac{1}{2^k},$ so $$p_{1,k} = \frac{\mathbb{P} \{ \text{win series in $k$ games and win game $1$} \}}{\mathbb{P} \{ \text{win game 1 } \}} = \binom{k-2}{2} \frac{1}{2^{k-1}}.$$ Therfore, $$p_1 = \sum_{k=4}^7 \binom{k-2}{2} \frac{1}{2^{k-1}} = \frac{1}{2} \sum_{k=4}^7 \binom{k-2}{2} \frac{1}{2^{k-2}} = \frac{1}{2} \sum_{k=2}^5 \binom{k}{2} \frac{1}{2^k}.$$

Now one way of computing $p_1$ would be using some generating function wizardry. Define the function $f(x) = \sum_{k=2}^5 \binom{k}{2} x^k,$ in which case, $p_1 = \frac{1}{2} f(\frac{1}{2}).$ Now we also see that \begin{align*} f(x) &= \frac{1}{2} x^2 \sum_{k=2}^5 k(k-1) x^{k-2} \\ &= \frac{1}{2} x^2 \frac{d^2}{dx^2} \left( \frac{1-x^6}{1-x} \right) \\ &= \frac{1}{2} x^2 \frac{d}{dx} \left( \frac{1-6x^5+5x^6}{(1-x)^2} \right) \\ &= \frac{1}{2} x^2 \frac{2(1-15x^4+24x^5-10x^6}{(1-x)^3} \\ &= \frac{ x^2 ( 1 - 15 x^4 + 24x^5 -10x^6) }{(1-x)^3}.\end{align*} So we have $$p_1 = \frac{1}{2} f(\frac{1}{2}) = \frac{1}{2} \frac{ \frac{1}{4} \left( 1 - \frac{15}{16} + \frac{24}{32} - \frac{10}{64} \right) }{ \frac{1}{8} } = \frac{ 42}{64} = \frac{21}{32}.$$

Now from symmetry, we see that the probability of you winning having lost the first game, let's say $q_1 = \mathbb{P} \{ \text{win series} \mid \text{lose game 1} \}$ is the same as the probability of you winning the series having lost the series having won the first game. That is $q_1 = 1 - p_1.$ So the proabbility swing of the first game is $$\Delta = p_1 - q_1 = p_1 - (1- p_1) = 2p_1 - 1 = 2 \frac{21}{32} - 1 = \frac{5}{16} = 32.125\%.$$

Mob rules: implied odds for binary outcomes based on bet frequency

Suppose there are two leading candidates, A and B, for MVP in the Fiddler Baseball League.

Part 1:

Assume the odds for A winning the award have been set to $+100x$, where $x \gt 1$. Let $f$ represent the fraction of dollars wagered in favor of A. For many values of $f$, the oddsmaker can set the odds for B so that they’ll make the same amount of money regardless of whether A or B wins the award. However, below a certain value of $f$, it’s impossible for the oddsmaker to do this. What is this critical value of f?

In this case, if A wins then the oddsmaker must pay out $-xf$ to the bettors who supported A but receive $+(1-f)$ from the losing bettors who supported B, so the total cashflow if A wins is $$\pi_A(x,f) = 1-(x+1)f.$$ Let's assume that if B wins that the oddsmaker will have to pay out $-\rho(1-f),$ for some $\rho \gt 0,$ while they would receive $+f$ from all of the losing A bettors. In this case, the total cashflow if B wins is $$\pi_B(f,\rho) = f - \rho(1-f).$$ If the oddsmaker wants to make sure that $$\pi = \pi_A = 1 - (x+1)f = f - \rho(1-f) = \pi_B,$$ then we would need to set the payoff ratio for B to be $$\rho = \rho(x,f) = - \frac{1 - (2+x)f}{1-f}.$$ Since we need to have $\rho \gt 0,$ and $1-f \gt 0$ by definition since $f \in (0,1),$ we must have $1 - (2+x) f \lt 0$ or equivalently $$f \gt \frac{1}{2+x}.$$ Ideally, the bookmaker wants to make a profit so we would also want to make sure that $\pi = 1 - (x+1)f \gt 0,$ so $$f \lt \frac{1}{1+x}.$$ Now we can convert the payoff ratio as follows: if $\rho \geq 1,$ then the odds for B should be $+100\rho;$ whereas, if $\rho \in (0,1)$ then the odds for B should be $-100 / \rho.$ Therefore, if the odds for A are $+100x,$ then as long as $$f \in \left(\frac{1}{2+x}, \frac{1}{1+x}\right)$$ the oddsmaker can make a profit of $\pi = 1-(1+x)f \gt 0,$ regardless of outcome.

Part 2:

Now, assume the odds for A winning the award have been set to $-100y$, where $y \gt 1$. Again, for many values of $f$, the oddsmaker can set the odds for B so they’ll make the same amount whether A or B wins the award. What is the critical value of $f$ below which this isn’t possible?

In this case, if A wins the oddsmaker must pay out $-\frac{f}{y}$ to the bettors who supported A but receive +(1-f) from the losing bettors who support B, so the total cashflow if A wins is $$\pi_A(y,f) = 1 - \left(1 + \frac{1}{y}\right) f.$$ Let's assume that if B wins that the oddsmaker will have to payout $-\varrho (1-f),$ for some $\varrho \gt 0,$ while they would receive $+f$ from all of the losing A bettors. In this case, the total cashflow if B wins is $$\pi_B(f,\varrho) = f - \varrho(1-f).$$ If the oddsmaker wants to make sure that $$\pi = \pi_A = 1 - \left(1+\frac{1}{y}\right)f = f - \varrho(1-f) = \pi_B,$$ then we would need to set the payoff ratio for B to be $$\varrho = \varrho(y,f) = - \frac{y - (2y+1)f}{y(1-f)}.$$ Since we need to have $\varrho \gt 0,$ and $1-f \gt 0$ by definition since $f \in (0,1),$ we must have $y - (2y+1) f \lt 0$ or equivalently $$f \gt \frac{y}{2y+1}.$$ Ideally, the bookmaker wants to make a profit so we would also want to make sure that $\pi = 1 - \left(1+\frac{1}{y}\right)f \gt 0,$ so $$f \lt \frac{y}{1+y}.$$ Now we can convert the payoff ratio as follows: if $\varrho \geq 1,$ then the odds for B should be $+100\varrho;$ whereas, if $\varrho \in (0,1)$ then the odds for B should be $-100 / \varrho.$ Therefore, if the odds for A are $-100y,$ then as long as $$f \in \left(\frac{y}{2y+1}, \frac{y}{1+y}\right)$$ the oddsmaker can make a profit of $\pi = 1-\left(1+\frac{1}{y}\right)f \gt 0,$ regardless of outcome.

MAWGWTWFMVP

With the regular season over, there are two clear favorites for baseball’s American League Most Valuable Player (MVP) award according to ESPN:

• Aaron Judge of the New York Yankees, whose odds are $-150$.
• Cal Raleigh of the Seattle Mariners, whose odds are $+110$.

While these betting lines may be informed by an assessment of Judge’s and Raleigh’s real chances, they may also be informed by how much money people are betting on each player. Suppose all bettors have wagered on either Judge or Raleigh with the odds above. Some fraction $f$ of dollars wagered have been in favor of Judge, while $1−f$ has been wagered on Raleigh. For what fraction $f$ will the oddsmaker earn the same amount of money, regardless of which player earns the MVP award?

Let's normalize everything so that there is a total of one unit of total dollars wagered. When the Baseball Writers Association of America rightfully crowns Cal Raleigh as the AL MVP, the bookmaker will happily take the $+f$ from all the sad crybaby losers who were enthralled by everything New York Yankees. On the other hand in this case, the bookmaker would have to payout a total of $-1.1(1-f) = 1.1f - 1.1$ to the rational baseball afficianados who saw through the glitz, glamour and sour grapes of the East Coast media blitz for Judge and bet on Raleigh. So the total cashflow for the oddsmaker is $+f + 1.1f - 1.1 = 2.1f-1.1.$

On the other hand, just from a pure devil's advocacy perspective, there could be some happenstance where Raleigh could theoretically lose the AL MVP (tvu!, tvu!, tvu!, bli ayin hara!), ranging from the incompetent (the BBWAA forgot to change over its ballots from last year), to the patehtic (the geriatric writers couldn't stay up past their East Coast bedtimes to watch the pure and utter dominace of Raleigh), to any number of more nefarious, perverse chicanery. In this purely theoretical scenario, the oddsmaker would have a total payout of $-\frac{f}{1.5} = -\frac{2f}{3}$ to those delusional Judge patrons, while they would take the $+(1-f)$ from the hard-working, salt-of-the-earth, righteous Raleigh boosters. In this infinitesimally remote scenario, the total cashflow for the oddsmaker is $-\frac{2f}{3} + 1 -f = 1 - \frac{5f}{3}.$

A sober, dispassionate bookmaker would want these two cashflows to align, no matter how justified he might be in skewing it towards Raleigh's side. In this case, the only justification for having the oddsmaker set Raleigh as the underdog in this AL MVP race is because the two sides would net the same amount of positive cashflow if $$2.1f - 1.1 = 1 - \frac{5f}{3},$$ that is, $$f = \frac{2.1}{2.1 + \frac{5}{3}} = \frac{63}{113} \approx 0.55752212389\dots$$ of all bets were for Judge, for some ungodly reason.

Average Distance from Center of a Unit Cube to Its Surface

Let’s raise the stakes by a dimension. Now, you start at the center of a unit cube. Again, you pick a random direction to move in, with all directions being equally likely. You move along this direction until you reach a point on the surface of the unit cube. On average, how far can you expect to have traveled?

So unlike shifting the shape that we are trying to hit the perimeter of, in the Extra Credit problem, we instead increase the dimensionality. Here $$B_\infty = \left\{ (x,y,z) \in \mathbb{R}^3 \mid \max \{ |x|, |y|, |z| \} = \frac{1}{2} \right\}.$$ Also, instead of parameterizing the direction of travel by a single bearing with respect to the positive $x$-axis, here we need to have two angles, one $\theta \in [0, \pi]$ with respect to the positive $z$-axis and a second $\varphi \in [0,2\pi)$ with respect to the positive $x$-axis. Since the differential of the solid angle of a region of the surface of the sphere is $d\Omega = \sin \theta \,d\varphi \,d\theta$ and the entire surface area of a unit sphere is $4\pi,$ we see that the join distribution function for $\theta$ and $\varphi$ is $$f(\theta, \varphi) = \frac{\sin \theta}{4\pi}.$$ Now, again assuming a unit speed, and given we get the position vector $$r(t) = ( t \cos \varphi \sin \theta, t \sin \varphi \sin \theta, t \cos \theta ).$$

Since you will hit $B_\infty$ whenever $t \max \{ |\cos \varphi \sin \theta|, |\sin \varphi \sin \theta|, |\cos \theta| \} = \frac{1}{2},$ so therefore the distance traveled is \begin{align*} d(\theta, \varphi) &= \frac{1}{2 \max \{ |\cos \varphi \sin \theta|, |\sin \varphi \sin \theta|, |\cos \theta| \}} \\ & = \frac{1}{2} \min \{ |\sec \varphi| \csc \theta, |\csc \varphi| \csc \theta, |\sec \theta | \}, \end{align*} where the final equation removes $\csc \theta$ from the absolute values since $\sin \theta, \csc \theta \geq 0$ for all $\theta \in [0,\pi]$

Therefore, the average distance is $$\hat{d} = \frac{1}{4\pi} \int_0^\pi \int_0^{2\pi} d(\theta, \varphi) \sin \theta \,d\varphi \, d\theta.$$ Now we can decompose this integral into three regions, two of which seem to have analytical solutions, so let's try even though we could just stop here and do the larger integral right here and right now.

Let's only worry about the upper hemisphere, that is $0 \leq \theta \leq \frac{\pi}{2}$. Here we can then break the range into the following three sections:

• Region I - when $0 \leq \theta \leq \frac{\pi}{4},$ where you will eventually hit the top of the unit cube no matter what the value of $\varphi$;
• Region II - when $\cos^{-1} \frac{1}{\sqrt{3}} \leq \theta \leq \frac{\pi}{2},$ where you will eventually hit one of the vertical sides of the unit cube no matter what the value of $\varphi$; and
• Region III - when $\frac{\pi}{4} \leq \theta \leq \cos^{-1} \frac{1}{\sqrt{3}},$ where depending on the value of $\varphi$ you will either hit the top or the sides.

In other words, in Region I, $$d_1(\theta, \varphi) = \frac{1}{2} |\sec \theta|, \forall \varphi \in [0,2\pi),$$ so we have \begin{align*}I_1 &= \frac{1}{2\pi} \int_0^{\pi/4} \int_0^{2\pi} d_1(\theta, \varphi) \,d\varphi \, \sin \theta \,d\theta \\ &= \frac{1}{2\pi} \int_0^{\pi/4} \pi \tan \theta \, d\theta = \left.-\frac{1}{2} \ln | \cos \theta | \right|^{\pi/4}_0 \\ &= \frac{1}{4} \ln 2 \approx 0.17328679514\dots.\end{align*} In Region II, $$d_2(\theta, \varphi) = \frac{\csc \theta}{2} \min \{ |\sec \varphi|, |\csc \varphi| \},$$ so we have \begin{align*} I_2 &= \frac{1}{2\pi} \int_{\cos^{-1} (1/\sqrt{3})}^{\pi/2} \int_0^{2\pi} \frac{1}{2} \min \{ |\sec \varphi|, |\csc \varphi| \} \,d\varphi \csc \theta \sin \theta \,d\theta \\ &= \int_{\cos^{-1} (1/\sqrt{3})}^{\pi/2} \left( \frac{1}{2\pi} \int_0^{2\pi} \frac{1}{2} \min \{ |\sec \varphi|, |\csc \varphi| \} \,d\varphi \right) \,d\theta\\ & = \frac{2}{\pi} \ln ( 1 + \sqrt{2} ) \left( \frac{\pi}{2} - \cos^{-1} \left(\frac{1}{\sqrt{3}}\right) \right)\\ & = \left( 1 - \frac{ 2 \cos^{-1} \left( \frac{1}{\sqrt{3}} \right) }{\pi} \right) \ln (1 + \sqrt{2}) \approx 0.345345573653\dots,\end{align*} since the integral with respect to $\varphi$ is none other than the expected distance traveled inside a square, which we found the solution for in the Classic Problem. The trickier third region has integral $$I_3 = \int_{\pi/4}^{\cos^{-1} (1/\sqrt{3})} \int_0^{2\pi} d(\theta,\varphi) \,d\varphi \sin \theta \, d\theta \approx 0.0920550322989\dots,$$ which does not seem to have a readily available analytical solution. Putting these regions together we get that the overall average distance traveled to the surface of the unit cube when uniformly randomly choosing a direction is $$\hat{d} = I_1 + I_2 + I_3 = \frac{1}{4} \ln 2 + \left( 1 - \frac{ 2 \cos^{-1} \left( \frac{1}{\sqrt{3}} \right) }{\pi} \right) \ln (1 + \sqrt{2}) + I_3 \approx 0.610687401568\dots.$$

Average Distance from Center of a Unit Square to Its Perimeter

You start at the center of the unit square and then pick a random direction to move in, with all directions being equally likely. You move along this chosen direction until you reach a point on the perimeter of the unit square. On average, how far can you expect to have traveled?

Let's assume that you start at the origin, which is the center of the unit square $B_\infty = \{ (x,y) \in \mathbb{R}^2 \mid \max \{ |x|, |y| \} = \frac{1}{2} \}.$ Further, let's assume that your randomly chosen bearing makes an angle of $\theta$ with the positive $x$-axis, so $\theta \sim U(0,2\pi),$ and let's assume that you move at some unit speed, so your position through time will be $r(t) = (t \cos \theta, t \sin \theta).$

Since you will hit the $B_\infty$ exactly when $t \max \{ |\cos \theta|, |\sin \theta| \} = \frac{1}{2}$, therefore, the distance you would travel from the origin is given by $$d(\theta) = \frac{1}{2 \max \{ |\cos \theta|, |\sin \theta| \} } = \frac{1}{2} \min \{ |\sec \theta|, |\csc \theta| \}.$$ Relying on the periodicity of $d(\theta)$ to break the entire integral into 8 equal parts, we get thatthe expected distance is therefore \begin{align*}\hat{d} &= \frac{1}{2\pi} \int_0^{2\pi} d(\theta) \,d\theta \\ &= \frac{1}{2\pi} \left( 8 \int_0^{\pi/4} \frac{1}{2} \sec \theta \,d\theta \right) \\ &= \frac{2}{\pi} \Biggl.\ln \left| \sec \theta + \tan \theta \right| \Biggr|^{\pi/4}_0 \\ &= \frac{2}{\pi} \ln \left( 1 + \sqrt{2} \right) \approx 0.561099852339\dots.\end{align*}

We can extend this problem to the slightly different problem of starting at the origin, pointing a random direction and traveling at a uniform, unit Euclidean speed until we get to any the perimeter of any half-unit ball, say $B_p = \{ (x,y) \in \mathbb{R}^2 \mid |x|^p + |y|^p = \frac{1}{2^p} \}.$ As you could possibly surmise, the official question was $B_\infty,$ which is the limit as $p \to \infty.$ In this case, we would get $$d_p (\theta) = \frac{1}{2 \sqrt[p]{\cos^p \theta + \sin^p \theta}}$$ and $$\bar{d}_p = \frac{2}{\pi} \int_0^{\pi/4} \frac{d\theta}{\sqrt[p]{\cos^p \theta + \sin^p \theta}} = \frac{4}{\pi} \int_0^{\sqrt{2}-1} \frac{dt}{\sqrt[p]{(1-t^2)^p + 2^p t^p}},$$ where the second integral is obtains through the mystical tangent half-angle substitution. In general, this is not an analytical answer, though in certain other cases it simplifies. Obviously, for the case of $p=2$ everything simplifies to $d_2(\theta) = \frac{1}{2}, \forall \theta \in [0,2\pi)$ and so $\bar{d}_2 = \frac{1}{2}$ as well. For $p=1$, we have $$d_1(p) = \frac{1}{2 (\cos \theta + \sin \theta)}$$ and \begin{align*}\bar{d}_1 &= \frac{4}{\pi} \int_0^{\sqrt{2}-1} \frac{dt}{(1-t^2) + 2t}\\ &= \frac{4}{\pi} \int_0^{\sqrt{2}-1} \frac{dt}{1+2t-t^2}\\ &= \frac{\sqrt{2}}{\pi} \int_0^{\sqrt{2}-1} \frac{1}{1 + \sqrt{2} - t} + \frac{1}{\sqrt{2} - 1 + t} \,dt \\ &= \frac{\sqrt{2}}{\pi} \left. \ln \left| \frac{\sqrt{2} - 1 + t}{\sqrt{2} + 1 - t} \right| \right|_0^{\sqrt{2}-1}\\ & = \frac{\sqrt{2}}{\pi} \left( \ln \left(\frac{2\sqrt{2}-2}{2} \right) - \ln \left( \frac{\sqrt{2}-1}{\sqrt{2}+1} \right) \right)\\ &= \frac{\sqrt{2}}{\pi} \ln ( 1 + \sqrt{2} ) \approx 0.396757510512\dots.\end{align*} For completeness's sake, below is a table for various other values of $p.$

$p$	$\bar{d}_p$
$1$	$0.396757510512\dots$
$1.5$	$0.466430018867\dots$
$2$	$0.500000000000\dots$
$2.5$	$0.518545527769\dots$
$3$	$0.529817160992\dots$
$4$	$0.542203450927\dots$
$5$	$0.548481398011\dots$
$10$	$0.557672594762\dots$
$100$	$0.561063099606\dots$
$1000$	$0.56109948237\dots$
$\infty$	$0.561099852339\dots$

Let's Make a Tic-Tac-Deal, Extra Credit

In the actual game, you get five rolls instead of three. But as with rolling a 2 or 12, rolling a number that you have already rolled is a wasted turn. With five rolls of the dice, what are your chances of getting three Xs in a row, either horizontally, vertically, or diagonally?

Let's just simulate our way out of this. We have the same 8 possible winning sets, that we will encode as sets in Python and then after simulating a 5 rolls of two dice, we can check whether the resulting set of roll outcomes contains any of the winning sets. See the code snippet below that we can use to encode playing a random round of Tic-Tac-Deal.

import numpy as np
r = np.random.default_rng()

WINS = [ {3, 4, 5}, {3, 6, 9}, {3, 7, 11},
        {4, 7, 10}, {5, 8, 11}, {5, 7, 9},
        {6, 7, 8}, {9, 10, 11}
       ]

def play_tic_tac_deal_2dot0(r, rolls=5):
    draws = r.integers(low=1,high=7, size=(rolls,2))
    final = set(draws.sum(axis=1))
    for win in WINS:
        if win.issubset(final):
            return True
    return False

Running $1$ million simulations, we infer that the probability of winning the game with $5$ dice rolls is about $36.0907\dots\%.$ In particular, the $95\%$ confidence interval is $(35.996568\%, 36.184832\%).$ Further, note that if we run these simulations with the parameter $rolls = 3,$ then we get a $95\%$ confidence interval of $(5.725294\%, 5.816706\%)$ which certainly contains our analytics answer of $\frac{113}{1944}.$

Let's Make a Tic-Tac-Deal!

The game of Tic-Tac-Deal $2.0$ has a $3$-by-$3$ square grid with the numbers $3$ through $11$, arranged as follows:

$3$	$4$	$5$
$6$	$7$	$8$
$9$	$10$	$11$

You start by rolling a standard pair of six-sided dice and add the two numbers rolled. You place an X on the board on the square that contains the sum. If the sum is a $2$ or $12$, your roll is wasted. If you have exactly three rolls of the dice, what are your chances of getting three Xs in a row (either horizontally, vertically, or diagonally)?

First, we see that $$p_n = \frac{\min\{n-1,13-n\}}{36}$$ is the probability of getting a vakue of $n$ on a roll of two standard dice. Secondly, we see that there are a total of 8 winning configurations: $\{3,4,5\}$, $\{3,6,9\}$, $\{3,7,11\}$, $\{4,7,10\}$, $\{5,7,9\}$, $\{5,8,11\}$, $\{6,7,8\}$, and $\{9,10,11\}.$

Since order doesn't matter here, the probability of getting a winning configuration $W=\{w_1, w_2, w_3\}$ is given by $$p(W)= 3! \prod_{i=1}^3 p_{w_i}.$$ So the overall probability of winning in three rolls is \begin{align*}P=\sum_W p(W)&= 3! \left( p_3p_4p_5 + p_3p_6p_9 + p_3p_7p_{11}\right. \\ &\quad\quad +p_4p_7p_{10} + p_5p_8p_{11} + p_5p_7p_9 \\ &\left.\quad\quad\quad + p_6p_7p_8 + p_9p_{10}p_{11} \right)\\ &= \frac{\left( 144 + 240 + 144 + 324 + 576 + 240 + 900 + 144 \right)}{46656} \\ &= \frac{113}{1944} \approx 5.812757\dots\%\end{align*}

What is Anita's 𝝋?

It’s time for you to check Anita’s work. What was the measure of angle $\varphi$?

Ok, so as we saw in the prior Classic Fiddler problem, Anita will be crossing the $1$-inch segment while she is on her $4$-inch line segment, that is when she is traveling from $$X_3 = (1+2\cos \varphi+3\cos 2\varphi, 2\sin \varphi + 3\sin 2\varphi)$$ to $$X_4 = (1 + 2 \cos \varphi + 3 \cos 2\varphi + 4\cos 3\varphi, 2 \sin \varphi + 3 \sin 2\varphi + 4 \sin 3 \varphi).$$ We have already somewhat loosely located $\varphi \in ( \frac{3\pi}{4}, \frac{4\pi}{5} ).$

We see that the line from $X_3$ to $X_4$ is given by $$y - 2 \sin \varphi - 3 \sin 2\varphi = \tan 3\varphi \left( x - 1 - 2 \cos \varphi - 3 \cos 2\varphi \right).$$ Additionally we note that since for large angles (e.g., $\phi = \pi$) the crossing point is near $(0,0)$ and since the crossing point for the smaller $\phi = \frac{4\pi}{5}$ being closer towards the $(1,0)$ endpoint of the initial segment, it stands to reason that for the optimal angle $\varphi,$ that the crossing point would be precisely at the endpoint $(1,0).$ In this cas we would have $$ - 2 \sin \varphi - 3 \sin 2 \varphi = \tan 3\varphi \left( -2 \cos \varphi - 3 \cos 2\varphi \right).$$ Since $$\tan 3 \varphi = \frac{ 3 \tan \varphi - \tan^3 \varphi }{ 1 - 3 \tan^2 \varphi } = \tan \varphi \frac{ 3 - \tan^2 \varphi }{ 1 - 3 \tan^2 \varphi } = \tan \varphi \frac{ 4 \cos^2 \varphi - 1}{ 4 \tan^2 \varphi - 3},$$ $$-2 \cos \varphi - 3 \cos 2\varphi = 3 - 2 \cos \varphi - 6 \cos^2 \varphi,$$ and $$2 \sin\varphi + 3 \sin 2\varphi = 2 \tan \varphi \cos \varphi ( 1 + 3 \cos \varphi ),$$ the above equality is equivalent (which much algebraic expansion and reduction) to \begin{align*} 0 &= \tan \varphi \frac{4 \cos^2 \varphi - 1}{4 \cos^2 \varphi - 3} ( 3 - 2\cos \varphi - 6 \cos^2 \varphi) + 2 \tan \varphi \cos \varphi (1 + 3 \cos \varphi) \\ &= \frac{\tan \varphi}{4 \cos^3 \varphi - 3} \left( (4 \cos^2 \varphi - 1) ( 3 - 2 \cos\varphi - 6 \cos^2 \varphi ) + 2 \cos \varphi ( 4 \cos^2 \varphi - 3 ) (1 + 3 \cos \varphi) \right) \\ &= - \frac{\tan \varphi (4 \cos \varphi + 3)}{4 \cos^2 \varphi - 3},\end{align*} so we have that $\varphi = \cos^{-1} \left(-\frac{3}{4}\right) \approx 2.41885840578\dots.$

Anita's Walk

Anita the ant is going for a walk in the sand, leaving a trail as she goes. First, she walks $1$ inch in a straight line. Then she rotates counterclockwise by an angle $\varphi$, after which she walks another $2$ inches. She rotates counterclockwise an angle $\varphi$ again, after which she walks $3$ inches. She keeps doing this over and over again, rotating counterclockwise an angle $\varphi$ and then walking $1$ inch farther than she did in the previous segment.

At some point during her journey, she crosses over her initial $1$-inch segment. By “cross over,” I am including the two end points of that first segment. Anita realizes that $\varphi$ was the smallest possible angle such that she crossed over her $1$-inch segment. (Among the ants, she’s known for her mathematical prowess.) How long was the segment along which she first crossed over the $1$-inch segment? Your answer should be a whole number of inches.

Let's let Anita's position on the $xy$-plane with origin centered at her trail's beginning after completing her line segment of length $n$, be $X_n = (x_n, y_n)$. In particular we then see that $$x_n = \sum_{k=1}^n k \cos ((k-1) \varphi) \,\,\text{and}\,\, y_n = \sum_{k=1}^n k \sin ((k-1) \varphi).$$ One thing we notice immediately is that as $n \to \infty,$ $X_n$ does not converge and in fact $\|X_n\| \to \infty.$ Therefore, if there is crossing over the initial segment it would have to happen in the first handful of steps, rather than after some extremely large cycle.

We see that if $\phi=\pi,$ then obviously Anita would de facto double back into her first line segment in her $n=2$ step, since she would start retracing her steps immediately. Let's try to see whether or not there can be some $\phi \lt \pi$ such that Anita crosses the first line segment in her $n=3$ step. In this case we see that $X_2 = (1 + 2\cos \phi, 2\sin \phi)$ and $X_3 = (1 + 2 \cos \phi + 3 \cos 2\phi, 2\sin \phi + 3\sin 2\phi),$ so the line connecting $X_2$ and $X_3$ is given by $$y - 2\sin \phi = \tan 2\phi \left( x - 1 - 2 \cos \phi \right).$$ In particular, if we assume that Anita crossed at some point $(h, 0)$ on the initial line segment, that is with $0 \leq h \leq 1,$ then we would get the equality \begin{align*}0 &= 2 \sin \phi \left( 1 - \frac{ \cos \phi \left( 2 \cos \phi + 1 - h \right) }{ \cos 2\phi } \right)\\ &= \frac{2 \sin \phi}{\cos 2\phi} \left( \cos 2\phi - \cos \phi \left( 2\cos \phi + 1 - h \right) \right) \\ &= \frac{2 \sin \phi}{\cos 2\phi} \left( 2 \cos^2 \phi - 1 - \left(2 \cos^2 \phi + (1-h) \cos \phi\right) \right) \\ &= -\frac{2\sin \phi}{\cos 2\phi} \left( 1 + (1-h) \cos \phi \right)\end{align*} For $h \in (0,1],$ we have $-\frac{1}{1-h} \lt -1,$ so there are no solutions of $\phi \in \mathbb{R}$ with $1 + (1-h) \cos \phi = 0.$ Therefore, besides the case of $\phi = \pi$ as we saw before, there are no solutions where Anita crosses the $1$-inch segment on her $n=3$ step.

Let's look at the case of say $\phi = \frac{4\pi}{5}.$ In this case, we see that $X_3 = (0.309017\dots, -1.677599\dots)$ and $X_4=(1.545085\dots, 2.126627\dots),$ so the $n=4$ line segment crosses the $1$-inch line segment at $(h,0)$ for $h\approx 0.854102\dots.$ So there is some value of $\phi$ for which Anita would cross the $1$-inch segment on the $n=4$ segment.

Let's look at another case where $\phi=\frac{3\pi}{4}.$ Here we see the $X_3=(1-\sqrt{2}, \sqrt{2}-3)$ and $X_4=(1+\sqrt{2},3\sqrt{2}-3).$ The line segment between $X_3$ and $X_4$ narrowly missed the $1$-inch segment, crossing at $(4-2\sqrt{2},0)$. We can show (or at least vigorously wave our hands) that there are no angle $\phi \leq \frac{3\pi}{4}$ that there are similarly no instances where Anita would cross the $1$-inch segment.

Therefore, we see that the length of the segment that Anita crossed the initial path with was four.

Riskier Risk, Now with Wilds!

The full deck of Risk cards also contains two wildcards, which can be used as any of the three types of cards (infantry, cavalry, and artillery) upon trading them in. Thus, the full deck consists of $44$ cards.

You must have at least three cards to have any shot at trading them in. Meanwhile, having five cards guarantees that you have three you can trade in.

If you are randomly dealt cards from a complete deck of $44$ one at a time, how many cards would you need, on average, until you can trade in three? (Your answer should be somewhere between three and five. And no, it’s not four.)

Let $S$ be the random number of cards you have when you can first turn in a set of three cards. Obviously we have $3\leq S\leq 5,$ so lets go about calculating $p_s = \mathbb{P} \{ S= s\},$ for $s \in \{3, 4, 5\},$ which we can then compute $$\mathbb{E} [S] = \sum_{s=3}^5 sp_s.$$

From the Classic wildless Risk problem, we see that there remain $3836$ possible combinations of three card sets without using any wilds. To this we must at $\binom{2}{1} \binom{42}{2} = 1722$ possible combinations of three card sets with ome wild card and $\binom{2}{2}\binom{42}{1}=42$ possible combinations of three card sets with two wild cards. In total, there are $5600$ possible sets of three cards, out of a total $\binom{44}{3}=13244$ possible hands of three Risk cards, so we have $$p_3 = \frac{5600}{13244}=\frac{200}{473}\approx 42.283\dots\%$$

Rather than the messiness of figuring out the exact combinations for $S=4$, let's instead tackle $S=5.$ We see that if you do not get a set on your fourth card then you will automatically get a set by your fifth card, so we only need to figure out what situations lead you to not have a set after four cards. This can only happen whenever you have two of one type and two of a different type (with no wilds, obviously). There are $\binom{14}{2}\binom{14}{2}\binom{3}{2}=24843$ possible hands that have exactly two cards in two different types. Since there are $\binom{44}{4} = 135751$ possible combinations of four distinct Risk cards, we thus have $$p_5=\frac{24843}{135751}=\frac{3549}{19393}\approx 18.300\dots\%$$

Since we can reason that $p_4=1-p_3-p_5 = \frac{7644}{19393}\approx 39.416\dots\%,$ we have the expected number of Risk cards needed to turn in a set is $$\mathbb{E}[S]= 3 \frac{200}{473} + 4 \frac{7644}{19393} + 5 \frac{3549}{19394} = \frac{72921}{19393} \approx 3.760171\dots$$

Risk without Wilds

There are $42$ territory cards in the deck—$14$ that depict an infantry unit, $14$ that depict a cavalry unit, and $14$ that depict an artillery unit. Once you have three cards that either (1) all depict the same kind of unit, or (2) all depict different kinds of units, you can trade them in at the beginning of your next turn in exchange for some bonus units to be placed on the board.

If you are randomly dealt three cards from the $42$, what is the probability that you can trade them in?

In this case, we see that there are $\binom{42}{3}=11480$ possible hands combined of three Risk cards if you remove the wild cards. There are $\binom{14}{3}=364$ possible combinations of three cards within any kind and three different kinds (that is, infantry, cavalry and artillery), so a total of $1092$ different three of a kind sets that can be formed. There are also $14^3 = 2744$ different one of each sets. So there a total of $3836$ sets of three Risk cards without wild cards, which implies that the probability of being able to trade in a randomly dealt set of three cards when the wild cards have been removed is $$p = \frac{3836}{11480} = \frac{137}{410} \approx 33.41463\dots \%$$

Letters Boxed, Like Surgeons General

Consider the following diagram, which consists of eight points (labeled $A$ through $H$), two on each side of the square. A valid “letter boxed” sequence starts at any of the eight points, and proceeds through all of the other points exactly once. However, adjacent points in the sequence can never be on the same side of the square. The first and last points in the sequence can be on the same side, but do not have to be.

As an illustration, $AFBCHEDG$ is a valid sequence of points. However, $AFBCHGED$ is not a valid sequence, since $H$ and $G$ are adjacent in the sequence and on the same side of the square. How many distinct valid “letter boxed” sequences are there that include all eight points on the square?

Well in total, there are $8! = 40,320$ different words that can be made up of the letters $A$ through $H$ with no repeated letters. One possible way is to get this answer is to just enumerate all $40,320$ possible words and throw away any words with forbidden doublets, like $AB$, $EF$ or $HG$. This is not too terribly time consuming in a short Python script, which yields that there are a total of $13,824$ different letters boxed that include all eight points on the square.

Instead of two points on each side of the square (and eight points in total), now there are three points on each side (and twelve points in total), labeled A through L in the diagram below. How many distinct valid “letter boxed” sequences are there that include all $12$ points on the square?

While $8!$ might be well within a modern programming languages wheelhouse to try to iterate through, $12!$ is more than $500$ million possible words that are composed of the letters $A$ through $L$ with no repeated letters. So unless we want to run a script all weekend, let's try a different approach. We can encode the 12 points on the square and the adjacency of the letter boxed game into a graph $\mathcal{G},$ where for instance there is an edge from $A$ to each letter $D, E, F, \dots, L,$ but no edge between $A$ and $B$, $A$ and $C$ or $B$ and $C,$ since they all share the same side of the square. A letter boxed that contains all twelve letters would then be a Hamiltonian path on $\mathcal{G},$ so let's liberally borrow the Python3 code provided by user Gaslight Deceive Subvert from this StackOverflow post related to enumerating all Hamiltonian paths on a graph and get to countings. Since I don't particularly care about the paths themselves and just the number of them, instead of printing the entire list of all Hamiltonian paths, I modified it to just print the number of distinct Hamiltonian paths.

To confirm that everything seemed above board, I started out with the graph from the Classic problem given by \begin{align*}\textsf{G} &\textsf{= \{'A':'CDEFGH', 'B':'CDEFGH', 'C':'ABEFGH', 'D':'ABEFGH',}\\ &\quad\quad \textsf{'E':'ABCDGH', 'F':'ABCDGH','G':'ABCDEF', 'H' : 'ABCDEF'\}}.\end{align*} THankfully, the code retrieved the answer of $13,824$ letters boxed, so I then felt confident enough to encode the Extra Credit graph as \begin{align*}\tilde{G} &\textsf{= \{'A':'DEFGHIJKL', 'B':'DEFGHIJKL', 'C':'DEFGHIJKL',}\\ &\quad\quad\quad \textsf{'D':'ABCGHIJKL', 'E':'ABCGHIJKL', 'F':'ABCGHIJKL',}\\ &\quad\quad\quad\quad \textsf{'G':'ABCDEFJKL', 'H' : 'ABCDEFJKL', 'I':'ABCDEFJKL',}\\ &\quad\quad\quad\quad\quad \textsf{ 'J' : 'ABCDEFGHI', 'K' : 'ABCDEFGHI', 'L' : 'ABCDEFGHI'\}}.\end{align*}.$$ Here, after running the code for roughly 15 minutes, we get a grand total of $53,529,984$ letters boxed with all $12$ points on the square.

High-Low Hijinks Extra Credit

Your friend is playing an epic game of “high-low” and has made it incredibly far, having racked up a huge number of points. Given this information, and only this information, what is the probability that your friend wins the next round of the game?

Let's define this problem as the following probabilistic statement, what is the conditional probability that $N \geq n+1$ given that $N \geq n,$ when $n$ is large? That is, find $$\lambda = \lim_{n \to \infty} \mathbb{P} \left \{ N \geq n+1 \mid N \geq n \right\} = \lim_{n\to \infty} \frac{\mathbb{P} \{ N \geq n+1 \}}{\mathbb{P} \{ N \geq n \} } = \lim_{n\to\infty} \frac{p_{n+1}}{p_n}.$$

One method that we can do is to just compute successive values of $p_n,$ as per the following table:

$n$	$p_n$
1	$\frac{3}{4}$
2	$\frac{13}{24}$
3	$\frac{25}{64}$
4	$\frac{541}{1920}$
5	$\frac{1561}{7680}$
6	$\frac{47293}{322560}$
7	$\frac{36389}{344064}$
8	$\frac{7087261}{92897280}$
9	$\frac{34082521}{619315200}$
10	$\frac{1622632573}{40874803200}$

Even by this point, it seems that the ratio of $p_{n+1} / p_n$ approaches roughly $0.72134752\dots,$ but let's see if we can make sense of this otherwise mysterious limit.

Let's focus on the recursion $h_{n+1}(t) = \int_0^1 I(t,x) h_n(x) \,dx$ that we saw in the Classic problem. Let's assume that we have $h_{n+1} (x) \approx \lambda h_n (x),$ for large values of $n \gg 1.$ Then the recursion formula would settle down to something like $$\lambda h^*(t) = \int_0^1 I(t,x) h^*(x) \,dx = \begin{cases} \int_t^1 h^*(x)\,dx, &\text{if $t \lt \frac{1}{2};$}\\ \int_0^t h^*(x) \,dx, &\text{if $t \gt \frac{1}{2};$}\end{cases}.$$ Differentiating both sides of the equation, we get $$\lambda \frac{d}{dt} h^*(t) = \begin{cases} -h^*(t), &\text{if $t \lt \frac{1}{2};$}\\ h^*(t), &\text{if $t \gt \frac{1}{2}.$}\end{cases}.$$ Let's focus on when $t \gt \frac{1}{2},$ in which case we have $\lambda \frac{d}{dt} h^*(t) = h^*(t),$ so we would have $h^*(t) = C \exp \left( \frac{t}{\lambda} \right)$ for $t \gt \frac{1}{2},$ with $h^*(t) = h^*(1-t) = C \exp \left( \frac{ 1-t}{\lambda} \right)$ for $t \lt \frac{1}{2}.$ In this case, plugging back in, if our recursion formula still holds for $t \gt \frac{1}{2},$ we would need to have \begin{align*}\lambda C e^{t/\lambda} &= \int_0^\frac{1}{2} C \exp \left( \frac{1-t}{\lambda} \right)\,dt + \int_\frac{1}{2}^t C\exp \left(\frac{t}{\lambda}\right) \,dt \\ &= \lambda C \left( e^{1/\lambda} - e^{1/(2\lambda)} \right) + \lambda C \left( e^{t/\lambda} - e^{1/(2\lambda)} \right) \\ &= \lambda C e^{t/\lambda} + \lambda C \left( e^{1/\lambda} - 2 e^{1/(2\lambda)} \right).\end{align*} Therefore, we must have either $\lambda = 0$ or $e^{1/\lambda} - 2 e^{1/(2\lambda)} = 0$ in order tof the recursion formula to hold, which implies that the conditional probability of winning the next round in a long game of high-low is $$\lambda = \lim_{n \to \infty} \frac{p_{n+1}}{p_n} = \frac{1}{2\ln 2} \approx 0.721347520444\dots.$$

High-Low Hijinks

You’re playing a game of “high-low,” which proceeds as follows:

• First, you are presented with a random number, $x_1$, which is between $0$ and $1.$
• A new number, $x_2$, is about to be randomly selected between $0$ and $1$, independent of the first number. But before it’s selected, you must guess how $x_2$ will compare to $x_1$. If you think $x_2$ will be greater than $x_1$ you guess “high.” If you think $x_2$ will be less than $x_1$, you guess “low.” If you guess correctly, you earn a point and advance to the next round. Otherwise, the game is over.
• If you correctly guessed how $x_2$ compared to $x_1$ then another random number, $x_3$, will be selected between $0$ and $1$. This time, you must compare $x_3$ to $x_2$, guessing whether it will be “high” or “low.” If you guess correctly, you earn a point and advance to the next round. Otherwise, the game is over.

You continue playing as many rounds as you can, as long as you keep guessing correctly. You quickly realize that the best strategy is to guess “high” whenever the previous number is less than $0.5,$ and “low” whenever the previous number is greater than $0.5.$ With this strategy, what is the probability you will earn at least two points? That is, what are your chances of correctly comparing $x_2$ to $x_1$ and then also correctly comparing $x_3$ to $x_2$?.

Let's define the indicator function $$I(s,t) = \begin{cases} 1, &\text{if $(t-s)(s-\frac{1}{2}) \leq 0;$} \\ 0, &\text{otherwise,}\end{cases}$$ such that $I(x_1,x_2) = 1$ whenever you successfully earned a point in the first round and $I(x_2,x_3) = 1$ whenever you successfully earned a second point. Let $N = N(x_1, x_2, \dots, x_n, \dots)$ be the random variable that corresponds to your score from playing this game of high-low. We see that based on this setup we have $$\mathbb{P} \{ N \geq n \} = \int_0^1 \int_0^1 \cdots \int_0^1 \prod_{i=1}^n I(x_i, x_{i+1}) \,dx_{n+1} \,dx_n \,dx_{n-1}\, \cdots \,dx_2 \,dx_1.$$ Further, let's define $h_0(t) = 1$ and $$h_1(t) = \int_0^1 I(t, x) \,dx = \begin{cases} \int_t^1 \,dx = 1-t, &\text{if $t \lt \frac{1}{2};$}\\ \int_0^t \,dx = t, &\text{if $t \geq \frac{1}{2};$} \end{cases} = \max \{ t, 1-t \}.$$ Finally, for any $n \in \mathbb{N},$ define $$h_{n+1}(t) = \int_0^1 I(t,x) h_n(x) \,dx.$$

In particular, if we want to see the probability of haveing a score of at least $2$ is \begin{align*}p_2 = \mathbb{P} \{ N \geq 2 \} &= \int_0^1 \int_0^1 \int_0^1 I(x_1,x_2) I(x_2, x_3) \,dx_3\,dx_2\,dx_1 \\ &= \int_0^1 \int_0^1 I(x_1,x_2) \left(\int_0^1 I(x_2, x_3) \,dx_3 \right) \,dx_2\,dx_1 \\ &= \int_0^1 \int_0^1 I(x_1,x_2) h_1(x_2) \,dx_2 \,dx_1\\ &= \int_0^1 h_2(x_1) \,dx_1.\end{align*} If we extrapolate further, which we will need primarily for the Extra Credit problem, we see that $$p_n = \mathbb{P} \{ N \geq n \} = \int_0^1 h_n(t) \,dt, \,\, \forall n \in \mathbb{N}.$$

Returning to the Classic problem here, we have $h_1(t) = \max \{ t, 1-t \}$ and \begin{align*}h_2(t) = \int_0^1 I(t,x) \max \{x, 1-x\} \,dx &= \begin{cases} \int_t^1 \max \{ x, 1 - x\} \,dx, &\text{if $t \lt \frac{1}{2};$} \\ \int_0^t \max \{x, 1-x\}\,dx, &\text{if $t \geq \frac{1}{2};$}\end{cases} \\ &= \begin{cases} \int_t^\frac{1}{2} (1-x) \,dx + \int_\frac{1}{2}^1 x\,dx, &\text{if $t \lt \frac{1}{2};$} \\ \int_0^\frac{1}{2} (1-x) \,dx + \int_\frac{1}{2}^t x \,dx, &\text{if $t \geq \frac{1}{2};$}\end{cases} \\ &= \begin{cases} \frac{3}{4} - t + \frac{t^2}{2}, &\text{if $t \lt \frac{1}{2};$} \\ \frac{1}{4} + \frac{t^2}{2}, &\text{if $t \geq \frac{1}{2};$}\end{cases} \\ &= \max \left\{ \frac{3}{4} -t + \frac{t^2}{2}, \frac{1}{4} + \frac{t^2}{2} \right\}.\end{align*} So we have the probability of earning at least two points is \begin{align*}p_2 = \mathbb{P} \{ N \geq 2 \} &= \int_0^1 h_2(t) \,dt\\ &= \int_0^\frac{1}{2} \left( \frac{3}{4} - t + \frac{t^2}{2} \right) \,dt + \int_\frac{1}{2}^1 \left( \frac{1}{4} + \frac{t^2}{2} \right) \,dt\\ &= \left[ \frac{3}{4}t -\frac{1}{2}t^2 + \frac{1}{6} t^3 \right]^{t=\frac{1}{2}}_{t=0} + \left[ \frac{1}{4} t + \frac{1}{6} t^3 \right]^{t=1}_{t=\frac{1}{2}} \\ &= \left(\frac{3}{8} - \frac{1}{8} + \frac{1}{48}\right) + \left(\frac{1}{4} + \frac{1}{6}\right) - \left( \frac{1}{8} + \frac{1}{48} \right) \\ &= \frac{13}{24}.\end{align*}

Sundown Trail Race with a Mulligan

Now let’s add one more wrinkle. At some point during the race, if you’re unhappy with the loop you’ve just been randomly assigned, you’re granted a “mulligan,” allowing you to get another random assignment. (Note that there’s a $25$ percent chance you’ll be assigned the same loop again.) You don’t have to use your mulligan, but you can’t use it more than once.

As before, the time is $5$:$55$ p.m. You have just completed a loop, and you haven’t used your mulligan yet. With an optimal strategy (i.e., using the mulligan at the right moment, if at all), on average, what score can you expect to earn between $5$:$55$ p.m. and $7$ p.m.?

As we saw in the Classic post, let's use the absorption probabilities matrix $B = \left(B(t,s)\right)_{t \in \mathfrak{T}, s \in \mathfrak{S}},$ which is the probability of starting at transient state $t$ and ending up at the final, absorbing state $s.$ This will give us the expected score of starting at transient state $i$ with no mulligans $$E(i) = \mathbb{E} [ S \mid S_0 = i ] = \sum_{s \in \mathfrak{S}} s B(i,s).$$ In particular, we have the vector $$E = \left(E(t)\right)_{t \in \mathfrak{T}} = \begin{pmatrix} \frac{19933}{4096} \\ \frac{5245}{1024} \\ \frac{1437}{256} \\ \frac{317}{64} \\ \frac{293}{64} \\ \frac{69}{16} \\ \frac{77}{16} \\ \frac{21}{4} \\ \frac{23}{4} \end{pmatrix}.$$

We can only use a single mulligan, but it is enough to change the overall expected score. Let's denote $$\tilde{E}(t) = \tilde{\mathbb{E}}[ S \mid S_0 = s ],$$ as the expected score when starting at state $s$. In particular, let's say that we are currently finishing up our lap to attain the transient score of $t \in \mathfrak{T},$ where we haven't yet used our mulligan, and we are quickly decide for which new laps we want to use our mulligan. Let's say the randomly assigned lap will move us from $t$ to $t^\prime \in \mathfrak{T}.$ If we use our mulligan in this turn then we will end up with an expected score of $E(t);$ whereas if we don't use the mulligan, then we would end up with an expected score of $\tilde{E}(t^\prime),$ since we would still have our mulligan remaining. So the optimal choice if we end up moving from $t$ to $t^\prime \in \mathfrak{T}$ would be to give us $\max \{ E(t), \tilde{E}(t^\prime) \}.$ Similarly, if we are randomly assigned to move from $t$ to some $s \in \mathfrak{S}$, then if we use our mulligan we end up with expected score of $E(t)$ versus a score of $s,$ if we don't. So if we are would move from $t$ to $s \in \mathfrak{S}$ the optimal choice gives us $\max \{E(t), s \}.$ Putting this altogether, we the corresponding transition probabilities from the $Q$ and $R$ matrices given in the Classic problem, we get the recursive formula $$\tilde{E}(t) = \sum_{t^\prime \in \mathfrak{T}} Q(t, t^\prime) \max \{ E(t), \tilde{E}(t^\prime) \} + \sum_{s \in \mathfrak{S}} R(t,s) \max \{ E(t), s \}.$$

So let's go recursing .... \begin{align*} \tilde{E}(5.5) &= \frac{3}{4} \max\{ E(5.5), 5.5 \} + \frac{1}{4} \max \{ E(5.5), 6.5 \} = \frac{3}{4} E(5.5) + \frac{1}{4} 6.5 = \frac{95}{16} \\ \tilde{E}(5) &= \frac{3}{4} \max \{ E(5), 5 \} + \frac{1}{4} \max \{ E(5), 6 \} = \frac{3}{4} E(5) + \frac{1}{4} 6 = \frac{87}{16} \\ \tilde{E}(4.5) &= \frac{1}{4} \max \{ E(4.5), \tilde{E}(5.5) \} + \frac{3}{4} \max \{ E(4.5), 4.5 \} = \frac{1}{4} \tilde{E}(5.5) + \frac{3}{4} E(4.5) = \frac{163}{32} \\ \tilde{E}(4) &= \frac{1}{4} \max \{ E(4), \tilde{E}(5) \} + \frac{3}{4} \max \{ E(4), 4 \} = \frac{1}{4} \tilde{E}(5) + \frac{3}{4} E(4) = \frac{147}{32} \\ \tilde{E}(3.5) &= \frac{1}{4} \max \{ E(3.5), \tilde{E}(4.5) \} + \frac{1}{2} \max \{ E(3.5), 3.5 \} + \frac{1}{4} \max \{ E(3.5), 6.5 \} \\ &\quad\quad = \frac{1}{4} \tilde{E}(4.5) + \frac{1}{2} E(3.5) + \frac{1}{4} 6.5 = \frac{83}{16} \\ \tilde{E}(3) &= \frac{1}{4} \max \{ E(3), \tilde{E}(4) \} + \frac{1}{4} \max \{ E(3), 3 \} + \frac{1}{4} \max \{ E(3), 6 \} + \frac{1}{4} \max \{ E(3), 6.5 \} \\ &\quad\quad = \frac{1}{4} E(3) + \frac{1}{4} E(3) + \frac{1}{4} 6 + \frac{1}{4} 6.5 = \frac{1411}{256}\\ \tilde{E}(2) &= \frac{1}{4} \max \{ E(2), \tilde{E}(3) \} + \frac{1}{4} \max\{ E(2), \tilde{E}(5) \} + \frac{1}{4} \max \{ E(2), \tilde{E}(5.5) \} + \frac{1}{4} \max \{ E(2), 6.5 \} \\ &\quad\quad = \frac{1}{4} E(2) + \frac{1}{4} E(2) + \frac{1}{4} \tilde{E}(5) + \frac{1}{4} 6.5 = \frac{3029}{512}\\ \tilde{E}(1) &= \frac{1}{4} \max \{ E(1), \tilde{E}(2) \} + \frac{1}{4} \max \{ E(1), \tilde{E}(4) \} + \frac{1}{4} \max \{ E(1), \tilde{E}(4.5) \} + \frac{1}{4} \max \{ E(1), \tilde{E}(5.5) \} \\ &\quad\quad = \frac{1}{4} \tilde{E}(2) + \frac{1}{4} E(1) + \frac{1}{4} E(1) + \frac{1}{4} \tilde{E}(5.5) = \frac{5657}{1024} \end{align*}

This leaves us with one more step to show that the total expected score on accrued between $5$:$55$ pm and $7$ pm going at a constant $10$ minute per mile pace with one single mulligan is \begin{align*} \tilde{E}(0) &= \frac{1}{4} \max \{ E(0, \tilde{E}(1) \} + \frac{1}{4} \max \{ E(0), \tilde{E}(3) \} + \frac{1}{4} \max \{ E(0), \tilde{E}(3.5) \} + \frac{1}{4} \max \{ E(0), \tilde{E}(4.5) \} \\ &\quad\quad = \frac{1}{4} \tilde{E}(1) + \frac{1}{4} \tilde{E}(3) + \frac{1}{4} \tilde{E}(3.5) + \frac{1}{4} \tilde{E}(4.5)\\ &\quad\quad = \frac{21921}{4096} = 5.351806640625 \end{align*}