MathDB

Let

S=\{(a,b)|a=1,2,\dots,n,b=1,2,3\}

. A rook tour of

S

is a polygonal path made up of line segments connecting points

p_1,p_2,\dots,p_{3n}

is sequence such that (i)

p_i\in S,

(ii)

p_i

and

p_{i+1}

are a unit distance apart, for

1\le i<3n,

(iii) for each

p\in S

there is a unique

i

such that

p_i=p.

How many rook tours are there that begin at

(1,1)

and end at

(n,1)?

(The official statement includes a picture depicting an example of a rook tour for

n=5.

This example consists of line segments with vertices at which there is a change of direction at the following points, in order:

(1,1),(2,1),(2,2),(1,2), (1,3),(3,3),(3,1),(4,1), (4,3),(5,3),(5,1).

)

A2