A square 2n×2n grid is given. Let us consider all possible paths along grid lines, going from the centre of the grid to the border, such that (1) no point of the grid is reached more than once, and (2) each of the squares homothetic to the grid having its centre at the grid centre is passed through only once.
(a) Prove that the number of all such paths is equal to 4∏i=2n(16i−9).
(b) Find the number of pairs of such paths that divide the grid into two congruent figures.
(c) How many quadruples of such paths are there that divide the grid into four congruent parts? combinatorics proposedcombinatorics