One square makes you faster, one square makes you slow...

A very tiny Alice (not to be confused with the Alice from last week) is racing across a 2-by-2 chessboard, as shown below, where each smaller square has a side length of 1 cm. Alice starts at the bottom-left corner of the bottom-left black square and is trying to reach the top-right corner of the top-right black square.

There’s just one catch. Alice moves faster on the white squares than she does on the black squares. Her speed on the white squares is 1 cm per minute (again, she’s very small), while her speed on the black squares is 0.9 cm per minute. What’s the least amount of time it will take her to reach the finish?

Since within each square, Alice's speed is constant, she will travel in straight lines within each square making a piecewise straight path from the lower left corner, at $(0,0)$, to upper right corners, at $(2,2)$. Let's say, based on the augmented picture below, that Alice first cuts a straight line for the point $(1,h)$ through the dark square, then heads to the point $(2-k, 1),$ before finishing at $(2,2),$ for some $0 \leq h, k \leq 1.$

The time elapsed in minutes by Alice for this path is $$T(h,k) = \frac{10}{9} \left( \sqrt{1 + h^2} + \sqrt{1 + k^2} \right) + \sqrt{ (1-h)^2 + (1-k)^2 }.$$ Taking the the gradient of the time elapsed function gives $$\nabla T = \begin{pmatrix} \frac{10h}{9\sqrt{1+h^2}} - \frac{1-h}{\sqrt{(1-h)^2 + (1-k)^2}} \\ \frac{10k}{9\sqrt{1+k^2}} - \frac{1-k}{\sqrt{(1-h)^2 + (1-k)^2}} \end{pmatrix}.$$ Setting the partial derivative with respect to $h$ to zero, we get $$\frac{10h}{9\sqrt{1+h^2}} = \frac{1-h}{\sqrt{(1-h)^2 + (1-k)^2}}.$$ Setting the partial derivative with respect to $k$ to zero, we get $$\frac{10k}{9\sqrt{1+k^2}} = \frac{1-k}{\sqrt{(1-h)^2 + (1-k)^2}}.$$ Combining these, we see that this would imply that $$\frac{h}{(1-h)\sqrt{1+h^2}} = \frac{k}{(1-k)\sqrt{1+k^2}},$$ which since $f(x) = \frac{x}{(1-x)\sqrt{1+x^2}}$ is monotonically increasing for $x \geq 0$ implies that $h = k.$ In this case, we get that we must have $$\frac{10h}{9\sqrt{1+h^2}} = \frac{1-h}{\sqrt{(1-h)^2 + (1-h)^2}} = \frac{1}{\sqrt{2}},$$ or equivalently $$\frac{h}{\sqrt{1+h^2}} = \frac{9\sqrt{2}}{20}.$$ Squaring both sides and solving for $h$, we get $h^2 ( 1 - \frac{81}{200} ) = \frac{81}{200},$ which give an optimal value of $h^* = k^* = \frac{9}{\sqrt{119}}.$ Plugging back into the time elapsed, shows that Alice can get reach the finish optimally in $$\begin{align*}T^* &= T\left( \frac{9}{\sqrt{119}}, \frac{9}{\sqrt{119}} \right) \\ &= \frac{20}{9} \sqrt{ 1 + \frac{81}{119} } + \sqrt{ \left(1 - \frac{9}{\sqrt{119}}\right)^2 + \left(1 - \frac{9}{\sqrt{119}} \right)^2 } \\ &= \frac{200 \sqrt{2}}{9 \sqrt{119}} + \sqrt{2} \left( 1 - \frac{9}{\sqrt{119}} \right) = \frac{\sqrt{2}}{\sqrt{119}} \left( \frac{200}{9} - 9 + \sqrt{119} \right)\\ &= \sqrt{2} \left( 1 + \frac{\sqrt{119}}{9} \right) \approx 3.12835... \,\text{minutes}.\end{align*}$$

Expanding Alice's journey to go to the final position of $(8,8),$ we can rely on certain portions of the argument for the $(2,2)$ case, but there are certainly some additional complications. Here we will generically have 14 possible values $h_1, \dots, h_{14}$ as shown in the figure below, we can rely on the symmetry to reduce the number of variables by a factor of two (i.e., $h_1 = h_{14}$, $h_2 = h_{13}$, $\dots$, $h_7 = h_8$).

