Least possible number of squares with odd side length An $n\times(n+3)$ rectangular grid ($n>10$) is cut into some squares, with all cuts being along the grid lines. What is the least possible number of squares with odd side length?
[Source: Russian competition problem]

OLD AND SURELY WRONG INTERPRETATION OF THE PROBLEM
If I understood correctly the problem ask for the greater common odd divisor of $n$ and $n+3$. But the parity of $n$ and $n+3$ is different, because if $n$ is even and you add 3 then $n+3$ is odd, and viceversa.
So then the problem is reduced to search the GCD of $n$ and $n+3$. If GCD divides $n$ then
$$(GCD\mid n)\land (GCD\mid n+3)\implies GCD\mid 3\implies GCD(n,n+3)\in\{1,3\}$$
Then we have that the less number of squares (LNS) will be 


*

*if $3\mid n$ then $\mathrm {LNS}=\frac n3*(\frac n3+1)=\frac{n^2}{9}+\frac n3$

*if $3\not\mid n$ then $\mathrm {LNS}=n*(n+3)=n^2+3n$


Cause $n>10$ we will compare the minimum n divisible by 3 ($n=12$) and the absolute minimum $n=11$:


*

*$\mathrm {LNS}(11)=11*14=154$

*$\mathrm {LNS}(12)=4*5=20$


So the minimum number of squares for a rectangle $n\times(n+3)$ where $n>10$ are $20$, and it happen when $n=12$.

NEW BEAUTIFUL AND FRESH INTERPRETATION OF THE PROBLEM ;)
Maybe the interpretation of the question wasnt correct because I see the tag "combinatorics". At the light of this information the problem may ask by the way to cut the rectangle into pieces that are squares with odd length.
If, from my previous interpretation, we know that $GCD(n,n+3)\in\{1,3\}$ then we know that 


*

*we can cut the rectangle in a big square $3k\times 3k; 2\not\mid k$ plus somes $3\times 3$ or $1\times 1$ squares if $3\mid n$

*or we can cut the rectangle in a big square $n\times n$ if $2\not\mid n$ and somes $1\times 1$ squares if $3\not\mid n$

*or we can cut the rectangle in a big square $(n-1)\times(n-1)$ if $2\mid n$ and somes $1\times 1$ squares if $3\not\mid n$


It is obvious that the optimal solution is related to some n divisible by 3:


*

*for $n=12$ we can divide in a $11\times11$ square plus 4 $3\times3$ squares, plus $25$ $1\times1$ squares, being a total of 30 squares.

*for $n=13$ we can divide in a $13\times 13$ square plus 4 $3\times3$ squares plus 3 $1\times1$ squares, being a total of 8 squares
...


Analysis:


*

*if $2\mid n$ then you cant cut a square $n\times n$ because $n$ is even, so you will have a lot of tiny squares of $1\times 1$ to cover one line of, at least, length $n$, i.e, you will have at least $n+1$ squares.

*if $2\not\mid n$ and $3\not\mid n$ then $GCD(n,n+3)=1$, how I prove above, then you can cut a big square $n\times n$ because n is odd, and after cut the rest that is a rectangle $n\times4$ where, remember, $3\not\mid n$ so you will have some rest of little squares of $1\times1$, maybe 3 or 6 depending of $n \pmod 3$ plus a entire line of $n+1$. So you will had a minimum of $n+8$ squares.

*if $3\mid n$ and $2\not\mid n$ then you can cut a big square $n\times n$, because n is odd, plus somes $3\times 3$ squares because n and $n+3$ are divisible by 3. You will had here the optimal solution because there isnt squares of $1\times 1$. The minimum number of squares will be $4$ when $n=9$, but $n>10$ so the minimum will be $6$ squares.
So the solution of the problem will be the minimum n that are odd and divisible by 3. If $n>10$ this number is 15.
For $n=15$ we will have a big square of $15\times 15$ and 5 squares of $3\times 3$, being a total of 6 squares. Any other n cannot be cut in less number of squares with side of length odd.
P.S.: solutions with less or equal numbers of squares exist but for $n<10$.
