Friday, October 25, 2019

Shortest Walk to get Stuck in nth Dimension

Consider a walk in $\mathbb{Z}^n$ with the following constraints:

1) At each step you may only step $1$ unit in the positive or negative direction of each orthogonal basis vector of $\mathbb{Z}^n$.

2) You may not visit the same position more than once.

What is the fewest number of steps you must take to get "stuck," or in other words, so that all positions $1$ step away have already been visited, leaving you with $0$ possible moves which follow the above constraints.

Claim:
The minimum number of steps needed to get stuck in $\mathbb{Z}^n$ is given by

$4n - 1$

for all $n \ge 2\in\mathbb{N}$

Proof:
Let $x_1, x_2, x_3, \ldots , x_n$ be the $n$ unit orthogonal basis vectors of $\mathbb{Z}^n$. Let $v_1 = \pm x_a$ and $v_2 = \pm x_b$ for all $a, b$ such that $1 \le a \ne b \le n$.



$v_1$ can reach $v_2$ in $2$ steps and no fewer. Each step can be seen as adding one of these basis vectors (muliplied by $\pm 1$) to the "current position." Then if $v_1$ is the current position, then the first step is to add $v_2$, putting the current position at $v_1 + v_2$. The second step is to add $-v_1$, putting the current position at $v_2$.

We will start the walk at $x_1$. Using the method just described, we will move from

$x_1$ to $x_1 + x_2$ to $x_2$ to $\ldots$ to $x_n$ to $x_n - x_1$ to $-x_1$ to $\ldots$ to $-x_n$.

Each one of the vectors we visit and each intermediary step is unique and not equal to the zero vector. There are $2n$ different positions that we will visit, not including the origin. Then there are $2n - 1$ jumps between them, eaching costing $2$ steps, putting the total number of steps at $2(2n-1) = 4n-2$ steps.

Lastly, we step to the origin, putting the total number of steps at $4n-1$. We have already visited all $2n$ positions reachable from the origin using the minimal number of steps possible, and have no more possible steps to take. Therefore, the minimal number of steps to get stuck in $\mathbb{Z}^n$ is $4n-1$.

No comments:

Post a Comment