In this case, we find that the time elapsed by Alice in minutes is $$\begin{align*}\tilde{T}(h_1, \dots, h_7) &= \frac{20}{9} \left( \sqrt{1+h_1^2} + \sum_{i=1}^3 \sqrt{h_{2i}^2 + h_{2i+1}^2} \right) \\ &\quad\quad+ 2\sqrt{(1-h_1)^2 + (1-h_2)^2} + 2\sqrt{(1-h_3)^2 + (1-h_4)^2}\\ &\quad\quad\quad + 2\sqrt{(1-h_5)^2 + (1-h_6)^2} + \sqrt{2} (1 - h_7).\end{align*}$$

In this case we can take the gradient of $\tilde{T}$ and get $$\nabla \tilde{T} (h) = \begin{pmatrix} \frac{20h_1}{9 \sqrt{1+h_1^2} } - \frac{2(1-h_1)}{\sqrt{ (1-h_1)^2 + (1-h_2)^2}} \\ \frac{20h_2}{9 \sqrt{h_2^2 + h_3^2} } - \frac{2(1-h_2)}{\sqrt{(1-h_1)^2 + (1-h_2)^2}} \\ \frac{20h_3}{9 \sqrt{h_2^2 + h_3^2} } - \frac{2(1-h_3)}{\sqrt{ (1-h_3)^2 + (1-h_4)^2}} \\ \frac{20h_4}{9 \sqrt{h_4^2 + h_5^2} } - \frac{ 2(1-h_4)}{\sqrt{ (1-h_3)^2 + (1-h_4)^2} } \\ \frac{20h_5}{9 \sqrt{h_4^2 + h_5^2} } - \frac{2 (1-h_5)}{\sqrt{(1-h_5)^2 + (1-h_6)^2}} \\ \frac{20h_6}{9 \sqrt{h_6^2 + h_7^2} } - \frac{ 2 (1-h_6) }{ \sqrt{ (1-h_5)^2 + (1-h_6)^2 } } \\ \frac{20h_7}{9 \sqrt{h_6^2 + h_7^2} } - \sqrt{2} \end{pmatrix}.$$ Let's first assume that there is some solution $\hat{h}$ in the interior of $[0,1]^7,$ where $\tilde{T}$ is infinitely differentiable. If we set the gradient to zero and solve for the last equation, we get that $$\frac{h_7^2}{h_6^2 + h_7^2} = \frac{81}{200},$$ which implies that $$\frac{h_6^2}{h_6^2 + h_7^2} = \frac{119}{200}.$$ Plugging this back into the second to last coordinate, we get that $$\frac{(1-h_6)^2}{(1-h_5)^2 + (1-h_6)^2} = \frac{1}{4} \frac{400}{81} \frac{119}{200} = \frac{119}{162},$$ which in turn implies that $$\frac{(1-h_5)^2}{(1-h_5)^2 + (1-h_6)^2} = \frac{43}{162}.$$ Plugging this into the third to last coordinate, we get that $$\frac{h_5^2}{h_4^2 + h_5^2} = \frac{81}{400} \cdot 4 \cdot \frac{43}{162} = \frac{43}{200},$$ which implies that $$\frac{h_4^2}{h_4^2 + h_5^2} = \frac{157}{200}.$$ Plugging this into the next coordinate, we get that $$\frac{(1-h_4)^2}{(1-h_3)^2 + (1-h_4)^2} = \frac{1}{4} \frac{400}{81} \frac{157}{200} = \frac{157}{162},$$ which implies that $$\frac{(1-h_3)^2}{(1-h_3)^2 + (1-h_4)^2} = \frac{5}{162}.$$ Continuing onward, this implies that $$\frac{h_3^2}{h_2^2 + h_3^2} = \frac{81}{400} \cdot 4 \cdot \frac{5}{162} = \frac{1}{40},$$ which in turn means that $$\frac{h_2^2}{h^2_2 + h^2_3} = \frac{39}{40}.$$ Plugging this value into the second coordinate and solving gives $$\frac{(1-h_2)^2}{(1-h_1)^2 + (1-h_2)^2} = \frac{1}{4} \frac{400}{81} \frac{39}{40} = \frac{65}{54};$$ however, this is a contradiction since for any $a, b \in \mathbb{R},$ $$\frac{a^2}{a^2 + b^2} \leq 1.$$ Therefore, there must not be some solution in the interior of $[0,1]^7.$

