Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3.
My only idea is to assume the opposite, make some needed arrangement, and to show that changing the arrangement won't change the divisibility. Not sure how to implement it though.
Instead of cutting up the board, I’ll tile it with dominoes. There are $3$ ways to tile a $2\times 3$ board. Say that a tiling of a $2n\times 3$ board is irreducible if it there is no $m\in\{1,\ldots,n-1\}$ such that the tiling can be split into a $2m\times 3$ tiling and a $2(n-m)\times 3$ tiling. It’s not hard to see that for each $n\ge 2$ there are exactly $2$ irreducible tilings of the $2n\times 3$ board: one has a row of horizontal tiles along the top with all of the other tiles vertical, and the other has a row of horizontal tiles along the bottom with all of the other tiles vertical.
Each composition of $n$ corresponds to one of the ways to divide the $2n\times 3$ board into smaller boards that are to be tiled irreducibly. If there are $k$ ones and $m$ larger integers in a composition of $n$, the composition gives rise to $3^k\cdot 2^m$ different tilings of the $2n\times 3$ board. If $k>0$ this is of course a multiple of $3$, so we’re interested in the compositions in which $k=0$, i.e., in which every part is at least $2$.
There are $\binom{n-1}{k-1}$ compositions of $n$ into $k$ parts; if each has to be at least $2$, we’re looking at unrestricted compositions of $n-k$ into $k$ parts, of which there are $\binom{n-k-1}{k-1}$. Each part can be tiled irreducibly in $2\equiv-1\pmod3$ ways, so modulo $3$ each composition contributes $(-1)^k$ to the total number of tilings. Altogether, then, the number of tilings of the $2n\times 3$ board is congruent modulo $3$ to
$$\begin{align*} t_n&\overset{\triangle}=\sum_k(-1)^k\binom{n-k-1}{k-1}\\\\ &=\sum_k(-1)^{k+1}\binom{n-2-k}k\\\\ &=\sum_k(-1)^{k+1}\left(\binom{n-3-k}k+\binom{n-3-k}{k-1}\right)\\\\ &=\sum_k(-1)^{k+1}\binom{n-3-k}k+\sum_k(-1)^{k+1}\binom{n-3-k}{k-1}\\\\ &=\sum_k(-1)^{k+1}\binom{n-3-k}k+\sum_k(-1)^k\binom{n-4-k}k\\\\ &=\sum_k(-1)^{k+1}\binom{n-3-k}k-\sum_k(-1)^{k+1}\binom{n-4-k}k\\\\ &=t_{n-1}-t_{n-2}\;. \end{align*}$$
It’s easy enough to check that $t_2=t_3=1$, and an easy induction then shows that
$$t_n\bmod3=\begin{cases} 0,&\text{if }n\equiv1\pmod6\text{ or }n\equiv4\pmod6\\ 1,&\text{if }n\equiv2\pmod6\text{ or }n\equiv5\pmod6\\ -1,&\text{if }n\equiv0\pmod6\text{ or }n\equiv3\pmod6\;. \end{cases}$$
In particular, $100\equiv4\pmod6$, so the number of tilings of the $200\times 3$ board is a multiple of $3$.