On the grid plane all possible broken lines with the following properties are constructed:
each of them starts at the point (0,0), has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding worm, the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles 2\times 1 and 1\times 2) in exactly n>2 different ways, is equal to the number of positive integers that are less than n and relatively prime to n.(Ilke Chanakchi, Ralf Schiffler)
combinatoricsphi functionKvant