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$$