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