Tiling a $3$ by $n$ rectangle "We are looking to tile a rectangle with dimensions $3$ down and $n$ across, using only $3$ by $1$ rectangles. Prove the number of horizontal rectangles is a multiple of $3$"
I'm probably being stupid, but I can't see a way to rigorously prove this. Surely its as simple as that if we have one horizontal rectangle somewhere in our tiling, then there must be $2$ other rectangles in the same "column" as it, as otherwise there would be some area of the $3\times n$ rectangle not covered.
Am I missing something?
 A: It can be proved using induction. Let $H_n$ be the number of horizontal block in $3$X$N$ Grid.
Clearly $H_1 = 0$. So $H_1$ is multiple of 3.
Now let's suppose $H_k$ is a multiple of 3 for all $k<k_0$ .
i.e. $H_k = 3m$ where $k \leq k_0 $ & $m \geq 0$.
Now for $H_{k_0+1}$ there are 2 ways to place the last tile , vertical or horizontal.
Case 1 :If we place the tile vertical then $H_{k_0 + 1} = H_{k_0} = 3m$ which proves our claim.

Case 2: If we place at last a horizontal tile then we also have to place 2 more horizontal tiles(we have no other choice). In which case we have

$$H_{k_0+1} = H_{k_0 - 2} + 3$$. Since $H_{k_0-2} = 3m$ for some m.
$$H_{k_0+1} = 3m + 3$$
$$H_{k_0+1} = 3(m+1)$$
Which is again a multiple of 3. So by induction it is true for all n.
EDIT : We also need to include $H_2 = 0$ and $H_3 = ( 0 $ or $3)$ as our base cases.
A: Let $V$ be the number of vertical tiles, and $H$ the number of horizontal tiles.
Each vertical tile lies in all three rows, so the number of horizontal tiles in each row is given by $H' = (N - V)/3$, which must of course be an integer** and is the same for each row. The total number of horizontal tiles is given by $H = 3H'$, and so $H$ is divisible by 3. 
** This then also implies $N \equiv V \pmod{3}$.

We can generalize the result for $3M \times N$ rectangles:
We color the rectangle so that cells in the first row are red, in the second row green, in the third row blue, and repeat the pattern.
Let $H_R$, $H_G$, $H_B$ be the number of red, green, blue horizontal tiles respectively. Notice that vertical tiles cover each color once. 


*

*The number of red cells is given by $MN = 3H_R + V$. 

*The number of green cells is given by $MN = 3H_G + V$. 

*The number of blue cells is given by $MN = 3H_B + V$.


From this we can $H_R$, $H_G$ and $H_B$ are all equal and given by
$H_R = H_G = H_B = (MN - V)/3$, and this must be an integer.
The total number of horizontal tiles must be $H = 3H_R$, which means $H$ is divisible by 3.
As before, an additional constraint is $MN \equiv V \pmod{3}$.
