I have an interesting lemma, and the problem is it's direct consequence, but I am not sure whether it's true. Let rows be numbered $0, 1...m-1$ from bottom. Then we have that for every $k $ the number of upward dominoes which hve their bottom tile in $k $th row, plus the number of missed cells below and in $k $th row is al least $k $.

aleksam wrote: I have an interesting lemma, and the problem is it's direct consequence, but I am not sure whether it's true. Let rows be numbered $0, 1...m-1$ from bottom. Then we have that for every $k $ the number of upward dominoes which hve their bottom tile in $k $th row, plus the number of missed cells below and in $k $th row is al least $k $. I used the same Lemma in an inductive form which eventually leads to a solution. Will fill in the bunch of nifty details later. A very nice and hard problem!

anantmudgal09 wrote: Will fill in the bunch of nifty details later. Since there have passed more than 2 years, can you please add the details now?

Solved with Alan Bu, Alex Zhao, Daniel Yuan, Edward Yu, Elliott Liu, Isaac Zhu, Jeffrey Chen, Kevin Wu, and Ryan Yang. The answer is \(mn-\lfloor m/2\rfloor\), achieved by a brick wall tiling. Now we prove this is optimal. Call a domino greenish if it is one of the dominos shown in the following picture: [asy][asy] size(7cm); defaultpen(fontsize(10pt)); real t=0.1; void f(real x, real y) { filldraw( (x+t,y+t)--(x+2-t,y+t)--(x+2-t,y+1-t)--(x+t,y+1-t)--cycle, green+white+white+white, heavygreen); } f(0,0); f(2,0); f(4,0); f(6,0); f(8,0); f(1,1); f(3,1); f(5,1); f(7,1); f(2,2); f(4,2); f(6,2); f(3,3); f(5,3); f(4,4); draw( (0,0)--(10,0)--(10,5)--(0,5)--cycle); for (int i=1;i<=9;i+=1) draw( (i,0)--(i,5),gray); for (int i=1;i<=4;i+=1) draw( (0,i)--(10,i),gray); [/asy][/asy] Claim: There is a maximal tiling containing all of these dominos. Proof. Consider the maximal tiling with the most greenish dominos, and assume this tiling omits some greenish domino. Take the lowest greenish domino \(\mathcal D\) that does not exist, and consider the two greenish dominos \(\mathcal D_1\) and \(\mathcal D_2\) below it. By maximality, we are not allowed to add the domino \(\mathcal D\) to the tiling. If there is a domino in this tiling directly above \(\mathcal D\), move it down one cell to \(\mathcal D\). Otherwise exactly one of the two cells of \(\mathcal D\) is covered by a vertical domino, so we can delete that domino and replace it with \(\mathcal D\). This contradicts maximality of the number of greenish dominos. the end. \(\blacksquare\) Now take the maximal tiling containing all greenish dominos. By a standard checkerboard coloring argument, at least \(\lfloor m/2\rfloor\) cells in the top-left right triangle are not covered by a domino, and at least \(\lfloor m/2\rfloor\) cells in the top-right triangle are not covered by a domino. Thus at least \(2\lfloor m/2\rfloor\) cells are not covered, the end.

Solved with Gabrupro, AdhityaMV We claim the answer is $mn - \left \lfloor \frac{m}{2} \right \rfloor$, which can be achieved by many constructions, one of them being to have $n$ horizontal dominoes on odd rows (numbering starting from $1$), and $n-1$ dominoes on the even rows. Consider the configuration with the maximal number of horizontal dominoes and if multiple such configurations are possible, pick one such that the horizontal dominoes are on as low rows as possible. Claim: If a row has $k$ consecutive horizontal dominoes, the row above it must have $k-1$ consecutive horizontal dominoes just above these. Proof: Suppose we need to show that the squares $(x,y)$ and $(x,y+1)$ are covered with a domino. If both of these squares are occupied, then we could add a domino here, a contradiction, unless both $(x+1,y)$ and $(x+1,y+1)$ are covered by a domino, in which case we can move it down. Note that both of them cannot be covered unless by the same domino due to condition (iii), so suppose one of them is covered, wlog $(x,y)$. Since it cannot be horizontal, the domino must be $(x,y), (x+1,y)$, in which case we can replace it with the claimed domino and this increases the number of horizontal dominoes, a contradiction again since the configuration picked was to have minimal number of these. So, we must indeed have $k-1$ consecutive dominoes above the current row. $\square$ So, by induction we must have that, building upon the bottom row of $n$ consecutive dominoes (since $n \ge m$), that the only squares left are the ones covered in a "staircase" structure of size $m-1$ on both sides. But now, do a chessboard coloring on each of these, to see that in each of them, at least $\left \lfloor \frac{m}{2} \right \rfloor$ squares must be left empty on either side, so the desired bound follows. $\blacksquare$

teenager forgets how to use local. hard problem. The answer is $mn-\lfloor m/2\rfloor$, achieved by putting dominoes horizontally in the obvious way. It suffices to show that there must be at least $2\lfloor m/2\rfloor$ uncovered squares. For the bound, rotate the board $45^\circ$ clockwise and replace each square with the square formed by its midpoints. We interpret dominoes as $2 \times 2$ squares, which cannot overlap by the conditions given (this employs condition (iii)). Thus we want to tile the following shape (only the parts with colored cells) with $2 \times 2$ squares covering a maximal number of black squares. The red outlines denote the bottom row, which is filled with dominoes, and the red squares denote cells that clearly can't be covered by a square and can thus be ignored. Thus we want to show that in any tile of the following shape we have at last $2\lfloor m/2\rfloor$ uncovered squares. Here I've made things bigger to better illustrate generality. We "checkerboard color" the formerly gray squares as above. Now note that each $2 \times 2$ square will contain exactly $2$ black squares and $1$ blue square. Consider the following purple "rows" (on the top) and "columns" (on the right)—keeping the original blue coloring underneath: It is clear that within each row/column at least one purple/blue cell isn't covered by a $2 \times 2$ square. Now a simple induction gives the number of such purple rows/columns as $2\lfloor (m-1)/2\rfloor$ (here we use $m \leq n$: if $m>n$ then these rows and columns can "collide" and our bound is messed up), and that there are $\tfrac{m-1}{2}(2n+1)$ blue tiles (post-deletion) if $m$ is odd and $\tfrac{m-2}{2}(2n+1)+(n-1)$ if $m$ is even. On the other hand, we have $2n(m-1)$ black squares in total, so when $m$ is odd at least $$2n(m-1)-(m-1)(2n+1)+4(m-1)/2=m-1=2\lfloor m/2\rfloor$$black squares are uncovered, and when $m$ is even at least $$2n(m-1)-(m-2)(2n+1)-2(n-1)+4(m-2)/2=m=2\lfloor m/2\rfloor$$black squares are uncovered. This finishes the problem. $\blacksquare$