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