0
$\begingroup$

Use Math Induction to prove that any checkerboard with dimensions 2 x 3n can be completely covered by L-shaped trominoes for any integer n $\ge$ 1.

How do I go about proving a problem like this? I know the P(n) for this proof is the sentence "A checkerboard with dimensions 2 x 3n for any integer n $\ge$ 1. And I know P(1) is the basis, but how do I prove it fully? I honestly don't understand what we are trying to prove.

$\endgroup$
4
$\begingroup$

The problem is to prove that L shaped tronimos can always cover a board of size $2$ x $3n$ with induction. The first step, as you figured out, is the inductive base case, to show that L tronimos can cover a board of size $2$ x $3$.

enter image description here

This is the simplest solution for $n=1$.

The next step is to assume the problem is true for any large $N$, and then show how that implies it is true for $N+1$

enter image description here

Here we have a board of size $2$ x $3n$, marked blue to show that it is already covered in L tronimos. Then we consider the the board of size $2$ x $3(n+1)$, which is equivalent to $2$ x $3n + 3$, so like @Andre Nicolas said, you simply tack on another $2$ x $3$.

We now show it is possible to cover this new board with L tronimos.

enter image description here

That concludes the proof. It is always possible to cover a board of size $2$ x $3n$ with L tronimos.

$\endgroup$
1
$\begingroup$

Hint: Draw a picture. For the base case, you need to show that a $2\times 3$ can be so covered. It turns out that this is also all that is needed for the induction step.

In the induction step, note that a $2\times 3(n+1)$ checkerboard is just a $2\times 3n$ checkerboard, with a $2\times 3$ tacked on at the end.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.