Can You Break The Riddler Bank?

Riddler Express

In a grid maze, the number in each box tells you how many spaces up, down, left, or right you must move (no diagonals). Starting at the yellow $6$ in the bottom-left corner, can you reach the asterisk?

The Riddler, FiveThirtyEight, October 18, 2019(original post)

Status

Solving the maze needs the published grid: the specific number printed in every box, which is given only as an image with no machine-readable transcription. Without those numbers the moves cannot be reconstructed. The puzzle has a definite answer (the asterisk is reachable, in as few as eight moves, found by working backwards from the goal or by a breadth-first search over the grid), but it is an image-specified path-finding puzzle.

The Express is therefore deferred from the worked-solution standard, in the same category as the column’s other image-only grid and maze puzzles. Were the grid transcribed, it would be a short breadth-first search.

Riddler Classic

Riddler Nation has two coins: the Dio ($$538$) and the Phantus ($$19$). The bank converts a dollar amount only if it can be written as a whole number of Dios and Phanti. What is the largest dollar amount that cannot be converted, i.e. the largest whole number not expressible as $538x + 19y$ with $x, y \ge 0$? Extra credit: if a third coin worth $$101$ is added, what is the largest non-convertible amount then?

The Riddler, FiveThirtyEight, October 18, 2019(original post)

Solution

This is the Frobenius coin problem. For two coin values that share no common factor, $\gcd(538, 19) = 1$, every large enough amount is payable, and the largest that is not has a classic closed form, $$g(a, b) = ab - a - b.$$ Here that gives $$g(538, 19) = 538 \cdot 19 - 538 - 19 = 10222 - 557 = \boxed{9665}.$$ The reason: group amounts by their remainder modulo $19$. Each remainder class first becomes payable at some multiple of $538$ (since $538 \equiv 6 \pmod{19}$, the multiples of $538$ cycle through all $19$ remainders). The last remainder to unlock does so at the $18$th multiple, $538 \cdot 18 = 9684$; the largest unpayable amount in that class is $9684 - 19 = 9665$, and every amount above it is payable.

For the extra credit, adding a $$101$ coin has no two-coin closed form, but the largest non-representable amount is a quick search: $$g(19, 101, 538) = \boxed{1799}.$$ The third coin fills in many previously unreachable amounts, dropping the threshold sharply.

The computation

Encode representability directly with a coin-reachability table (a number is reachable if subtracting some coin leaves a reachable number), then take the largest unreachable amount and confirm everything above it is reachable.

def reachable(n, coins):
    dp = [False] * (n + 1); dp[0] = True
    for i in range(1, n + 1):
        dp[i] = any(i >= c and dp[i - c] for c in coins)
    return dp

dp = reachable(11000, [19, 538])
g = max(i for i in range(11001) if not dp[i])
print("Frobenius(19, 538) =", g, "| all above representable:", all(dp[g + 1:]))

dp3 = reachable(3000, [19, 101, 538])
g3 = max(i for i in range(3001) if not dp3[i])
print("Frobenius(19, 101, 538) =", g3, "| all above:", all(dp3[g3 + 1:]))
# Frobenius(19, 538) = 9665 | all above representable: True
# Frobenius(19, 101, 538) = 1799 | all above: True

The search confirms $9665$ for the two coins and $1799$ once the $$101$ coin is added.