Least possible number of squares with odd side length

Question

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]

Answer 1

Denote by $f(n)$ the minimal number of odd-sized squares in a decomposition of a $n\times (n+3)$ square. Then (as was guessed by @Willemien in his answer) we have $f(n)=g(n)$ where $g(n)=4$ when $n$ is of the form $4q$ or $4q+1$, and $g(n)=2$ when $n$ is of the form $4q+2$ or $4q+3$.

First, if $r$ is the number of odd-sized squares in any decomposition of a $n\times (n+3)$ square, counting the unit squares and working modulo $4$, we see that $n(n+3)\equiv r \ ({\textsf{mod}} \ 4)$. Also, $r$ cannot be zero because one of $n$ or $n+3$ is odd. It follows that $r\geq g(n)$ for any decomposition, and hence $f(n)\geq g(n)$.

The converse inequality $f(n)\leq g(n)$ has already been shown in @Willemien's answer. Below is a picture summarizing his argument (with even-sized rectangles in green and odd-sized squares in red ):

Answer 2

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

Answer 3

Thanking Steve Kas for his drawings

It looks it can always be done with 2 or 4 (odd-sided) squares

I think you need 4 "odd"squares if n or n+3 is divisible trough 4 otherwise it is 2.

First of all you can fill even-by-even rectangles with even squares only.

If n or n+3 is not divisible by 4, 2 odd similar sized squares will leave an even-by-even rectangle so you only need 2 odd-sided squares

if n or n+3 is divisible by 4 you are left with a 2-by-odd and a even-by-even rectangle.

and you need two extra odd-sided squares to chance the 2-by-odd rectangle to an even-by-even rectangle , so a total of 4 odd-sided squares

Thanks to Steve for the drawings