Instead, we must have solutions with some variables on the endpoints of $\{0, 1\}.$ While the contradiction above was arrived at by initially setting $h_7$ to something nonzero, we will arrive at similar contradictions unless we have $h_4 = h_5 = h_6 = h_7 = 0,$ since if let's say that $h_4 > 0 = h_5,$ then since the normal cone of $[0,1]^7$ at $h$ is given by $$\mathcal{N}_{[0,1]^7}(h) = \left\{ y \in \mathbb{R}^7_{-} \mid y_i h_i = 0 \right\}$$ in order for $h$ to be an optimizer of $\tilde{T}$ on $[0,1]^7$ we would need to have $$\frac{\partial}{\partial h_5} \tilde{T} = \frac{20}{9} - \frac{2 (1-h_4)}{\sqrt{(1-h_3)^2 + (1-h_4)^2} = 0,$$ which again since $$0 \leq \frac{1-h_4}{\sqrt{(1-h_3)^2 + (1-h_4)^2} } \leq 1$$ for all values of $h_3, h_4 \in [0,1]$ we will be hard pressed to solve. So let's then reduce the problem to optimizing the further reduced function $$\begin{align*}\check{T} (h_1, h_2, h_3) &= \tilde{T} (h_1, h_2, h_3, 0, 0, 0, 0)\\ &= \frac{20}{9} \left( \sqrt{1 + h_1^2} + \sqrt{h_2^2 + h_3^2} \right)\\ &\quad\quad + \sqrt{ (1-h_1)^2 + (1-h_2)^2 } + \sqrt{ 1 + (1-h_3)^2 } + 3 \sqrt{2}\end{align*}$$ over $[0,1]^3.$

Here again, we have the reduced and slightly modified gradient $$\nabla \check{T} = \begin{pmatrix} \frac{20h_1}{9 \sqrt{1+h_1^2} } - \frac{2(1-h_1)}{\sqrt{ (1-h_1)^2 + (1-h_2)^2}} \\ \frac{20h_2}{9 \sqrt{h_2^2 + h_3^2} } - \frac{2(1-h_2)}{\sqrt{(1-h_1)^2 + (1-h_2)^2}} \\ \frac{20h_3}{9 \sqrt{h_2^2 + h_3^2} } - \frac{2(1-h_3)}{\sqrt{ 1 + (1-h_3)^2}}\end{pmatrix}.$$ Since this still yields some gnarly system of quadratics, at this point, though you can also just give up and program it, finding $\hat{h} = (0.485699\dots, 0.0737739\dots, 0.057801\dots)$ which yields an optimal value of $$\check{T}^* = \tilde{T}^* = 11.78815\dots$$ minutes for Alice to get to $(8,8)$.

The Oldest Sister's Burden

Three siblings are at a playground: Alice, Bob, and Carey. Alice, the oldest, gets a call from their dad \emdash their pancake dinner is ready! But they won’t get to eat until all three kids are home.

They each walk home at a different constant speed. Alice can walk home in 10 minutes, Bob can do it in 20, and Carey in 30. Fortunately, any of the kids can carry any of the others on their back without reducing their own walking speed. (However, none of them can carry a kid who is, in turn, carrying another kid.) Assume that they can pick someone up, set someone down, and change direction instantaneously.

What is the fastest they can all get home?

Clearly Alice, the oldest sister will have to do some amount of carrying, else everyone will be waiting for Carey to get home in 30 minutes. If Bob is never carried, then the best possible dinner time is 20 minutes after their dad's call. To do better, let's envision a scheme where indefatiguable Alice first carries one sibling for $t$ minutes, then drops that sibling and reverses course and travels away from home to meet up with the other sibling, then carries that second sibling the rest of the way home.

