Can You Randomly Move The Tower?

Riddler Express

Five three-digit numbers fill the rows of a CrossProduct table. The product of each number’s digits is $135, 45, 64, 280, 70$, and the products down the hundreds, tens and ones columns are $3{,}000$, $3{,}969$ and $640$. Find all five numbers.

Solution

As with any CrossProduct, factor each row’s product into three digits and let the column products select the right factorization. A short backtracking search gives the unique answer: $$\boxed{395,\ 591,\ 818,\ 578,\ 572.}$$ The hundreds digits multiply to $3\cdot5\cdot8\cdot5\cdot5 = 3{,}000$, the tens to $9\cdot9\cdot1\cdot7\cdot7 = 3{,}969$, and the ones to $5\cdot1\cdot8\cdot8\cdot2 = 640$, all as required.

The computation

List each row’s digit triples and search for the combination matching the three column products.

rows = [135, 45, 64, 280, 70]
cols = (3000, 3969, 640)
opts = [[(h, t, o) for h in range(1, 10) for t in range(1, 10)
         for o in range(1, 10) if h*t*o == p] for p in rows]
sols = []
def search(i, prod, acc):
    if any(prod[c] > cols[c] for c in range(3)): return
    if i == len(rows):
        if prod == list(cols): sols.append(acc)
        return
    for h, t, o in opts[i]:
        search(i + 1, [prod[0]*h, prod[1]*t, prod[2]*o], acc + [f"{h}{t}{o}"])
search(0, [1, 1, 1], [])
print(len(sols), sols[0])     # 1, ['395','591','818','578','572']

Riddler Classic

Cassius the ape has a three-disk Tower of Hanoi, all disks on one pole. He only ever makes a uniformly random legal move (never placing a larger disk on a smaller one). On average, how many moves until he solves it, meaning all three disks end up together on any other pole?

Solution

Track the state by which pole each of the three disks is on; all $3^3 = 27$ such states are legal, since disks always rest largest-at-the-bottom. From any state the legal moves are to lift the top disk of a pole onto an empty pole or onto a larger top disk, and Cassius picks among them uniformly. Two states win: all three disks on the second pole, or all three on the third. We want the expected number of moves to reach either, starting from all-on-the-first.

Solving the hitting-time equations $E(\text{state}) = 1 + \text{average of } E$ over the next move, with $E = 0$ at the two winning states, gives $$\boxed{\tfrac{637}{9}} \approx 70.8 \text{ moves}.$$ That is ten times the optimal seven, because at almost every step the move that makes progress is outnumbered by moves that undo it. (Had the target been one specific pole rather than either, the wait would double, to $1274/9 \approx 141.6$.)

The computation

Let Cassius loose: from the current arrangement list the legal moves, pick one at random, and count moves until all three disks share a pole other than the start.

import numpy as np
rng = np.random.default_rng(0)
def random_solve(runs=500_000):
    total = 0
    for _ in range(runs):
        poles = [[3, 2, 1], [], []]            # pole 0 holds all disks, 1 on top
        moves = 0
        while poles[1] != [3, 2, 1] and poles[2] != [3, 2, 1]:
            legal = []
            for i in range(3):
                if not poles[i]:
                    continue
                d = poles[i][-1]
                for j in range(3):
                    if j != i and (not poles[j] or poles[j][-1] > d):
                        legal.append((i, j))
            i, j = legal[rng.integers(len(legal))]
            poles[j].append(poles[i].pop()); moves += 1
        total += moves
    return total / runs
print(random_solve())                          # ~70.8 = 637/9