Can You Race Across the Chess Board?

fiddler-2024.01.26.md

Can You Race Across the Chess Board?

This Week's Fiddler

We can draw a line across the diagonal of the board (top left to bottom right); due to symmetry of the board, the optimal time from the bottom left to the top right is twice the optimal time from the bottom left to said diagonal. Additionally, due to symmetry along the other diagonal, it does not matter if we travel through the top-left white square or the bottom-right white square.

Arbitrarily, let's say we travel through the bottom-right white square. We can say there's a point at $(1, x)$ (in cm) where this happens, where $0\le x\le 1$. The distance travelled in the first black square is $\sqrt{1+x^2}$ with a speed of $0.9$, making a time of $\frac{\sqrt{1+x^2}}{0.9}=\frac{10}{9}\sqrt{1+x^2}$. After crossing, we can beeline to the diagonal (with a slope of 1); the total distance travelled in the white square is $(1-x)\sqrt{2}$. Then the last black square travel is symmetric to the first, making it also $\frac{10}{9}\sqrt{1+x^2}$. This makes the final time:

$2(\frac{10}{9}\sqrt{1+x^2})+(1-x)\sqrt{2}$

Minimum is at $x=\frac{9}{\sqrt{119}}$, making the time needed $\sqrt{2}+\frac{\sqrt{238}}{9}$, or about 3.1284 minutes.

Answer: (sqrt(2) + sqrt(238)/9) minutes

Extra Credit

We can extend this idea to finding the point of intersection for the 8 by 8 board, except this time we would need 7 variables.

Because it is difficult to solve for the minimum of a 7-variable multivariate function, I used SciPy to find an optimal estimate:

import math

from scipy.optimize import minimize


def alice(X):
    ans = (1 - X[-1]) * math.sqrt(2)
    for i, (a, b) in enumerate(zip([0, *X[:-1]], X)):
        mult = (10 / 9) if (i % 2 == 0) else 1
        ans += 2 * mult * math.sqrt((1 - a) ** 2 + b**2)
    return ans


print(minimize(alice, (0.5,) * 7, method="Nelder-Mead", tol=0.00001))

Output:

       message: Optimization terminated successfully.
       success: True
        status: 0
           fun: 11.799178130784053
             x: [ 5.280e-01  7.501e-01  1.852e-01  1.000e+00  2.090e-09
                  9.999e-01  6.510e-05]
           nit: 872
          nfev: 1335
 final_simplex: (array([[ 5.280e-01,  7.501e-01, ...,  9.999e-01,
                         6.510e-05],
                       [ 5.280e-01,  7.501e-01, ...,  9.999e-01,
                         6.511e-05],
                       ...,
                       [ 5.280e-01,  7.501e-01, ...,  9.999e-01,
                         6.511e-05],
                       [ 5.280e-01,  7.501e-01, ...,  9.999e-01,
                         6.513e-05]]), array([ 1.180e+01,  1.180e+01,  1.180e+01,  1.180e+01,
                        1.180e+01,  1.180e+01,  1.180e+01,  1.180e+01]))

So we have an estimate of about 11.799 minutes.

Just to verify, we can confirm that this function also works for part 1:

print(minimize(alice, (0.5,), method="Nelder-Mead", tol=0.00001))

       message: Optimization terminated successfully.
       success: True
        status: 0
           fun: 3.128352297990603
             x: [ 8.250e-01]
           nit: 19
          nfev: 38
 final_simplex: (array([[ 8.250e-01],
                       [ 8.250e-01]]), array([ 3.128e+00,  3.128e+00]))

3.1284 - nice 😎

Answer: 11.799 minutes