A square is divided into N2 equal smaller non-overlapping squares, where N≥3. We are given a broken line which passes through the centres of all the smaller squares (such a broken line may intersect itself).[*] Show that it is possible to find a broken line composed of 4 segments for N=3.
[*] Find the minimum number of segments in this broken line for arbitrary N.
combinatoricsbroken linePAMO