Problem

Source: 2019 Pan-African Mathematics Olympiad, Problem 5

Tags: combinatorics, broken line, PAMO



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$.