PAMO 2019 Problem 5

A square is divided into $N^2$ equal smaller non-overlapping squares, where $N \geq 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$ .