4
$\begingroup$

I am not sure how to get a closed-form formula for $R(3,n)$ as the recursion involves a summation. Maybe the best that can be achieved is a recursion that does not involve a summation having an upper index that increases with grid size. The WolframAlpha article considers a similar but not identical diagonal walk on a rectangular grid.

This is problem number five from the 2008 Canada National Olympiad:

A self-avoiding rook walk on a chessboard (a rectangular grid of unit squares) is a path traced by a sequence of moves parallel to an edge of the board from one unit square to another, such that each begins where the previous move ended and such that no move ever crosses a square that has previously been crossed, i.e., the rook’s path is non-self-intersecting.

Let $R(m, n)$ be the number of self-avoiding rook walks on an $m×n$ ($m$ rows, $n$ columns) chessboard which begin at the lower-left corner and end at the upper-left corner. For example, $R(m, 1) = 1$ for all natural numbers $m$; $R(2, 2) = 2$; $R(3, 2) = 4$; $R(3, 3) = 11$. Find a formula for $R(3, n)$ for each natural number $n$.


So far, I have deduced that:

  1. Once the rook moves to the top row, it will need to move left on the next move, and at least as far as the rightmost open square on an "open" block of, say $p$ squares $(p\ge2)$, in the second row. This is equivalent to the rook making a forced move to exactly $(3,p)$ then deciding where to move in a $2\times{p}$ rectangle, so is the rotated equivalent of the original problem for $R(p,2)$. (There may be multiple disjoint open blocks in the second row).
  2. Once the rook completes a move to the left in the second row, it will then need to move up to row 3, then proceed as per rule 1.

Sub-problem 1: finding $R(p,2)$

The path is completely determined by the $(p-1)$ choices of which rows (excluding the last, potentially including the first) on which to move from one side to another. So

$R(p,2) = 2^{p-1} \tag{1}$

This is also applicable if the rook starts out one square to the right (and the walk is between diagonally opposite corners).

Enumerating possible walks

Introduce the following further notation:

  • $W(3,q)$ : a complete walk for the $R(3,q)$ problem, $q < n$
  • $W(p,2)$ : a complete walk for the $R(p,2)$ problem, $p < n$
  • $U^i,D^i,L^i,R^i$ : move of $i$ squares in the up,down,left,right direction to be followed by a move in another direction ($i$ may be omitted if equal to $1$)
  • $R^{i+}, \dots$ : move of $i$ squares to the right,$\dots$ that can be followed by a move in $any$ direction (including a continuation in the same direction)

I have identified the following distinct walks:

  1. $U^2$ (trivial)
  2. $UR^xU$ followed by forced moves, $1 \le x \le n-1$
  3. $UR^xDR^{1+} \rightarrow W(3,n-x-1) \rightarrow\text{ forced},\:1 \le x \le n-2$
  4. $R^xU^2L^{1+} \rightarrow W(x,2),\:1 \le x \le n-1$
  5. $R^xUL^{1+} \rightarrow W(x,2),\:1 \le x \le n-1$
  6. $R^xUR^yU \rightarrow L^{y+1} \rightarrow W(x,2),\:x,y \ge 1,\:x+y \le n-1$
  7. $R^xUR^yDR^{1+} \rightarrow W(3,n-x-y-1) \rightarrow L^{y+2} \rightarrow W(x,2),\:x,y \ge 1,\:x+y \le n-2$

Of these the path count involves:

  • single summation for cases 2-5
  • double summation for cases 6,7
  • recursion in cases 3,7

For the contribution from case 7, I get:

$R_7(3,n) = \cases{\displaystyle\sum\limits_{x=1}^{n-3}\sum\limits_{y=1}^{n-x-2}{R(3,n-x-y-1)\cdot2^{x-1}}, n>3 \\ 0, \text{ otherwise}}$

This seems a bit too complicated; is there a neater way of classifying walks?

$\endgroup$
1
$\begingroup$

Here is a possible solution, with quite a different approach to counting walks to yours.