The time, let's say $t_1 = t_1(t, v_2),$ it will take Alice to travel away from home until she meets up with the other sibiling will be a function of the chosen first time period $t$ and the speed of the second sibling, $v_2$. In particular, if Alice and the second sibling were both traveling for $t$ minutes, then given the differential in their speeds, they would be a distance of $\frac{t}{10} - tv_2$ apart (assuming distance to home is the unit length here). In this case, in order for both of them to make up that distance at their relative combined speed of $v_2 + \frac{1}{10},$ we have $$t_1 = t\frac{\frac{1}{10} - v_2}{\frac{1}{10}+ v_2} = t \frac{1-10v_2}{1+10v_2}.$$ Additionally of note, Alice and her second siblings meeting occurs $$d = d(t, v_2) = (t + t_1) v_2 = t v_2 \left( 1 + \frac{1 - 10v_2}{1 + 10v_2} \right) = \frac{ 2t v_2 }{1 + 10v_2}$$ home lengths away from the playground. So in order for Alice and the second sibling to arrive home, it will take another, let's say $$t_2 = t_2(t, v_2) = \frac{1 - d(t,v_2)}{0.1} = 10 - 10d = 10 - \frac{20tv_2}{1 + 10v_2}$$ minutes. So Alice and one sibling will arrive at $$\begin{align*}T_A = T_A(t,v_2) &= t + t_1(t, v_2) + t_2(t, v_2) \\ &= t + t \frac{1 - 10v_2}{1 + 10v_2} + 10 - \frac{20tv_2}{1+10v_2} \\ &= 10 + \frac{ t(1 + 10v_2) + t(1-10v_2) - 20 t v_2) }{1 + 10v_2} \\ &= 10 + \frac{ 2t - 20t v_2}{1 + 10v_2} = 10 + 2t \frac{1-10v_2}{1+10v_2}\end{align*}$$ minutes.

Meanwhile, the first sibling that Alice dropped off after $t$ minutes has been trudging home under their own power at a uniform rate of $v_1$ and will arrive home at $$T_1 = T_1(t, v_1) = t + \frac{1 - \frac{t}{10}}{v_1} = \frac{1}{v_1} - t\frac{1 - 10v_1}{10 v_1}.$$ So the time when all of the siblings are safely home and devouring pancakes for dinner is $$\begin{align*}T = T(t, v_1, v_2) &= \max \{ T_A(t, v_2), T_1(t, v_1) \} \\ &= \max \left\{ 10 + 2t \frac{1 - 10v_2}{1 + 10v_2}, \frac{1}{v_1} - t \frac{1-10v_1}{10v_1} \right\} \end{align*}$$ So in particular, if Alice first picks up Bob and then Carey, we have $$T_{B,C} = T_{B,C} (t) = T\left(t, \frac{1}{20}, \frac{1}{30}\right) = \max \{ 10 + t, 20 - t \},$$ while if Alice first picks up Carey and then Bob, we have $$T_{C,B} = T_{C,B} (t) = T\left(t, \frac{1}{30}, \frac{1}{20}\right) = \max \left\{10 + \frac{2}{3}t, 30 -2t \right\}.$$ The optimal value of $T_{B,C}$ is $$T_{B,C}^* = \min_{t \in [0,10]} T_{B,C} (t) = 15 \,\text{minutes},$$ which occurs when $t^* = 5$ minutes; whereas, the optimal value of $T_{C,B}$ is $$T_{C,B}^* = \min_{t \in [0,10]} T_{C,B} (t) = 17.5 \, \text{minutes},$$ which occurs when $t^* = 6.5$ minutes. So between the two cases of carrying Bob first or carrying Carey first, the children will be eating pancakes sooner if Alice carries Bob first.

We can safely exclude the cases of either Bob carrying Carey at first, or Alice having more than one session of carrying any individual sibling, since each of these cases would lead to Carey, the slowest of the bunch, having a longer average speed home and thus delaying pancake festivities. Therefore, the fastest that Alice, Bob and Carey can all get home is in 15 minutes, where Alice carries Bob for 5 minutes, then sends him home, goes back to meet Carey and upon meeting Alice carries Carey the rest of the way home.

Dice Dungeon

Two people are sitting at a table together, each with their own bag of six “DnD dice”: a d4, a d6, a d8, a d10, a d12, and a d20. Both people randomly pick one die from their respective bags and then roll them at the same time. For example, suppose the two dice selected are a d4 and a d12. The players roll them, and let’s further suppose that both rolls come up as 3. What luck!

What’s the probability of something like this happening? That is, what is the probability that both players roll the same number, whether or not they happened to pick the same kind of die?

