This week’s Riddler Classic is a short problem 3D geometry. Here we go! (I paraphrased the question)
A polyhedron has six edges. Five of the edges have length $1$. What is the largest possible volume?
Here is my solution
[Show Solution]
A blog for mathematical riddles, puzzles, and elegant proofs
This week’s Riddler Classic is a short problem 3D geometry. Here we go! (I paraphrased the question)
A polyhedron has six edges. Five of the edges have length $1$. What is the largest possible volume?
Here is my solution
[Show Solution]
The only polyhedron with six edges is a tetrahedron, which is a pyramid with a triangular base. Two of the faces will be equilateral triangles that share a common edge. This accounts for the five edges of length 1. The length of the sixth edge is determined by the angle between the faces, which we will call $\theta$. Here is an animation showing the different tetrahedra you get as you vary $\theta$:
In this diagram, $AB=BC=AC=AD=BD=1$ and $OD=OC=\frac{\sqrt{3}}{2}$.
The volume is equal to
\begin{align}
V&=\frac{1}{3}(\text{Area of base})\cdot(\text{altitude}) \\
&= \frac{1}{3}(\text{Area ABC})\cdot(DG) \\
&= \frac{1}{3}\left( \frac{1}{2} (AB)(OC) \right) \cdot \left( (OD) \sin\theta \right) \\
&= \frac{1}{3} \cdot \frac{1}{2}\cdot 1 \cdot \frac{\sqrt{3}}{2} \cdot \frac{\sqrt{3}}{2} \cdot \sin\theta \\
&= \frac{1}{8}\cdot\sin\theta
\end{align}Therefore, the maximum volume is $\frac{1}{8}$ and it occurs when $\theta=90^\circ$. This is intuitive because the area of the base is fixed, so the largest volume occurs when the altitude is as large as possible.
This week’s Riddler Express is a short problem about infinite series. Let’s dig in! (I paraphrased the question)
You and your infinitely many friends are sharing a cake, and you come up with several different methods of splitting it.
- Friend 1 takes half of the cake, Friend 2 takes a third of what remains, Friend 3 takes a quarter of what remains after Friend 2, Friend 4 takes a fifth of what remains after Friend 3, and so on.
- Friend 1 takes $1/2^2$ (or one-quarter) of the cake, Friend 2 takes $1/3^2$ (or one-ninth) of what remains, Friend 3 takes $1/4^2$ of what remains after Friend 3, and so on.
- Same as previous, with even denominators only: Friend 1 takes $1/2^2$ of the cake, Friend 2 takes $1/4^2$ of what remains, Friend 3 takes $1/6^2$ of what remains after Friend 2, and so on.
For each of these methods, after your infinitely many friends take their respective pieces, how much cake is left?
Here is my solution
[Show Solution]
For each different method, let’s call $x_n$ the amount of cake remaining after the first $n$ friends have taken their share. Since we start with a full cake, $x_0=1$. The amount of cake remaining after all friends have taken their share is therefore $\lim_{n\to\infty} x_n$.
In this method, Friend number $n$ takes $\frac{1}{n+1}$ of what remains, which is $\frac{1}{n+1}x_{n-1}$. After this happens, the amount of cake remaining is:
\[
x_n = x_{n-1}-\frac{1}{n+1}x_{n-1} = \left(1-\frac{1}{n+1}\right)x_{n-1}.
\]The net result is therefore:
\begin{align}
x_n &= \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)\cdots\left(1-\frac{1}{n+1}\right) \\
&= \left(\frac{1}{2}\right)\left(\frac{2}{3}\right)\left(\frac{3}{4}\right)\cdots\left(\frac{n}{n+1}\right) \\
&= \left(\frac{1}{\bcancel{2}}\right)\left(\frac{\bcancel{2}}{\bcancel{3}}\right)\left(\frac{\bcancel{3}}{\bcancel{4}}\right)\cdots\left(\frac{\bcancel{n}}{n+1}\right) \\
&= \frac{1}{n+1}
\end{align}This is an example of a telescoping series; all the terms in the middle cancel out and we are left with $\frac{1}{n+1}$ of the cake after all friends have gone. Unfortunately, this tends to zero as $n\to\infty$, so with this method, there will be no cake left after all friends have gone!
In this method, Friend number $n$ takes $\frac{1}{(n+1)^2}$ of what remains. Using an approach similar to the previous method, we are left with:
\begin{align}
x_n &= \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right)\cdots\left(1-\frac{1}{(n+1)^2}\right) \\
&= \left(\frac{2^2-1}{2^2}\right)\left(\frac{3^2-1}{3^2}\right)\left(\frac{4^2-1}{4^2}\right)\cdots \left(\frac{(n+1)^2-1}{(n+1)^2}\right) \\
&= \left(\frac{1\cdot 3}{2 \cdot 2}\right)\left(\frac{2\cdot 4}{3 \cdot 3}\right)\left(\frac{3\cdot 5}{4\cdot 4}\right)\cdots \left(\frac{n\cdot(n+2)}{(n+1)(n+1)}\right) \\
&= \left(\frac{1\cdot \bcancel{3}}{2 \cdot \bcancel{2}}\right)\left(\frac{\bcancel{2}\cdot \bcancel{4}}{\bcancel{3} \cdot \bcancel{3}}\right)\left(\frac{\bcancel{3}\cdot \bcancel{5}}{\bcancel{4}\cdot \bcancel{4}}\right)\cdots \Biggl(\frac{\bcancel{n}\cdot(n+2)}{\bcancel{(n+1)}(n+1)}\Biggr) \\
&= \frac{n+2}{2(n+1)}.
\end{align}In the third step, we used the difference of squares formula $n^2-1 = (n-1)(n+1)$ to again obtain a telescoping series. This time, however, the sum is $\frac{n+2}{2(n+1)}$, for which the limit $n\to\infty$ is $\frac{1}{2}$. So half of the cake is left after all friends have gone.
In this method, Friend number $n$ takes $\frac{1}{(2n)^2}$ of what remains. Again using an approach similar to the previous methods, we obtain.
\begin{align}
x_n &= \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{4^2}\right)\left(1-\frac{1}{6^2}\right)\cdots\left(1-\frac{1}{(2n)^2}\right).
\end{align}While it looks deceptively similar to the two previous examples solved above, this infinite product is substantially more complicated since there is no telescoping. There is a way to approach this using calculus, but I will instead show a proof using complex analysis that I think is a bit more intuitive.
Every polynomial $p(z)$ of degree $n$ can be factored as $p(z)=a(z-c_1)\cdots(z-c_n)$ where the $c_k$ are zeros of the polynomial (they may be complex numbers). This result can be extended to the case where $p(z)$ is an infinite polynomial with infinitely many zeros. This is known as the Weierstrass factorization theorem. Roughly speaking, if $f(z)$ is an entire function (it must have a power series expansion that is valid everywhere), then we can write it as an infinite product $f(z)=a(z-c_1)(z-c_2)\cdots$ where the $c_k$ are zeros of the infinite polynomial.
Consider the function $f(z) = \frac{\sin(\pi z)}{\pi z}$. This is an entire function because $\sin(\pi z)$ has a power series that is valid everywhere and it has no constant term (recall $\sin(x) = x-\frac{1}{3!}x^3+\frac{1}{5!}x^5-\cdots$) so we can divide through by $\pi z$ and we get another valid power series. The places where $f(z)=0$ correspond to $z \in \{\pm1,\pm2,\pm3,\dots\}$. Note also that $f(0) = \lim_{z\to 0} \frac{\sin(\pi z)}{\pi z} = 1$. By the Weierstrass factorization theorem (I’m skipping some technical details here), we can write:
\begin{align}
f(z) &= a(1-z)(1+z)\left(1-\frac{z}{2}\right)\left(1+\frac{z}{2}\right)\left(1-\frac{z}{3}\right)\left(1+\frac{z}{3}\right)\cdots \\
&= a\left(1-z^2\right)\left(1-\frac{z^2}{2^2}\right)\left(1-\frac{z^2}{3^2}\right)\cdots
\end{align}Since $f(0) = 1$, it must be the case that $a=1$. So we have the series:
\[
\frac{\sin(\pi z)}{\pi z} = \left(1-z^2\right)\left(1-\frac{z^2}{2^2}\right)\left(1-\frac{z^2}{3^2}\right)\cdots.
\]This is known as the Euler infinite product representation for the sinc function. Substituting $z=\frac{1}{2}$, the infinite product becomes exactly the one we wanted to evaluate for how much cake is left:
\[
\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{4^2}\right)\left(1-\frac{1}{6^2}\right)\cdots = \frac{2}{\pi} \approx 0.6366.
\]This infinite product (or its inverse, rather) also has a name; it’s called the Wallis product.
As a side note, if we only keep the odd-numbered terms of the product, we obtain:
\[
\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\left(1-\frac{1}{7^2}\right)\cdots = \frac{\pi}{4} \approx 0.7854.
\]This can be proved using a similar approach, this time with the function:
\[
\cos\left(\frac{\pi z}{2}\right) = (1-z^2)\left(1-\frac{z^2}{3^2}\right)\left(1-\frac{z^2}{5^2}\right)\left(1-\frac{z^2}{7^2}\right)\cdots
\]It then follows that:
\[
\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\left(1-\frac{1}{7^2}\right)\cdots
= \lim_{z\to 1} \frac{\cos\left(\frac{\pi z}{2}\right)}{1-z^2} = \frac{\pi}{4}
\]As a sanity check, we found that using the even terms gives $\frac{2}{\pi}$ and using the odd terms gives $\frac{\pi}{4}$. So using all the terms gives $\frac{2}{\pi}\cdot \frac{\pi}{4} = \frac{1}{2}$, which is what we found using “Method 2”!
This week’s Riddler Classic is an interesting back-and forth game trying to guess whose number is larger.
Martina and Olivia each secretly generate their own random real number, selected uniformly between 0 and 1. Starting with Martina, they take turns declaring (so the other can hear) who they think probably has the greater number until the first moment they agree. Throughout this process, their respective numbers do not change. So for example, their dialogue might go as follows:
Martina: My number is probably bigger.
Olivia: My number is probably bigger.
Martina: My number is probably bigger.
Olivia: My number is probably bigger.
Martina: Olivia’s number is probably bigger.
They are playing as a team, hoping to maximize the chances they correctly predict who has the greater number.
For any given round with randomly generated numbers, what is the probability that the person they agree on really does have the bigger number?
Extra credit: Martina and Olivia change the rules so that they stop when Olivia first says that she agrees with Martina. That is, if Martina says on her turn that she agrees with Olivia, that is not a condition for stopping. Again, if they play to maximizing their chances, what is the probability that the person they agree on really does have the bigger number?
Here is my solution
[Show Solution]
The question is ambiguous as stated, because of the phrase “they are playing as a team”. What does this mean? I will address two possible interpretations.
The first interpretation is that Martina and Olivia can decide on a strategy ahead of time. In this case, any accuracy is possible, but this accuracy must be decided ahead of time. To this end, pick an integer $N \geq 1$, and use the following strategy.
The only way this algorithm can fail is if both Martina and Olivia would have failed on the same turn, e.g. they both have numbers that are contained in the same interval $\tfrac{k}{N+1} \lt x \lt \tfrac{k+1}{N+1}$ for some $k=1,\dots,N$. This happens with probability $\tfrac{1}{N}$. In this case, the algorithm produces an incorrect outcome half of the time.
This strategy will take at most $N$ turns, and produces an error with probability $\frac{1}{2N}$. Therefore, arbitrary accuracy is possible with this approach, but the accuracy must be decided between the two players before the game begins.
Extra credit: If only Olivia has the power to end the game, then this allows Martina to say whatever she wants and the game will not end. In other words, she can communicate her number to Oliva! Here is a strategy that accomplishes this:
The only way this strategy can fail is if Martina’s infinite string of binary digits is eventually constant. Since Martina’s number was chosen uniformly at random, this will occur with probability zero.
So when only one of the two players has the power to end the game, it is possible to determine who has the largest number in finitely many turns, and we outlined an approach that succeeds with probability one.
In this interpretation, “working as a team” means that Martina and Olivia are always truthful with each other. Mathematically, this means for example that Martina will say her number is larger than Olivia’s if the conditional probability that her number is larger than Olivia’s is greater than $0.5$, where we are conditioning on all of the players’ past responses.
Since the game stops whenever somebody agrees with the other person, the only way the game continues is if there is constant disagreement. This means either both players argue their number is largest, or both players argue their number is smallest. Let’s start with the “largest” case. So suppose Martina has $x \gt \frac{1}{2}$ and Olivia has $y$.
Looks like a fractal made of sim cards!
Since each rectangle has $\frac{11}{12}$ of its area shaded and the square is completely tiled with similar rectangles, this means the entire square has $\frac{11}{12}$ of its area shaded, and this is the final answer to the problem.
Extra credit: If only Olivia has the power to end the game, it turns out the outcome is exactly the same, and we get the same picture as the one above. The reason is that in any scenario where Martina would have ended the game by agreeing with Olivia, instead the game continues, and then Olivia will just agree with Martina on the very next turn. For example, if Martina thinks her number is largest, then Olivia also thinks so, and then Martina agrees with Olivia but the game continues, we now have $(x,y) \in (0.5,0.875)\times(0.75\times 1]$. At this point, the midpoint of Martina’s interval is $\frac{0.5+0.875}{2} = 0.6875$. Therefore, Olivia will always agree with Martina and end the game. The same holds for all other scenarios; the game ends with the same outcome, but will sometimes take one extra turn to do so. For that matter, you could also put the power in Martina’s hands instead of Olivia’s and again we get the same result!
This week’s Riddler Classic is a tricky puzzle that combines logic and game theory.
You will be asked four seemingly arbitrary true-or-false questions by the Sphinx on a topic about which you know absolutely nothing. Before the first question is asked, you have exactly $1. For each question, you can bet any non-negative amount of money that you will answer correctly. That is, you can bet any real number (including fractions of pennies) between zero and the current amount of money you have. After each of your answers, the Sphinx reveals the correct answer. If you are right, you gain the amount of money you bet; if you are wrong, you lose the money you bet.
However, there’s a catch. (Isn’t there always, with the Sphinx?) The answer will never be the same for three questions in a row.
With this information in hand, what is the maximum amount of money you can be sure that you’ll win, no matter what the answers wind up being?
Extra credit: This riddle can be generalized so that the Sphinx asks N questions, such that the answer is never the same for Q questions in a row. What are your maximum guaranteed winnings in terms of N and Q?
If you’re just looking for the answer, here it is:
[Show Solution]
Suppose there are $N$ total questions, and the Sphinx never gives the same answer $Q$ times in a row.
Define $F^{Q}_{n}$ to be the $n^\text{th}$ $Q$-generalized Fibonacci number. Specifically:
\begin{align}
F^Q_{n} &= 0 & \text{for }n \leq 0 \\
F^Q_1 &= 1 \\
F^Q_n &= F^Q_{n-1} + F^Q_{n-2} + \cdots + F^Q_{n-Q} & \text{for }n \geq 2
\end{align}These are also called Fibonacci $Q$-step numbers. Here are some examples (borrowed from here)
$Q$ | OEIS | Name | sequence $F^{Q}_{n}$ starting at $n=0$ |
1 | degenerate | 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, … | |
2 | A000045 | Fibonacci | 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … |
3 | A000073 | tribonacci | 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, … |
4 | A000078 | tetranacci | 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, … |
5 | A001591 | pentanacci | 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, … |
6 | A001592 | hexanacci | 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, … |
7 | A066178 | heptanacci | 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, … |
The maximum amount of money we can expect to have after $N$ questions assuming optimal play is given by the formula:
$\displaystyle
\text{Maximum guaranteed winnings} = \frac{2^{N-1}}{F^{Q-1}_{N+1}}
$
Here is the optimal strategy that achieves this gain:
Note that as $q$ increases (the Sphinx is getting closer to being forced to answer predictably), the wagers get larger. When $q=Q-1$, the wager fraction simplifies to $1$, i.e. we should wager everything because we know we will win. When $n+q \lt Q$, there aren’t enough questions remaining to force the Sphinx to answer predictably, so we can expect to always lose and we should wager nothing.
Here is a plot showing the maximum guaranteed winnings as a function of $N$ and $Q$ if we start with \$1, which is given by the formula $\frac{2^{N-1}}{F^{Q-1}_{N+1}}$.
When $Q=2$, the Sphinx must alternate answers, so we can double our money every turn! This explains why the plot grows by a factor of 2 when $Q=2$ (the vertical axis is on a logarithmic scale). The plot is also flat for $N \leq Q-1$. This corresponds to the case where we have insufficient questions to force the Sphinx to answer predictably, so our best bet is to wager nothing and cut our losses.
In the detailed write-up, I explain how all of these formulas were derived, and I also go into detail on the asymptotic growth rate we can expect for different $Q$.
Here is a more detailed write-up of the solution:
[Show Solution]
We will solve the most general version of the problem, with $N$ questions and no $Q$ answers in a row are ever the same. This is a sequential decision-making problem, where at each turn of the game, we make a move (pick an answer and pick a wager), and then the Sphinx makes a move (picking the correct answer). We are looking to maximize our guaranteed winnings, which means we should assume the Sphinx is doing her best to minimize our winnings, while we are doing our best to maximize our winnings.
We will approach this problem using recursion, by expressing any given state of the game in terms of simpler states of the game. To do this, we must think about what constitutes a state of the game; what is the complete set of information that should be used to determine our next actions? Based on the rules of the game, the key pieces of information are:
Importantly, the current amount of money we have is irrelevant, because we will always wager some proportion of our current holdings. Likewise, the amount we win in the end will also be proportional to our current holdings. For example, any strategy that guarantees we will have \$1.50 at the end if we currently have \$1 can be used to guarantee us \$3 if we currently have \$2, or \$15 if we currently have \$10.
With this knowledge in mind, define $V_{q,n}^Q$ to be the amount we will have at the end if we start with \$1 and both players (us and the Sphinx) play perfectly, the current streak is at $q$ with a limit of $Q$, and we have $n$ turns remaining. Ultimately, our goal is to find $V_{0,N}^Q$, but we’ll find all possible values in the process of solving the problem. We’ll use a dynamic programming approach, starting from simple cases (small $n$) and working our way back to the general $n=N$ case. The function $V$ we defined is typically called the value function.
Let’s call $u$ the amount we wager, with $0\leq u \leq 1$. We can consider several base (or special) cases, for which the answer is immediately apparent. Here they are:
Case $n=0$. If there are no questions left to answer, the game is over and we take home the money we currently have. So we can write:
\[
V_{q,0}^Q = 1
\qquad\text{for all }q,Q.
\]
Case $n + q \lt Q$. If there aren’t enough questions remaining for the Sphinx to reset their streak quota, then the Sphinx can make us lose our remaining turns and they suffer no consequences. If we ever find ourselves in this situation, we should cut our losses and wager $u=0$. Therefore,
\[
V_{q,n}^Q = 1\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0
\]
Case $q=Q-1$. This is the situation where the Sphinx’s hand is forced. They have already answered the same way $Q-1$ turns in a row, so they are forced to answer differently on their next turn, so we can bet everything we’ve got and we’re assured to win and double our money! Therefore, we should answer whatever the opposite to the current streak (i.e., if the correct answer was True $Q-1$ times in a row, we should answer the next question False) and we will win:
\[
V_{Q-1,n}^Q = 2 V_{1,n-1}^Q\qquad\text{and we should wager }u=1.
\]
Case $q=0$. This case is also interesting because it only happens at the start of the game. Once the game in underway, we have $q \geq 1$. So let’s see what happens on that first move. After our move, $n$ is reduced by one, and we either have $1+u$ or $1-u$, depending on whether we answered correctly or incorrectly.
\[
V_{0,n}^Q = \begin{cases}
(1+u)V_{1,n-1}^Q & \text{if we are correct} \\
(1-u)V_{1,n-1}^Q & \text{if we are incorrect}
\end{cases}
\]Keep in mind the Sphinx is out to ruin us, so for all intents and purposes, the Sphinx decides whether we are correct or not. No matter what happens, the Sphinx will accrue a streak of 1 so $q=1$. There is no trade-off here; the Sphinx can make us lose and it doesn’t cost her anything! We will lose any amount we bet, so the only safe move in this case is to bet nothing, and essentially skip our first turn. So we have:
\[
V_{0,n}^Q = V_{1,n-1}^Q
\qquad\text{and we should wager }u=0.
\]
In the general case, with a current streak of $1 \leq q \leq Q-2$ and $n$ questions left to answer, we can answer the same as the current streak, or answer differently. We can also be right or wrong. So there are four possibilities. The possibilities are:
\[
V_{q,n}^Q = \begin{cases}
\text{Answer same:} & \begin{cases}
(1+u)V^Q_{q+1,n-1} & \text{if correct} \\
(1-u)V^Q_{1,n-1} & \text{if incorrect}
\end{cases}\\
\text{Answer different:} & \begin{cases}
(1+u)V^Q_{1,n-1} & \text{if correct} \\
(1-u)V^Q_{q+1,n-1} & \text{if incorrect}
\end{cases}
\end{cases}
\]The Sphinx will always pick the option that causes us to lose as much as possible, so we can simplify this to:
\[
V_{q,n}^Q = \begin{cases}
\min\left\{ (1+u)V^Q_{q+1,n-1}, (1-u)V^Q_{1,n-1} \right\}
& \text{if we answer same}\\
\min\left\{ (1+u)V^Q_{1,n-1}, (1-u)V^Q_{q+1,n-1} \right\}
& \text{if we answer different}
\end{cases}
\]We can simplify further, by noting that $V^Q_{q,n}$ is an increasing function of $q$. In other words, the longer the current streak, the more we can expect to win, because we are closer to forcing an answer out of the Sphinx. These properties imply that $(1+u)V^Q_{q+1,n-1} \geq (1-u)V^Q_{1,n-1}$. So if we “answer same”, the Sphinx will always have us lose. Naturally, if we give the Sphinx an opportunity to take some of our money and reset its streak counter, of course she will take it! This drives us to the striking conclusion:
Always answer the opposite of the previous correct answer.
This simplifies things greatly, but we still don’t know how much to wager. We should wager an amount $u$ that maximizes our winnings assuming the Sphinx plays perfectly. Therefore:
\[
V_{q,n}^Q = \max_{0 \leq u \leq 1}
\min\left\{ (1+u)V^Q_{1,n-1}, (1-u)V^Q_{q+1,n-1} \right\}
\]In other words, we are presenting the Sphinx with a trade-off: she can choose to have us lose our wager, but this will bring her closer to filling her streak quota and forcing her hand. Or, she can reset her streak quota, but at the cost of having us win our wager.
Putting everything together, here are the dynamic programming recursions for our value function.
\begin{align}
V_{0,n}^Q &= V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=0\\
V_{q,0}^Q &= 1\qquad \text{for all }q\\
V_{q,n}^Q &= 1\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0 \\
V_{Q-1,n}^Q &= 2V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=1 \\
V_{q,n}^Q &= \max_{0 \leq u \leq 1}
\min\left\{ (1+u)V^Q_{1,n-1}, (1-u)V^Q_{q+1,n-1} \right\},\\
&\quad \text{for }\quad 1\leq q \leq Q-2\text{ and }n\geq \max\{Q-q,1\}
\end{align}
The min/max optimization is now straightforward to solve. All functions involved are linear in $u$, so the optimum will occur either at a boundary ($u=0$ or $u=1$), or it will occur at the intersection of both functions. We already took care of all boundary cases, so we are now dealing with the latter case. Therefore, the optimal wager satisfies $(1+u)V^Q_{1,n-1}=(1-u)V^Q_{q+1,n-1}$, which leads to:
\[
u_\text{opt} = \frac{V^Q_{q+1,n-1}-V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}
\quad\text{and}\quad
V^Q_{q,n} = \frac{2V^Q_{q+1,n-1}V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}
\]Our simplified recursion is therefore:
\begin{align}
V_{0,n}^Q &= V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=0\\
V_{q,0}^Q &= 1\qquad \text{for all }q\\
V_{q,n}^Q &= 1\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0 \\
V_{Q-1,n}^Q &= 2V_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=1 \\
V_{q,n}^Q &= \frac{2V^Q_{q+1,n-1}V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}
\quad\text{with wager }u = \frac{V^Q_{q+1,n-1}-V^Q_{1,n-1}}{V^Q_{q+1,n-1}+V^Q_{1,n-1}}\\
&\qquad\text{for }\quad 1\leq q \leq Q-2\text{ and }n\geq \max\{Q-q,1\}
\end{align}This still looks complicated, but we can make one last simplification. Notice that our only messy expression is the general recursion, which looks like $v = \frac{2ab}{a+b}$. We can rewrite this as: $\frac{1}{v} = \frac{1}{2}\left( \frac{1}{a} + \frac{1}{b} \right)$, which looks much nicer. To this effect, let’s make this change of variables:
\[
W^Q_{q,n} := \frac{2^n}{V^Q_{q,n}} \qquad\text{for all }Q,q,n.
\]With this change of variables, the recursion becomes linear!
\begin{align}
W_{0,n}^Q &= 2 W_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=0\\
W_{q,0}^Q &= 1\qquad \text{for all }q\\
W_{q,n}^Q &= 2^n\qquad\text{if }q+n\lt Q\quad\text{with wager }u=0 \\
W_{Q-1,n}^Q &= W_{1,n-1}^Q\qquad\text{if }n\geq 1\quad\text{with wager }u=1 \\
W_{q,n}^Q &= W^Q_{1,n-1} + W^Q_{q+1,n-1}
\quad\text{with wager }u = \frac{W^Q_{1,n-1}-W^Q_{q+1,n-1}}{W^Q_{1,n-1}+W^Q_{q+1,n-1}}\\
&\qquad\text{for }\quad 1\leq q \leq Q-2\text{ and }n\geq \max\{Q-q,1\}
\end{align}
Let’s start with the case $q=1$, so we’ll solve for $W^Q_{1,n}$. Applying the last three recursions, we get:
\begin{align}
W^Q_{1,n} &= 2^n \qquad\text{for }0 \leq n \leq Q-2 \\
W^Q_{1,n} &= W^Q_{1,n-1} + W^Q_{1,n-2} + \cdots + W^Q_{1,n-(Q-1)}\qquad\text{for }n \geq Q-1
\end{align}This further simplifies to the compact form:
\begin{align}
W^Q_{1,-k} &= 0 \qquad \text{for all }k\geq 2\\
W^Q_{1,-1} &= 1 \\
W^Q_{1,n} &= W^Q_{1,n-1} + W^Q_{1,n-2} + \cdots + W^Q_{1,n-(Q-1)}\qquad\text{for }n \geq 0.
\end{align}The sequence of $W^Q_{1,n}$ are none other than generalized Fibonacci numbers! I guess we could call them $Q$bonacci numbers? When $Q=3$, we recover the standard Fibonacci numbers (A000045):
\[
\{1,1,2,3,5,8,13,21,\dots\}
\]but shifted by 2 (we are indexing starting from -1 here, but typically Fibonacci numbers are defined where the first “1” occurs at index 1). When $Q=4$, we obtain the so-called Tribonacci numbers (A000073):
\[
\{1,1,2,4,7,13,24,44,\dots\}
\]again shifted by 2. Let’s rename the sequence so it coincides with the standard generalized Fibonacci number naming convention.
\[
F^Q_n := W^{Q+1}_{1,n-2}
\]
We can derive the rest of the $W^Q_{q,n}$ by again using the recursion, and this allows us to write all $W^Q_{q,n}$ in terms of the $Q$bonacci numbers.
\begin{align}
W^Q_{q,n}
&= W^Q_{1,n-1} + W^Q_{1,n-2} + \cdots + W^Q_{1,n-(Q-q)} \\
&= F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}
\end{align}Converting back to the value function notation, we can write a formula for $V^Q_{q,n}$ and the optimal wager $U^Q_{q,n}$ in terms of the $Q$bonacci numbers:
\[
\begin{aligned}
V^Q_{0,n} &= V^Q_{1,n-1} = \frac{2^{n-1}}{W^Q_{1,n-1}} = \frac{2^{n-1}}{F^{Q-1}_{n+1}} \\
U^Q_{0,n} &= 0 \\
V^Q_{q,n} &= \frac{2^n}{W^Q_{q,n}} = \frac{2^n}{F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}}\qquad\text{for }1\leq q \leq Q-1\\
U^Q_{q,n} &= \frac{2F^{Q-1}_{n+1}}{F^{Q-1}_{n+1} + F^{Q-1}_{n} + \cdots + F^{Q-1}_{n-(Q-q)+2}}-1
\end{aligned}
\]
Therefore, the solution to the original question, how much money can we be guaranteed to win if we wager optimally, is given by the formula
$\displaystyle
V^Q_{0,N} = \frac{2^{N-1}}{F^{Q-1}_{N+1}}
$
We might also be interested in the limit $N\to\infty$. In other words, what will our asymptotic growth rate look like if $N$ is much larger than $Q$? The generalized Fibonacci numbers have an asymptotically exponential growth, because they are solutions of a linear recurrence. This leads to Binet’s formula for the $n^\text{th}$ Fibonacci number:
\[
F^2_n = \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n – \left(\frac{1-\sqrt{5}}{2}\right)^n \right)
\]In spite of the $\sqrt{5}$ terms, this formula always produces integers! The asymptotic growth of $F^2_n$ is dictated by the term with the largest magnitude. In this case, $F^2_n \sim O\left( \varphi^n \right)$, where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. The Binet formula can also be generalized for $Q \gt 2$, and so can the asymptotic rate. The following paper by Dresden and Du does just this. I will summarize the key result.
\[
F^Q_n = O(\alpha^n)
\]Where $\alpha$ is the positive real root (there is only one) of the equation
\[
\alpha^Q = \alpha^{Q-1} + \alpha^{Q-2} + \cdots + \alpha + 1
\]In general, this polynomial will have one root that is positive and less than 2, and the other roots will be negative or complex and will have magnitude less than 1. In the paper, the authors prove that $\alpha$ increases as we increase $Q$, and $2-\frac{1}{Q} \lt \alpha \lt 2$. The growth rate of our earnings is given by $\frac{2}{\alpha}$. Here is what we obtain for different values of $Q$:
Q | Growth rate $\frac{2}{\alpha}$ |
2 | 2 |
3 | 1.236068 |
4 | 1.087378 |
5 | 1.0375801 |
6 | 1.0173208 |
7 | 1.00827652 |
8 | 1.00403411 |
9 | 1.00198836 |
10 | 1.000986237 |
There is no known closed-form expression for $\alpha$ when $Q \geq 5$ as quintics (polynomials of degree $5$) are not solvable using standard functions like square roots, but it is easy enough to approximate. One way to do this is to notice that the polynomial that defines $\alpha$ is precisely the characteristic polynomial of the $Q\times Q$ matrix:
\[
A = \begin{bmatrix}
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \ddots & 0 \\
\vdots & \vdots & \ddots & \ddots & \vdots \\
0 & 0 & \cdots & 0 & 1 \\
1 & 1 & \cdots & 1 & 1
\end{bmatrix} \in \mathbb{R}^{Q\times Q}
\]Therefore $\alpha = \rho(A)$ is spectral radius of the matrix $A$. This can be found efficiently using something like the Power Iteration, particularly because this top eigenvalue is so well-separated from the other eigenvalues, which have magnitude less than 1.
This week’s Riddler Classic is about baking the biggest pie. Just in time for π day!
You have a sheet of crust laid out in front of you. After baking, your pie crust will be a cylinder of uniform thickness (or rather, thinness) with delicious filling inside.
To maximize the volume of your pie, what fraction of your crust should you use to make the circular base (i.e., the bottom) of the pie?
Here is my solution:
[Show Solution]
Since we have a fixed amount of crust that we will shape into a cylinder, the problem is one of maximizing the volume for a fixed area. This is known as the isovolume problem (which is a misnomer; it should really be called the isoarea problem).
Let’s suppose the crust has an area of $A$. Given this area, we would like to maximize the volume of the cylinder. Let’s suppose the radius of the base is $r$ and the height is $h$. Then the formulas are:
\[
A = 2\pi r^2 + 2\pi r h \qquad\text{and}\qquad V = \pi r^2 h.
\]Since the area $A$ is fixed, we are not free to choose $r$ and $h$ independently. Once $r$ is chosen, $h$ is uniquely determined by the equation for $A$. Solving for $h$ in terms of $A$ from the area equation, we obtain:
\[
h = \frac{A-2\pi r^2}{2\pi r}
\]Substituting this value of $h$ into the equation for $V$, we obtain:
\[
V= \frac{1}{2} r (A-2\pi r^2)
\]Here is a plot of what this function $V(r)$ looks like for a value of $A=1$:
We can maximize $V$ by looking for an $r$ such that $\frac{\mathrm{d}V}{\mathrm{d}r}=0$ and $\frac{\mathrm{d}^2V}{\mathrm{d}r^2}\lt 0$. In other words, at the optimal choice of $r$, the tangent to the curve $V(r)$ is flat and the curvature is negative (curves downward). This leads to the equations:
\[
\frac{1}{2}(A-6\pi r ^2) = 0 \qquad\text{and}\qquad -6\pi r \lt 0
\]Since $r\geq 0$ (radius can’t be negative), the second equation is always satisfied, and the first equation implies that $r=\sqrt{\frac{A}{6\pi}}$. If $A=1$ as in the plot above, this leads to $r=0.23033$, which looks about right! With the optimal choice of $r$, the corresponding choice of $h$ becomes $h=\sqrt{\frac{2A}{3\pi}}$ and the corresponding optimal volume is $V=\frac{A^{3/2}}{3\sqrt{6\pi}}$. Interestingly, we can observe that with these choices,
\[
2r = 2\sqrt{\frac{A}{6\pi}} = \sqrt{\frac{4A}{6\pi}} = \sqrt{\frac{2A}{3\pi}} = h
\]So in order to maximize the area, the diameter should be equal to the height! In other words, when viewed from the side, our pie should have a square shape; we’ll be making more of a cake rather than a pie.
The fraction of crust used for the base of the optimal pie is:
\[
\frac{\pi r^2}{A} = \frac{\pi \left(\frac{A}{6\pi}\right)}{A} = \frac{1}{6}.
\]
$\displaystyle
\begin{aligned}
&\text{So we should use $\tfrac{1}{6}$ of the crust for the base, $\tfrac{1}{6}$ for the top,}\\
&\text{and the remaining $\tfrac{2}{3}$ for the sides.}
\end{aligned}$
One way to explain the shape of this tall pie is to think back to the isovolume problem discussed earlier. The solution to the isovolume problem is a sphere. So in order to be as efficient as possible, the pie’s shape should be as close to a sphere as possible, hence the tall shape. For a sphere, $A=4\pi r^2$ and $V=\frac{4}{3}\pi r^3$, so by eliminating $r$, we obtain $V=\frac{A^{3/2}}{6\sqrt{\pi}}$.
If we take the ratio of the volume of the sphere and the volume of the optimized cylinder, we obtain:
\[
\frac{V_\text{cylinder}}{V_\text{sphere}} = \frac{ \frac{A^{3/2}}{3\sqrt{6\pi}} }{ \frac{A^{3/2}}{6\sqrt{\pi}} } = \sqrt{\frac{2}{3}} \approx 0.8165
\]So the optimized cylindrical pie will have a volume which is about 82% of the largest possible volume.
If the top and bottom areas of the pie have different radii, then the shape is no longer a cylinder, but rather a frustom of a cone. The formulas are now a bit more complicated, because they depend on two radii ($r$ and $R$) and the height $h$:
\begin{align}
A &= \pi (r+R) \sqrt{h^2+(R-r)^2}+\pi \left(r^2+R^2\right)\\
V &= \frac{1}{3} \pi h \left(r^2+r R+R^2\right)
\end{align}Using a similar procedure as before (solving for $h$ in the area equation and substituting this into the volume equation), we obtain the following volume formula that depends only on the radii of the top and bottom
\[
V = \frac{\left(r^2+r R+R^2\right) \sqrt{\left(A-2 \pi r^2\right) \left(A-2 \pi R^2\right)}}{3 (r+R)}
\]A necessary condition for optimality is that both partial derivatives are zero, namely $\frac{\partial V}{\partial r} = \frac{\partial V}{\partial R} = 0$. This leads to the equations:
\begin{align}
\frac{\partial V}{\partial r} &= -\frac{r \left(A-2 \pi R^2\right) \left(2 \pi \left(4 r^2 R+2 r^3+2 r R^2+R^3\right)-A (r+2 R)\right)}{3 (r+R)^2 \sqrt{\left(A-2 \pi r^2\right) \left(A-2 \pi R^2\right)}} \\
\frac{\partial V}{\partial R} &= -\frac{R \left(A-2 \pi r^2\right) \left(2 \pi \left(2 r^2 R+r^3+4 r R^2+2 R^3\right)-A (2 r+R)\right)}{3 (r+R)^2 \sqrt{\left(A-2 \pi r^2\right) \left(A-2 \pi R^2\right)}}
\end{align}Much messier than the ordinary cylinder case… But we can simplify this. It must be true that $A\gt 2\pi R^2$ and $A\gt 2\pi r ^2$, since the area of the smaller circle plus the area of the sides must be at least the area of the larger circle (they are only equal when the pie is flat). So if $\frac{\partial V}{\partial r} = \frac{\partial V}{\partial R} = 0$, we can cancel a bunch of terms and we are left with:
\begin{align}
2 \pi \left(4 r^2 R+2 r^3+2 r R^2+R^3\right)-A (r+2 R) &= 0& &(1) \\
2 \pi \left(2 r^2 R+r^3+4 r R^2+2 R^3\right)-A (2 r+R) &= 0& &(2)
\end{align}This still looks rather messy to solve, but we can make a clever observation. If we subtract one equation from the other $(2)-(1)$ and factor, we obtain:
\[
(R-r) \left(A+2 \pi r^2+6 \pi r R+2 \pi R^2\right)=0
\]The right factor consists of a sum of positive terms, and therefore must be positive. So we conclude that $R=r$. Put another way, the only way we’ll have an optimized volume is if the top and bottom circles are of equal size. This reduces our more complicated case to the simpler case we already solved above.
This week’s Riddler Classic is a simple-looking question about the turning radius of a truck.
Suppose I’m driving a very long truck (with length L) with two front wheels and two rear wheels. (The truck is so long compared to its width that I can consider the two front wheels as being a single wheel, and the two rear wheels as being a single wheel.)
Suppose I can also rotate the front wheels by $\alpha$ and the back wheels — independently from the front wheels — by $\beta$. What is the truck’s turning radius?
Here is my solution:
[Show Solution]
When operating normally (no slippage), wheels can never slide sideways. They can only lead to motion in the direction they are pointing. In a steady turn (front and rear wheel angles constant), the wheels each trace out a circle and each wheel is tangent to its circle. Thinking about this a bit more carefully, we come to the conclusion that the front and rear wheels cannot trace out the same circle, since that would cause either the front or rear to slip. Therefore, there are actually two turning radii (inner and outer). Here is a diagram illustrating the situation:
By the law of sines, we have:
\[
\frac{r}{\sin(\tfrac{\pi}{2}-\alpha)} = \frac{R}{\sin(\tfrac{\pi}{2}-\beta)}
\]and by the law of cosines, we have:
\[
L^2 = R^2 + r^2-2rR \cos(\alpha+\beta).
\]Putting these two together and solving for $r$ and $R$, we obtain:
$\displaystyle
\frac{r}{L} = \frac{\cos(\alpha)}{\sin(\alpha+\beta)}
\quad\text{and}\quad
\frac{R}{L} = \frac{\cos(\beta)}{\sin(\alpha+\beta)}
$
We have a few cases depending on the relative size of $\alpha$ and $\beta$:
Here is a live GeoGebra script I made so you can play around with different values of the front and rear angles; click and drag to pan, use the mouse wheel to zoom, and use the sliders to change the angles!
Here is a GeoGebra link if you want to edit the file in full-screen mode.
This week’s Riddler Classic is a neat puzzle about eating chocolates.
I have 10 chocolates in a bag: Two are milk chocolate, while the other eight are dark chocolate. One at a time, I randomly pull chocolates from the bag and eat them — that is, until I pick a chocolate of the other kind. When I get to the other type of chocolate, I put it back in the bag and start drawing again with the remaining chocolates. I keep going until I have eaten all 10 chocolates.
For example, if I first pull out a dark chocolate, I will eat it. (I’ll always eat the first chocolate I pull out.) If I pull out a second dark chocolate, I will eat that as well. If the third one is milk chocolate, I will not eat it (yet), and instead place it back in the bag. Then I will start again, eating the first chocolate I pull out.
What are the chances that the last chocolate I eat is milk chocolate?
Here is my original solution:
[Show Solution]
Let’s solve the more general version of the problem, where we initially have $M$ milk chocolates and $N$ dark chocolates in the bag. When referring to a state of the game, I will write a pair $(m,n)$, where $m$ and $n$ denote the number of milk chocolates and dark chocolates remaining, respectively. Let’s define a few functions given that we are currently in state $(m,n)$:
Note that $F(m,0)=H_1(m,0)=H_2(m,0) = 1$ for all $m\geq 1$, since we always win if there are only milk chocolates remaining. Also, we have that $F(0,n)=H_1(0,n)=H_2(0,n) = 0$ for all $n \geq 1$, since we always lose if there are only dark chocolates remaining.
We can write several recursive relationships relating these functions. First, once the game starts, we always eat the first chocolate we pick, and this determines our next state of the game:
\[
F(m,n) = \tfrac{m}{m+n} H_1(m-1,n) + \tfrac{n}{m+n} H_2(m,n-1)
\]Next, once we eat a chocolate, we will either continue to do so, or we will reset the state of the game, depending on which chocolate we pick next:
\begin{align}
H_1(m,n) &= \tfrac{m}{m+n}H_1(m-1,n) + \tfrac{n}{m+n}F(m,n) \\
H_2(m,n) &= \tfrac{m}{m+n}F(m,n) + \tfrac{n}{m+n}H_2(m,n-1)
\end{align}Let’s try to eliminate $H_1$ and $H_2$ in order to obtain a recursion in $F$ alone. Starting with the expression for $H_1$, we can recurse it backward to obtain:
\begin{align}
&H_1(m,n)\\
&= \tfrac{n}{m+n}F(m,n) + \tfrac{m}{m+n}H_1(m-1,n) \\
&= \tfrac{n}{m+n}F(m,n) + \tfrac{m}{m+1}\left( \tfrac{n}{m+n-1}F(m-1,n) + \tfrac{m-1}{m+n-1}H_1(m-2,n) \right) \\
&= \cdots
\end{align}Aggregating the terms and using the definition of the binomial coefficient, we can write the expression for $H_1$ compactly as
\[
H_1(m,n) = \frac{1}{\binom{m+n}{m}}\sum_{i=1}^m \binom{n+i-1}{n-1}F(i,n)
\]Similarly, we can recurse the expression for $H_2$ and obtain:
\[
H_2(m,n) = \frac{1}{\binom{m+n}{m}}\left[ 1 + \sum_{j=1}^n \binom{m+j-1}{m-1}F(m,j)\right]
\]The reason the expressions for $H_1$ and $H_2$ look slightly different in spite of all the symmetry in this problem is due to the different initial conditions; recall that $H_1(m,0)=H_2(m,0) = 1$, whereas $H_1(0,n)=H_2(0,n) = 0$.
Now substitute these expressions into our recursion for $F$ and after simplifying, we obtain:
\begin{align}
F(m,n) &= \tfrac{m}{m+n} H_1(m-1,n) + \tfrac{n}{m+n} H_2(m,n-1)\\
&= \frac{1}{\binom{m+n}{m}}\left[ 1 + \sum_{i=1}^{m-1} \binom{n+i-1}{n-1}F(i,n) + \sum_{j=1}^{n-1} \binom{m+j-1}{m-1}F(m,j)\right]
\end{align}Together with the initial conditions $F(i,0)=1$ and $F(0,j)=0$, this recursion gives us everything we need to find $F(m,n)$ for all $m$ and $n$.
Evaluating the first few terms, we discover something shocking… $F(m,n)$ appears to be exactly equal to $\tfrac{1}{2}$ for all values of $m$ and $n$! We can verify this by mathematical induction. Since our plan is to apply the above equation to generate all values of $F$, let’s assume that $F(i,j)=\tfrac{1}{2}$ for all terms on the right-hand side of the equation. Then we can compute:
\begin{align}
F(m,n) &= \frac{1}{\binom{m+n}{m}}\left[ 1 + \frac{1}{2}\sum_{i=1}^{m-1} \binom{n+i-1}{n-1} + \frac{1}{2}\sum_{j=1}^{n-1} \binom{m+j-1}{m-1}\right] \\
&= \frac{1}{\binom{m+n}{m}}\left[ 1 + \frac{1}{2}\left( \binom{m+n-1}{n}-1\right) + \frac{1}{2}\left( \binom{m+n-1}{m}-1 \right)\right]\\
&= \frac{1}{2\binom{m+n}{m}}\left[\binom{m+n-1}{n} + \binom{m+n-1}{m}\right] \\
&= \frac{1}{2\binom{m+n}{m}}\left[\binom{m+n-1}{n} + \binom{m+n-1}{n-1}\right] \\
&= \frac{1}{2\binom{m+n}{m}}\binom{m+n}{m} \\
&= \frac{1}{2}
\end{align}In the first step, we used the Hockey Stick Identity, in the third step we used the symmetry identity $\binom{n}{k}=\binom{n}{n-k}$, and in the fourth step we used the Pascal’s Triangle identity, namely $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$.
So amazingly, the probability of winning the game is independent of how many chocolates of each type are in the bag to begin with (as long as you have at least one of each type to begin with)! I have yet to come up with an elegant or intuitive way to understand why the answer should be independent of the initial number of chocolates, so if you have any ideas, leave them in the comments section below!
Given the surprising solution to the previous problem, one might suspect that the pattern continues; if there are three different types of chocolates in the bag (say, milk chocolate, dark chocolate, and white chocolate), then perhaps the probability of eating a milk chocolate last is $\tfrac{1}{3}$? Unfortunately, this is not the case. Here are the recursions:
\begin{align}
F(m,n,p) &= \tfrac{m}{m+n+p} H_1(m-1,n,p) + \tfrac{n}{m+n+p} H_2(m,n-1,p) + \tfrac{p}{m+n+p} H_3(m,n,p-1) \\
H_1(m,n,p) &= \tfrac{m}{m+n+p}H_1(m-1,n,p) + \tfrac{n+p}{m+n+p}F(m,n,p) \\
H_2(m,n,p) &= \tfrac{n}{m+n+p}H_2(m,n-1,p) + \tfrac{m+p}{m+n+p}F(m,n,p) \\
H_3(m,n,p) &= \tfrac{p}{m+n+p}H_3(m,n,p-1) + \tfrac{m+n}{m+n+p}F(m,n,p)
\end{align}The initial conditions are a bit more complicated. For all $m\geq 1$:
\[
F(m,0,0)=H_1(m,0,0)=H_2(m,0,0)=H_3(m,0,0)=1
\]and for all $n\geq 0$ and $p \geq 0$ with $n+p \geq 1$, we have:
\[
F(0,n,p)=H_1(0,n,p)=H_2(0,n,p)=H_3(0,n,p)=0
\]A quick numerical check reveals that the solution is not $F(m,n,p)=\tfrac{1}{3}$. Here are a few values for $i=1,2,\dots$ and $j=1,2,\dots$:
\begin{align}
F(i,j,1) &= \begin{bmatrix}
\frac{1}{3} & \frac{13}{36} & \frac{3}{8} & \frac{23}{60} & \frac{7}{18} & \frac{11}{28} \\
\frac{5}{18} & \frac{7}{24} & \frac{71}{240} & \frac{107}{360} & \frac{25}{84} & \frac{25}{84} \\
\frac{1}{4} & \frac{31}{120} & \frac{31}{120} & \frac{115}{448} & \frac{685}{2688} & \frac{2041}{8064} \\
\frac{7}{30} & \frac{43}{180} & \frac{53}{224} & \frac{209}{896} & \frac{1237}{5376} & \frac{291}{1280} \\
\frac{2}{9} & \frac{19}{84} & \frac{299}{1344} & \frac{293}{1344} & \frac{493}{2304} & \frac{21343}{101376} \\
\frac{3}{14} & \frac{73}{336} & \frac{857}{4032} & \frac{199}{960} & \frac{10271}{50688} & \frac{40283}{202752} \\
\end{bmatrix} \\
F(i,j,2) &= \begin{bmatrix}
\frac{13}{36} & \frac{5}{12} & \frac{107}{240} & \frac{167}{360} & \frac{10}{21} & \frac{163}{336} \\
\frac{7}{24} & \frac{1}{3} & \frac{127}{360} & \frac{131}{360} & \frac{187}{504} & \frac{379}{1008} \\
\frac{31}{120} & \frac{53}{180} & \frac{4159}{13440} & \frac{203}{640} & \frac{31133}{96768} & \frac{52357}{161280} \\
\frac{43}{180} & \frac{49}{180} & \frac{2551}{8960} & \frac{1171}{4032} & \frac{2957}{10080} & \frac{4757}{16128} \\
\frac{19}{84} & \frac{65}{252} & \frac{929}{3456} & \frac{5507}{20160} & \frac{83627}{304128} & \frac{65203}{236544} \\
\frac{73}{336} & \frac{125}{504} & \frac{10393}{40320} & \frac{10529}{40320} & \frac{372011}{1419264} & \frac{13285}{50688} \\
\end{bmatrix} \\
F(i,j,3) &= \begin{bmatrix}
\frac{3}{8} & \frac{107}{240} & \frac{29}{60} & \frac{227}{448} & \frac{1405}{2688} & \frac{4309}{8064} \\
\frac{71}{240} & \frac{127}{360} & \frac{2561}{6720} & \frac{3567}{8960} & \frac{39623}{96768} & \frac{67351}{161280} \\
\frac{31}{120} & \frac{4159}{13440} & \frac{1}{3} & \frac{55961}{161280} & \frac{1275}{3584} & \frac{1283833}{3548160} \\
\frac{53}{224} & \frac{2551}{8960} & \frac{24679}{80640} & \frac{128069}{403200} & \frac{288059}{887040} & \frac{233803}{709632} \\
\frac{299}{1344} & \frac{929}{3456} & \frac{517}{1792} & \frac{105989}{354816} & \frac{1297237}{4257792} & \frac{3793873}{12300288} \\
\frac{857}{4032} & \frac{10393}{40320} & \frac{490247}{1774080} & \frac{1013213}{3548160} & \frac{3575315}{12300288} & \frac{1580549}{5381376} \\
\end{bmatrix}
\end{align}As anticipated, symmetry dictates that $F(k,k,k)=\tfrac{1}{3}$, and we do observe this in the numerical results above, but aside from that there is no immediately apparent pattern.
I didn’t put too much effort into trying to find a closed form for this case or the more general case with $k$ types of chocolates. If you think of a neat way to do it, leave a message in the comments section below!
And here is a far more elegant solution, courtesy of @rahmdphd on Twitter.
[Show Solution]
Let’s say the game is “reset” when no matter which chocolate we pick, we will eat it. Once we’ve eaten a chocolate of one type, then subsequent turns will either involve eating more of that same type of chocolate if we keep picking them, or the game will reset again if we pick differently. Let’s also define a “run” to be when you start from the reset state, and then keep picking chocolates of the same type until none are left.
Once we go on a run, the outcome of the game is decided: a run on milk chocolates means you only have dark chocolates remaining so you definitely lose. Likewise, a run on dark chocolates means you will definitely win.
The game starts in the “reset” state, and consists of some number of repeated resets (each time, with strictly fewer total chocolates in the bag), until we finally go on a run, and then the game ends.
If we are reset and have $(m,n)$ chocolates in the bag, what is the probability of a run on milk chocolates?
\[
\frac{m}{m+n} \cdot \frac{m-1}{m+n-1} \cdot \ldots \cdot \frac{1}{n+1} = \frac{m!n!}{(m+n)!}
\]Similarly, what is the probability of a run on dark chocolate?
\[
\frac{n}{m+n} \cdot \frac{n-1}{m+n-1} \cdot \ldots \cdot \frac{1}{m+1} = \frac{m!n!}{(m+n)!}
\]These two probabilities are exactly the same! And amazingly, this fact is always true regardless of how many chocolates are in the bag (as long as we have at least one of each type left).
So no matter how many resets we get, when the time comes for our run, we are always equally likely to run out of either chocolate. So the probability of winning the game is $\frac{1}{2}$.
This argument does not generalize to the case where there are $3$ types of chocolates, because the probability of running out of milk, dark, or white chocolates is:
\[
\frac{m!(n+p)!}{(m+n+p)!},\, \frac{n!(m+p)!}{(m+n+p)!},\, \frac{p!(m+n)!}{(m+n+p)!}
\]and these three quantities are not equal!
his week’s Riddler Classic has to do with the card game “War”. Here is the problem, paraphrased:
War is a two-player game in which a standard deck of cards is first shuffled and then divided into two piles with 26 cards each; one pile for each player. In every turn of the game, both players flip over and reveal the top card of their deck. The player whose card has a higher rank wins the turn and places both cards on the bottom of their pile. Assuming a deck is randomly shuffled before every game, how many games of War would you expect to play until you had a game that lasted just 26 turns (with no ties; a flawless victory)?
Here is my solution:
[Show Solution]
Suppose our cards have values $\{1,2,\dots,n\}$ and the deck contains $m_i$ cards with value $i$. The total number of cards in the deck is equal to $m = m_1 +\dots+m_n$, and we assume $m$ is even so that the deck can be evenly split in half. In a standard deck of playing cards, we have $n=13$ and $m_1=m_2=\dots=m_n = 4$.
Rather than thinking about “how many games we would expect to play before I had a flawless game”, let’s instead work out the probability that a game of War will be flawless for me (I wins in $m/2$ turns with no ties). This is a counting problem: how many ways are there of arranging the cards in the deck so that I win flawlessly?
To this effect, define $f(m_1,\dots,m_n)$ to be the number of ways I can win flawlessly if the cards remaining have distribution $(m_1,\dots,m_n)$. We will develop a recursive formulation of $f$.
If I pick “$i$” in the first round, I will win the round with no tie if my opponent picks “$j$” with $j \lt i$. This can happen in $m_i m_j$ ways, and then I can win the remaining rounds flawlessly in $f(\dots)$ ways, where the arguments $m_i$ and $m_j$ are each decremented by $1$. Therefore, we can write:
\[
f(m_1,\dots,m_n) = \sum_{1 \leq j \lt i \leq n} m_i m_j f(m_1,\dots,m_j-1,\dots,m_i-1,\dots,m_n)
\]We also have the terminal condition $f(0,\dots,0)=1$, for if we ever achieve this condition, there are no cards left and we have won!
We can make two critical observations that will greatly simplify computation of $f$:
Equipped with these tools, we can write very efficient code to compute the solution for the case of a standard deck of cards. Here is an efficient recursive implementation in Python that computes the solution for a standard deck of cards.
from itertools import combinations def memoize(f): memo = {} def helper(x): # prune zeros and sort! y = tuple( sorted([z for z in x if z > 0]) ) if y not in memo: memo[y] = f(y) return memo[y] return helper @memoize def winning_hands(counts): N = len(counts) if N == 0: # base case (no cards left in the deck) return 1 out = 0 for i1,i2 in combinations(range(N),2): tmp = list(counts) tmp[i1] -= 1 tmp[i2] -= 1 out += counts[i1] * counts[i2] * winning_hands(tmp) return out winning_hands( 13 * [4] )
The code took about 100ms to compute the answer:
\[
252656585660288881535364185959261220490470307542335488000000
\]
We can divide this by the total number of hands (which is $m!$) to obtain the probability of winning flawlessly.
from math import factorial from fractions import Fraction Fraction( winning_hands(13 * [4]), factorial(52) )
And the result is:
\begin{align}
p &= \mathrm{Prob}(\text{flawless win}) \\
&= \frac{93686147409122073121}{29908397871631390876014250000} \\
&\approx 3.132436\times 10^{-9}
\end{align}
This is a very small number, but the more we play, the likelier we are to win. To quantify this, suppose we play $N$ games. The probability that we win flawlessly at least once is $1-(1-p)^N$. We can plot this as a function of $N$ to see how it grows:
So to have a $50\%$ chance of winning flawlessly at least once, I would have to play around 220 million times. To have a $95\%$ chance of winning flawlessly at least once, I would have to play around 1 billion times. Needless to say, that’s a lot of war.
his week’s Riddler Classic involves designing maximum-area polygons with a fixed budget on the length of the perimeter and the number of vertices. The original problem involved designing enclosures for hamsters, but I have paraphrased the problem to make it more concise.
You want to build a polygonal enclosure consisting of posts connected by walls. Each post weighs $k$ kg. The walls weigh $1$ kg per meter. You are allowed a maximum budget of $1$ kg for the posts and walls.
What’s the greatest value of $k$ for which you should use four posts rather than three?
Extra credit: For which values of $k$ should you use five posts, six posts, seven posts, and so on?
Here is my solution:
[Show Solution]
For a fixed perimeter, the maximum-area polygon with $n$ sides is a regular polygon. Since we are interested in maximizing area, we should therefore always use regular polygons as our shape, and we should always use our entire mass budget of $1$ kg.
Let’s assume the weight of the posts $k$ is given and fixed. If the perimeter is $p$ and the number of sides is $n$, the formula for the area of a regular $n$-gon is as follows (explanation here).
\[
A = \frac{p^2}{4n \tan\frac{\pi}{n}}
\]Our total budget constraint is that $p + kn \leq 1$. Since our goal is to maximize area we should always use our entire budget. So $p = 1-kn$. This means that $n \leq \frac{1}{k}$ in order to ensure we respect the weight budget. So for a fixed $k$, the maximum area of an $n$-gon enclosure is given by the formula
$\displaystyle
A = \frac{(1-kn)^2}{4n\tan\frac{\pi}{n}}\qquad\text{for: }2\leq n \leq \frac{1}{k}
$
Let’s talk about limiting cases for a moment.
So for each $k$, we should choose the $n \in \{2,3,4,\dots,\lfloor \tfrac{1}{k}\rfloor\}$ that maximizes $A$. Here is a plot showing plots of $A$ for each $n$ and $k$. When $k$ is large (posts weigh a lot), we try to use as few of them as possible. So at first, the triangle ($n=3$) is best. As we decrease $k$, it eventually becomes more efficient to use a square ($n=4$), and so on. As $k$ goes to zero, we obtain the solution with $n\to\infty$, which is the circular enclosure discussed above.
To find out where the transition occurs between $n$ and $n+1$, we should look for the value of $k$ at which the areas match (indicated by the black dots on the plot). So we want to find $k$ such that:
\[
\frac{(1-kn)^2}{4n\tan\frac{\pi}{n}} = \frac{(1-k(n+1))^2}{4(n+1)\tan \frac{\pi}{n+1}}
\]Solving this equation for $k$, we obtain:
$\displaystyle
k_n = \frac{ \sqrt{n \tan \frac{\pi}{n}}-\sqrt{(n+1) \tan \frac{\pi}{n+1}} }{ (n+1)\sqrt{n \tan \frac{\pi}{n}}-n\sqrt{(n+1) \tan \frac{\pi}{n+1}} }
$
We can interpret this formula as follows: $k_n$ is the smallest value of $k$ for which we should use $n$ posts in our enclosure. So if we make $k$ smaller, it becomes more efficient to use $(n+1)$ posts instead. Here are the first few numerical values of $k_n$:
$n$ | $k_n$ | Range of $k$ for this $n$ |
---|---|---|
$2$ | $0.333333$ | $0.333333 \leq k$ |
$3$ | $0.089642$ | $0.089642 \leq k \leq 0.333333$ |
$4$ | $0.039573$ | $0.039573 \leq k \leq 0.089642$ |
$5$ | $0.021016$ | $0.021016 \leq k \leq 0.039573$ |
$6$ | $0.012511$ | $0.012511 \leq k \leq 0.021016$ |
$7$ | $0.008056$ | $0.008056 \leq k \leq 0.012511$ |
$8$ | $0.005494$ | $0.005494 \leq k \leq 0.008056$ |
This week’s Riddler Classic is a paradoxical question about cutting a ruler into smaller pieces.
Recently, there was an issue with the production of foot-long rulers. It seems that each ruler was accidentally sliced at three random points along the ruler, resulting in four pieces. Looking on the bright side, that means there are now four times as many rulers — they just happen to have different lengths. On average, how long are the pieces that contain the 6-inch mark?
With four cuts, each piece will be on average 3 inches long, but that can’t be the answer, can it?
Here is my solution:
[Show Solution]
We will consider the following more general version of the problem.
Suppose a ruler of length $L$ is marked at a fraction “$a$” from one end of the ruler. Now suppose $N-1$ cuts are chosen uniformly at random along the length of the ruler, which splits the ruler into $N$ smaller pieces. What is the expected length of the piece that contains the mark?
In the original problem, $L=12\text{ inches}$, $a=\tfrac{1}{2}$, and $N=4$.
We will start by considering a simpler problem. Suppose we have $k$ numbers chosen uniformly at random and independently on the interval $[0,b]$. What is the expected value of $\min_{1\leq i \leq k} x_i$? We can compute this using the fact that:
\begin{align}
\mathbb{E}\left( \min_{1\leq i \leq k} x_i \right) &= \int_0^b \mathbf{Prob}( \min(x_i) \geq t )\,\mathrm{d}t \\
&= \int_0^b \mathbf{Prob}( x_1 \geq t, \dots, x_k \geq t )\,\mathrm{d}t \\
&= \int_0^b \mathbf{Prob}( x_1 \geq t) \cdots \mathbf{Prob}( x_k \geq t )\,\mathrm{d}t \\
&= \int_0^b \mathbf{Prob}( x_1 \geq t)^k\,\mathrm{d}t \\
&= \int_0^b \left( \frac{b-t}{b}\right)^k \mathrm{d}t \\
&= \frac{b}{k+1}
\end{align}The first equality follows from the fact that expectation can be written as the integral of the complementary cumulative distribution function (wiki link). Then, we use the fact that the $x_i$ are mutually independent and identically distributed.
Back to our original problem, we can split it into cases depending on how many cuts end up to the left vs how many end up to the right of our mark. Suppose we have $k$ cuts to the left of $a$, and the remaining $N-k-1$ cuts to the right. Then the expected length of the piece containing $a$ is the sum of the expected lengths of the “left part” and “right part”. Each of these pieces can be computed based on the preliminary result above, and we obtain:
\[
L\left(\frac{a}{k+1}+\frac{1-a}{N-k}\right)
\]Note that this formula gives the correct answer when $k=0$; it returns a length of $a$ for the left half (the whole interval). Next, we must compute the probability of this actually occurring; that exactly $k$ cuts are on the left and $N-k-1$ cuts are on the right. Since the probability of these events happening are $a$ and $1-a$, respectively, and they are mutually independent, we have a binomial distribution. The probability that $k$ cuts are to the left of $a$ is therefore:
\[
\binom{N-1}{k}a^k (1-a)^{N-k}
\]Combining these two facts, the expectation we seek to evaluate can be written as the sum:
\[
\sum_{k=0}^{N-1} L\left(\frac{a}{k+1}+\frac{1-a}{N-k}\right) \binom{N-1}{k}a^k (1-a)^{N-k-1}
\]We can split this into two separate sums. For the first one,
\begin{align}
&\sum_{k=0}^{N-1} \frac{L a}{k+1}\binom{N-1}{k}a^k (1-a)^{N-k-1}\\
&= \sum_{k=0}^{N-1} \frac{L}{N}\binom{N}{k+1}a^{k+1} (1-a)^{N-k-1} \\
&= \sum_{k=1}^{N} \frac{L}{N}\binom{N}{k}a^{k} (1-a)^{N-k} \\
&= \frac{L}{N}\left( 1-(1-a)^N \right)
\end{align}where we used the binomial theorem in the final step to evaluate the sum. Using a similar argument for the other half of the sum, we obtain $\frac{L}{N}\left( 1-a^N\right)$. Combining both parts, we find our final formula for the expected length of the piece containing the mark:
$\displaystyle
\frac{L}{N}\Bigl( 2-a^N-(1-a)^N \Bigr)
$
In particular, for the original problem statement, $L=12\text{ inches}$, $a=\tfrac{1}{2}$, and $N=4$. So the final answer is $\frac{45}{8}= 5.625\text{ inches}$. This is substantially longer than the average length of each piece, which is 3 inches.
Several interpretations of this fact were brought to my attention, so I will relay a couple here.
Commenter Guy D. Moore noted that this is an example of selection bias. My colleague Kangwook Lee also pointed out that this phenomenon is precisely the inspection paradox from probability theory.
Here is an intuitive explanation for why the true answer is so much larger than 3. The longer pieces of ruler are more likely to contain the 6-inch mark. In fact, any piece longer than 6 inches is guaranteed to contain the 6-inch mark! Although such pieces are rare, we are conditioning on the fact that our piece contains the 6-inch mark, so we are likelier to pick out these longer pieces and so the average piece length will be longer.
As a sanity check, let’s see what happens when we consider the limiting behavior of our formula.
Here is a figure showing how much longer the marked piece of ruler is compared to the average length $\frac{L}{N}$. We can visually confirm the three limiting cases: when $N=1$, we just get the average length, if $a=0$ or $a=1$ we also get the average length, and as $N\to\infty$, we do indeed tend to $2$. The solution to the original problem ($a=\tfrac{1}{2}$ and $N=4$) produces a ratio of $1.875$, which when multiplied by the average length $\frac{L}{N} = \frac{12}{4} = 3$ produces the answer we reported above, $5.625$.