11th CanMO 1979 Problem 5 The lattice is the set of points (x, y) in the plane with at least one coordinate integral. Let f(n) be the number of walks of n steps along the lattice starting at the origin. Each step is of unit length from one intersection point to another. We only count walks which do not visit any point more than once. Find f(n) for n =1, 2, 3, 4 and show that 2 n < f(n) ≤ 4·3 n-1 .
f(1) = 4 (any of 4 directions), f(2) = 12 (any of 3 directions for step 2), f(3) = 36 (any of 3 directions for step 3), f(4) = 100 (any of 3 for step 4, except for the 8 paths after step 3 which go around 3 sides of a square - only 2 possible directions for each of those). You cannot go back the way you came, so for steps 2 to n there is a choice of at most 3 directions. Hence f(n)  2 n . 11th CanMO 1979 © John Scholes jscholes@kalva.demon.co.uk 10 June 2002