Bottom of rectangular box (which is obviously a rectangle) is covered by $2*2$ and $1*4$ tiles. Tiles were removed out of the box and shuffled. One $2*2$ tile was lost. We replaced it with $1*4$ tile.
Can we cover the rectangle now with this new set of tiles?
I apparently don't know what steps should I take in order to solve that problem. Will appreciate unusual methods as when I am able, always try something original.
The question yells for us to prove that it is impossible. If we want to do that, usually we want some kind of invariant. In this case colouring works. Now what colouring will give invariant shifting of the $1 \times 4$ rectangular pieces? $4$ colours of course, each diagonal being the same colour, cycling through the diagonals. Each rectangular piece covers exactly one cell of each colour. Each $2 \times 2$ square piece, on the other hand, covers $1,2,1,0$ cells respectively of the $4$ colours in a cyclic order. So clearly replacing a square piece by a rectangular piece will not work. To simplify the number of cases to check, notice that the intrinsic structure is modulo two, and we can see that we can restrict to two colours, the first two diagonals black, the next two white, the next two black again, which is same as before but with pairs of colours identified. Now each rectangular piece covers $2$ of each colour and each square piece covers $3$ of one colour but $1$ of the other. It is then obvious that you cannot have different parity of each type of piece.
Consider the two tilings. In one tiling, there is and odd number of $4 \times 1$ tiles. In the other tiling, there is an even number of these tiles. Now consider the odd case. All $4 \times 1$ tiles are oriented either vertically or horizontally. The number of tiles oriented in one of these directions must be odd. Let's assume, WLOG, that the number of vertically oriented tiles is odd.
Now we can show that the breadth $b$ of the rectangle is odd (1). To see why, assume it is even towards a contradiction. Then consider every row of the rectangle. The number of intersections with a vertical tile must be even, as in the picture below, because the rest of the tiles are $2 \times 2$. Stepping through the rows from top to bottom, we notice that we always must introduce an even number of new vertical tiles. So the total number would have to be even, contradicting our assumption.
Now that we know $b$ is odd, we can show that $l$ divides $4$. To see why, consider the number of vertical tiles starting/ending at a certain row. By ending what is meant is the number of tiles that were in the previous row but not in this one. There must be an odd number of tiles starting at row $1$, and ending at row $5$. So there must be an even number starting at all rows $2, 3, 4$. So there must be an odd number of tiles starting at row $5$. Following this pattern, we see that $l$ must divide $4$. (2). We can strengthen this, by noticing that if $l = 4k$, $k$ must itself be odd. Otherwise the number of vertically stacked tiles would be even, contradicting our assumption. (2.1)
Now, consider the $4 \times 1$ tiles in the other tiling. These are even in number. So either there are an even number oriented vertically and oriented horizontally, or both are odd. The case of both odd causes a contradiction: by similar reasoning to (1), we get that the length must then be odd, which contradicts (2).
So we are now forced to accept that it is possible to tile the rectangle with an even number $V$ of vertically stacked tiles. Now, recall from (2) that the number of tiles starting at rows $1, 5, 9, \dots$ is odd, and the number of tiles starting at the other rows is even. Now, because $V$ is the sum over all rows of the number of tiles starting at that row, and $V$ must be even, then we can see $l$ must in fact divide $8$. This contradicts (2.1), proving the impossibility of the result.
