C2) Let $n$ be a strictly positive integer. Roger has a rectangular garden of dimensions $(2 n+1) \times(2 n+1)$, and he places barriers to divide his garden into several rectangular cells. Once completed, he will have thus formed exactly two horizontal rectangles $k \times 1$ and two vertical rectangles $1 \times k$ for each even integer $k$ between 1 and $2 n+1$, as well as a single $1 \times 1$ square. How many ways can Roger do this?
## Solution :

Consider the 4 largest plots that Roger will delineate. Let's prove that they will form the garden's border.

If we consider a vertical plot $1 \times 2k$, we notice that one of its short sides (horizontal) must touch the edge of the garden, otherwise there would be a space of height strictly less than 1 above or below the plot, which cannot belong to any of the other plots.

You can also see that one of its long sides (vertical) touches the edge of the garden. If this were not the case, there would be spaces of length less than $2n$ to the left and right of this plot, and the two large horizontal plots would have to be placed in the remaining $(2n+1) \times 1$ rectangle above or below. This is clearly impossible, as $2n + 2n > 2n + 1$.

It has therefore been proven that a plot of $1 \times 2k$ must have a vertical and a horizontal border, and therefore a garden border; the same is true for a plot of $2k \times 1$. We have one plot per corner, and it is simple to see that there are only two possible configurations:
![](https://cdn.mathpix.com/cropped/2024_04_28_5d50c375e30aaac9179ag-13.jpg?height=414&width=1010&top_left_y=1278&top_left_x=568)

After removing these 4 plots, we are left with a square $(2n-1) \times (2n-1)$ in the middle, which must be subdivided exactly as in the problem statement (with $n-1$ instead of $n$). By iterating the same argument, we should get the answer of $2^n$. We prove this rigorously using induction.

Induction Hypothesis: There are exactly $2^k$ ways to divide the garden $(2k+1) \times (2k+1)$. Base Case: For $n=1$, we have the $2=2^1$ ways described above for the garden border. We are then left with the $1 \times 1$ square, which completes the base case. Induction Step: By the reasoning above, we first choose one of the two possibilities for the border of the $(2n+1) \times (2n+1)$ garden, and we are left with a $(2n-1) \times (2n-1)$ garden, which can be divided in $2^{n-1}$ different ways by the induction hypothesis for $k=n-1$. Since we can combine each of the border possibilities with each of the possibilities for the inner garden, we have a total of $2 \cdot 2^{n-1} = 2^n$ ways to do it.

We have thus proven that $2^n$ is the desired answer.