Let $\rho(3,k)$ be the set of self-avoiding rook walks using exactly the first $k$ columns. Then $$R(3,n) = \sum_{i = 1}^n |\rho(3,i)|$$ Now we attempt to split $\rho(3,k)$ in to disjoint subsets. (This is easier than in the original problem since we know that the $k$-th column gets occupied so there are fewer cases). Define:
$$\rho_1(3,k) := \{\mbox{paths in which square } (1,k) \mbox{ isn't used}\} \\ \rho_2(3,k) := \{\mbox{paths using both square } (1,k) \mbox{ and } (3,n)\} \\ \rho_3(3,k) := \{\mbox{paths in which square } (3,k) \mbox{ isn't used}\}$$ We note that since we have to enter and exit the $k$-th column we must use at least two squares in that column and in the case of $\rho_2$ we must use all three. This gives us that the above sets form a partition of $\rho(3,k)$. By symmetry $|\rho_1(3,k)| = |\rho_3(3,k)|$.
Now we need to think about constructing $\rho(3,k+1)$ from $\rho(3,k)$. We can do this by taking the entry square (or for paths in $\rho_2(3,k)$ the square $(2,k)$) from a given path in $\rho(3,k)$ to the $k$-th and changing this path to move through the $(k+1)$-th column, re-entering the $k$-th column in to the square from which the original path exited the $k$-th column. This gives us that (suppressing the 3s): $$|\rho_1(k+1)| = |\rho_1(k)| + |\rho_2(k)| \\ |\rho_2(k+1)| = |\rho_1(k)| + |\rho_2(k)| + |\rho_3(k)| \\ |\rho_3(k+1)| = |\rho_2(k)| + |\rho_3(k)|$$ but using the symmetry we noted earlier this reduces to: $$|\rho_1(k+1)| = |\rho_1(k)| + |\rho_2(k)| \\ |\rho_2(k+1)| = 2|\rho_1(k)| + |\rho_2(k)|$$ Which gives us (for $k > 1$): $$ |\rho_1(k+1)| = |\rho_1(k)| + 2|\rho_1(k-1)| + |\rho_2(k-1)| = 2|\rho_1(k)| + |\rho_1(k-1)|$$ and similarly $$|\rho_2(k+1)| = 2|\rho_2(k)| + |\rho_2(k-1)|$$ These are linear difference equations so we only need some initial cases to determine constants and we will have formulae for $|\rho_1|$ and $|\rho_2|$. But it is easy to see $|\rho_1(1)| = 0$ and $|\rho_2(1)| = 1$. This gives us the following solutions: $$|\rho_1(k)| = \frac{1}{2 \sqrt{2}}(1+\sqrt{2})^{k-1} - \frac{1}{2 \sqrt{2}}(1-\sqrt{2})^{k-1} \\ |\rho_2(k)| = \frac{1}{2}(1+\sqrt{2})^{k-1} + \frac{1}{2}(1 - \sqrt{2})^{k-1}$$ Finally $$R(3,n) = \sum_{i = 1}^n |\rho(3,i)| = \sum_{i=1}^n |\rho_2(3,i)| + 2 \sum_{i=1}^n |\rho_1(3,i)|$$ But these are geometric series and so we can sum them to get: $$R(3,n) = \bigg(\frac{1}{2} + \frac{1}{\sqrt{2}}\bigg) \bigg ( \frac{(1 + \sqrt{2})^n - 1}{\sqrt{2}} \bigg ) - \bigg ( \frac{1}{2} - \frac{1}{\sqrt{2}} \bigg ) \bigg ( \frac{(1 - \sqrt{2})^n - 1}{\sqrt{2}} \bigg ) $$ $$ = \bigg ( \frac{1}{2 \sqrt{2}}\bigg )((1 + \sqrt{2})^{n+1} - (1- \sqrt{2})^{n+1}) - 1$$

$\endgroup$
  • $\begingroup$ The method looks great! The second-last line also looks correct, but the last line is not (the integral parts of the powers of $1+sqrt2,1-sqrt2$ cannot cancel unless the exponents are the same. Will do just a bit more checking before I accept ... $\endgroup$ – Marconius Aug 6 '15 at 20:04
  • $\begingroup$ @Marconius whoops, the powers are meant to be the same. Obviously got a bit lax at the end of typing it up. Will correct that now. $\endgroup$ – Rhys Steele Aug 6 '15 at 20:06
2
$\begingroup$

Let $A(n),B(n),C(n),D(n)$ be the set of $3\times n$ walks that in the last column look like these images, respectively:

enter image description here

Let $a(n)=|A(n)|$, $b(n)=|B(n)|$, $c(n)=|C(n)|$, $d(n)=|D(n)|$. Clearly, $a(n)=R(3,n-1)$, by symmetry $b(n)=c(n)$, and as no other configuration is valid, $R(3,n)=a(n)+b(n)+c(n)+d(n)=R(3,n-1)+2b(n)+d(n)$.

We can extend any $B(n-1)$-walk or $D(n-1)$-walk to a $B(n)$-walk, and we can extend a $B(n-1)$, $C(n-1)$, or $D(n-1)$-walk to a $D(n)$-walk, each in a unique way, and vice versa by "short-cutting" the last column as in the following image:

enter image description here

In other words, we have a bijection $B(n-1)\cup D(n-1)\leftrightarrow B(n)$ and a bijection $B(n-1)\cup C(n-1)\cup D(n-1)\leftrightarrow D(n)$. This gives us the recursions $$ b(n)=b(n-1)+d(n-1),\qquad d(n)=d(n-1)+2b(n-1)$$ whence $$ 2b(n-1)=d(n)-d(n-1)=(b(n+1)-b(n))-(b(n)-b(n-1))$$ and so $$ b(n+1)=2b(n)+b(n-1).$$ We conclude that $b(n)$ is a linear combination of $\lambda_1^n$ and $\lambda_2^n$, where $\lambda_{1,2}$ are the solutions of $X^2=2X+1$, i.e., $\lambda_{1,2}=1\pm\sqrt 2$. Then $d(n)$ is also such a linear combination, and up to a constant so is $R(3,n)$. We conclude $$R(3,n)=\alpha(1+\sqrt 2)^n+\beta(1-\sqrt 2)^n+\gamma $$ where $\alpha,\beta,\gamma$ can be obtained from $$\begin{align}1=R(3,1)&=\alpha(1+\hphantom{1}\sqrt 2)+\beta(1-\hphantom{1}\sqrt 2)+\gamma\\ 4 = R(3,2)&=\alpha(3+2\sqrt 2)+\beta(3-2\sqrt 2)+\gamma\\ 11=R(3,3)&=\alpha(7+5\sqrt 2)+\beta(7-5\sqrt 2)+\gamma\end{align}$$ One finds straighforwardly (or at least verifies) that $\alpha = \frac{2+\sqrt 2}4$, $\beta =\frac{2-\sqrt 2}4 $, $\gamma = -1$. In summary, $$ R(3,n)= \frac{2+\sqrt 2}4(1+\sqrt 2)^n +\frac{2-\sqrt 2}4(1-\sqrt 2)^n-1.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.