# What's the largest square you can make with given tiles of a form?

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

## 1 Answer

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 :)