Partition of a rectangle into smaller rectangles, with their diagonals forming a loop

Question

The Big and the Small Kingdom are both rectangular islands and divided into rectangular landscape. In each province there is a road that runs along one of the diagonals. On each island exist roads that make a closed route, which does not go through any point several times. The picture shows the Little Kingdom, which has six area:

The Great Kingdom has an odd number of landscapes. How many landscapes does the Great Kingdom have at least?

Answer 1

If one requires the route go through all provinces, then $9$ suffices (as shown by diagram below).

$\hspace1in$

Update

In fact, $9$ is the smallest odd number that does the job. The basic arguments go like this:

1. Consider the "four" rectangles covering the four corners of kingdom. They must be distinct from each other. Otherwise, there will be a rectangle that cover an edge of kingdom. Independent of which diagonal one pick, one of the endpoints of the diagonal will be in a position impossible to extend.

2. Over each edge, there can be rectangles between the corner rectangles. e.g. in the left edge of above diagram, there are two rectangles (magenta and green) between the red rectangle at top and olive-green rectangle at bottom. The key is in order for the route to be possible to extend, the number of such filling rectangles on each edge need to be even.

3. This means the total number of rectangles on the edges $N$ is an even number $\ge 4$.

4. $N$ cannot be $4$, Otherwise, the four corner rectangles are next to each other. There is only one way to pick the diagonals but that will lead to a closed route which one cannot add more diagonals.

5. Next, let us consider the case $N = 6$ and look at the diagonals of magenta and green rectangles in above diagram for inspiration. One will discover no matter how one place the $6$ rectangles on the edge, there is only one legal way to pick the $6$ diagonals. After you pick the diagonals, the two dangling endpoints are either lying on a horizontal or a vertical line. This means we need at least $3$ more edges (i.e 9 edges) to construct a closed route of odd length.

6. Finally, if $N \ge 8$, we need at least one more edge to construct a closed route of odd length. Once again, this means we need at least $9$ edges to do the job.

Combine $5.$ and $6.$ and the diagram above, we can conclude $9$ is the smallest odd number that one can construct a closed route of odd length.

Answer 2

Here a solution with $5$ regions :