There are twenty possible outcomes $1, 2, \dots, 20$, however, since for instance, the probability that a d4 die rolls 17 is nil, we have a non-uniform distribution of outcomes. All outcomes less than or equal to $4$ are always possible no matter which die is selected, so the probability is $$p_i = \frac{1}{6} \left( \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{10} + \frac{1}{12} + \frac{1}{20} \right) = \frac{93}{720}, \,\, i = 1, 2, 3, 4.$$ The conditional probability of getting i \in \{5,6\} given that the d4 die was selected is zero, so we have $$p_i = \frac{1}{6} \left( 0 + \frac{1}{6} + \frac{1}{8} + \frac{1}{10} + \frac{1}{12} + \frac{1}{20} \right) = \frac{63}{720}, \,\, i = 5,6.$$ Doing similar manipulations for other outcomes gives $$p_i = \begin{cases} \frac{93}{720}, &\text{for $i = 1, 2, 3, 4$}\\ \frac{63}{720}, &\text{for $i = 5,6$;}\\ \frac{43}{720}, &\text{for $i = 7,8$;}\\ \frac{28}{720}, &\text{for $i = 9,10$;}\\ \frac{16}{720}, &\text{for $i = 11,12$;}\\ \frac{6}{720}, &\text{for $i = 13, 14, 15, 16, 17, 18, 19, 20$.}\end{cases}$$

Let the roll person 1 be $X,$ with probability distribution given by $\mathbb{P} \{ X = i \} = p_i.$ Similarly let the roll of person 2 be $Y,$ which has the i.i.d. distribution. Then the probability that both rolls are the same, i.e., $X=Y,$ is given by $$\begin{align*}\mathbb{P} \{ X = Y \} &= \sum_{i=1}^{20} \mathbb{P} \{ X = Y = i \} \\ &= \sum_{i=1}^{20} \mathbb{P} \{X=i\} \mathbb{P} \{Y = i\}\\ &= \sum_{i=1}^{20} p_i^2 \\ &= \frac{1}{720^2} \left( 4 \cdot 93^2 + 2 \cdot 63^2 + 2 \cdot 43^2 + 2 \cdot 28^2 + 2 \cdot 16^2 + 8 \cdot 6^2 \right) \\ &= \frac{48600}{518400} = \frac{3}{32} = 9.375\%.\end{align*}$$

If we went further and added a third person who has a bag of DnD dice. Again, all three randomly pick one die from their respective bags and roll them at the same time. For example, suppose the three dice selected are a d4, a d20, and a d12. The players roll them, and let’s further suppose that the d4 comes out as 4, the d20 comes out as 13, and the d12 comes out as 4. In this case, there are two distinct numbers (4 and 13) among the three rolls.

On average, how many distinct numbers would you expect to see among the three rolls?

Well the hard part of establishing the distribution is done, so let's assume $X$, $Y$ and now $Z$ are all i.i.d. with $\mathbb{P}\{X = i\} = \mathbb{P}\{Y=i\} = \mathbb{P}\{Z=i\} = p_i, i = 1, 2, \dots, 20.$ Let $N$ be the number of distinct rolls. I'm lazy so I'm going to leave $N=3$ alone and instead tackle $N=1$ and $N=2.$ The probability that $X=Y=Z$ and hence $N = i$ is by extension of the previous problem $$\mathbb{P} \{N=1\} = \sum_{i=1}^{20} p_i^3 = \frac{3930360}{373248000} = \frac{32753}{3110400} \approx 1.05302.....\%$$

For $N=2,$ we have a modicum of work. As we saw above if $X=Y$ then this would be represented by $p_i^2,$ but then in this case of $N = 2,$ we must have $Z \ne X=Y,$ which has probability of $(1-p_i).$ Furthermore, since the order of $X, Y, Z$ doesn't matter, there are 3 possible ways to get two rolls of $i$ and one roll of anything but $i.$ So we have $$\mathbb{P} \{ N=2\} = 3 \sum_{i=1}^{20} p_i^2 (1-p_i) = \frac{93184920}{373248000} = \frac{776541}{3110400} \approx 24.96595....\%$$

The only thing left to do is compute the expectation, $$\begin{align*}\mathbb{E} [N] &= 1 \cdot \mathbb{P} \{ N=1\} + 2 \cdot \mathbb{P} \{N=2\} + 3 \cdot \left( 1- \mathbb{P}\{N=1\} - \mathbb{P} \{N=2\} \right)\\ &= 3 - 2\mathbb{P} \{N=1\} -\mathbb{P}\{N=2\}.\end{align*}$$ So the expected number of unique numbers among the three rolls is $$\begin{align*}\mathbb{E}[N] &= 3 - 2 \cdot \frac{32753}{3110400} - \frac{776541}{3110400} \\ &= \frac{9006847}{3110400} \approx 2.89571984\end{align*}$$