3
$\begingroup$

Given $M$ tiles of size $1 \times 1$ and $N$ tiles of size $2 \times 2$, what's the side-length of the largest square I can make (the square must be completely filled in the middle)?

I think I can come up with a recurrence. If we're at a state $(m, n, k)$ with $m$ tiles of the first form, $n$ tiles of the second form, and side-length $k$, we can transition to state $k + 1$ by using some number of $1 \times 1$ or state $k + 2$ by using some number of $2 \times 2$ squares. However, this is clearly not exhaustive because it doesn't account for the case in which we use both.

I'm thinking there might be a way to get a closed formula (rather than a dynamic programming recurrence), and I was wondering if someone might know a good approach to this problem

$\endgroup$
2
$\begingroup$

If the biggest square that we can make with m,n has an even lentgh, we have that the biggest square that we can make is the nearest one, i.e: if we have $k' \in \mathbb{N}$ s.t $(2k')^2 \leq m + 4n < (2(k'+1))^2$ then the side length of the square is 2k'. We can construct the square by putting all the tiles of second form in (the square has an area that is a multiple of four, so we can juxtapose this kind of tiles). And if it's not sufficient, we put a maximum of tiles of the first form.

For example, if $n = 11$ and $m = 13$. We have $m + 4n = 13 + 4 \times 11 = 57$, and $6^2 < 57 < 8^2$. And we can actually fill a $6\times6$ square with a number of nine $9$ ($2\times 2$) tiles. But if we had $m = 13$ and $n = 8$: $m + 4n = 13 + 4 \times 8 = 45$. We have $6^2 < 45 < 8^2$ so we can fill the $6\times 6$ square with $8$ ($2\times 2$)tiles and $4$ ($1\times 1$) tiles (for example, by putting them in a corner of the square). We did not use $9$($1\times 1$) tiles.

Now if the square has a side-length of the form $2k' + 1$ it's more complicated. Actually we can only put a maximum of $k'^2$ tiles of the second form in it, because if we juxtapose them from a corner there'll be always a line on two-edges (in the opposite corner) that is too thin. We can convince ourselves that moving theses tiles doesn't change anything, it will either reduce the number of $(2\times 2)$ that we can put or this will not change (I don't have a rigourous proof about that but it's intuitive, I think we should do some drawings to see this).

So we have to consider an inequality. The number of missing-tiles in this line is $(2k'+1)^2 - (2k')^2 = 4k' + 1$. And actually this is the minimum number of $(1\times1)$ tiles (m) required. So if we have $(2k'+1)^2 \leq m + 4n < (2k' + 2)^2$, then we must verifiy if $m \geq 4k' + 1$. If it is (by a similar reasonning), we can construct the square. If it's not, then we can only construct a square of side length 2k'.

The final answer should then be: find $k \in \mathbb{N}$ s.t $k^2 \leq m+4n < (k+1)^2$. If $k$ is even, then the biggest square that we can make has a side-length of $k$. If $k$ is odd, then if $m \geq 2k + 1$, we can also make a square with a side-length of $k$. Else, we can only make one with a side-length of $(k-1)$.

I hope I answered your question, if not tell me :)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy