IBM Ponder This #302 · June 2023

A super intelligent mouse is placed in a three dimensional "maze", consisting of a $k\times k\times k$ grid, where the mouse is placed at the beginning at $(1,1,1)$ at time $t=1$.

Every cell in the maze contains one unit of cheese. The catch: This is temporal cheese; it's phasing in and out, and is present only at certain times. If the mouse is at cell $(a,b,c)$ at time $t$ where the cheese is present in the cell, the mouse collects it. Afterwards, the cheese no longer appears in that cell!

At each time unit, the mouse can either stay in place, or move one step in exactly one direction. The maze has walls allowing only movement right, up, and forward on the X, Y, and Z axes, respectively. For example, if present at $(3,5,1)$ at $t=13$, the possible locations for the mouse at $t=14$ are

1. $(3,5,1)$ (waiting in place)
2. $(4,5,1)$ (moving right in the X axis)
3. $(3,6,1)$ (moving up in the Y axis)
4. $(3,5,2)$ (moving forward in the Z axis)

We denote the path taken by the mouse by a sequence of letters: 'W', 'R', 'U', and 'F', corresponding to options 1-4 above.

At time $n$, the mouse is removed from the maze and can no longer collect cheese. His goal: To maximize the cheese collected by then.

The phases of the cheese are determined by the following linear congruential generator:

$f(x)=(ax+c)modm$

Where

a = $1103515245$
c = $12345$
m = $2^{31}$

The cheese is present at $(a,b,c)$ at time $t$ if and only if there is a value $0\le x<n/2$ such that $t=f(a\cdot b\cdot c+x)modn$.

For example, when $n=20$ and $(a,b,c)=(3,5,1)$, the set of values of $t$ where the cheese appears is $\{1,3,4,5,6,7,8,9,10,12\}$.

For $k=5$ and $n=20$, the maximum amount of cheese obtainable is 10 units, given by the following path:
FFRFWFWRRRUUUWWWUWW

Your goal: Find the maximum amount of cheese obtainable for $k=30$ and $n=100$. Supply your solution as two lines, one with the maximum number of cheese units and the other with the path itself.

A bonus "*" will be given for solving the same problem for $k=50$ and $n=200$, but this time allowing the mouse to move in more possible ways: left (L), down (D) and backwards (B) as well as wait (W), right (R), up (U) and forward (F), and allowing the mouse to collect the cheese more than once for the same cell, at each time where the cheese is present there.

Solution

Best opened after a real attempt

To be added.