You are given a N x M rectangle. The question is - what is the maximum number of 2x1 tiles that you can fit inside.
The tiles can be rotated, the can touch the edges of the grid, but they cannot overlap and they must not intersect (no common corners too), meaning in a 3x3 grid you can only fit 2 tiles.
I have made an algorithm but now am wondering if there's a more elegant mathematical formula.
Thank you
I don't have a formula for you, but I do have a way to rephrase the question to make it appear to have less arbitrary rules:
Take your $n \times m$ grid, and convert it to an $(n+1) \times (m + 1)$ grid. Now try to fill it with "fat tiles", where each "fat tile" is $3 \times 2$, and consists of a $2 \times 1$ tile surrounded by a size $1/2$ 'buffer' all the way around it.
For this problem, the word "fill" has the more ordinary meaning: tiles can touch along their boundaries.
A crude estimate of the max is given by computing ratios of areas: $$ t_{max} \le \lfloor \frac{(n+1)(m+1)}{3 \times 2} \rfloor $$
In the $n = m = 3$ case you cited, this crude estimate gives $$ t_{max} \le \lfloor \frac{(4)(4)}{3 \times 2} \rfloor = \lfloor \frac{16}{6} \rfloor = 2 $$ so it's not so horrible an estimator. In general, I expect it to be off by no more than one or two.
For solving the problem in my revised form, there's a kind of natural induction: you can solve the $(p, q)$ problem if $q$ is even and $p$ is greater than $3$ by solving the $(p-3, q)$ problem, and then covering the $3$-unit-tall strip you removed with a long stretch of $3 \times 2$ tiles (namely $q/2$) of them. The other cases -- particularly when $q$ is odd -- are likely to be messier, and I'm not gonna slog through them because...this kind of problem doesn't interest me much. :(