all possible broken lines constructed on grid plane
Source: Tournament of Towns, Senior A-Level , Spring 2019 p7
May 13, 2020
combinatoricsphi functionKvant
Problem Statement
On the grid plane all possible broken lines with the following properties are constructed:
each of them starts at the point , 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 different ways, is equal to the number of positive integers that are less than n and relatively prime to .(Ilke Chanakchi, Ralf Schiffler)