The following puzzles are two classics about checkerboards and dominoes. The problems are useful in that they introduce several ideas that can be used to approach similar puzzles, and furthermore they can be used to explain the value of logical proof over brute-force proof in a mathematical context, and to compare and contrast inductive and deductive reasoning.
Both problems will be presented, followed by their solutions.
Checkerboard problem 1
If we have a standard checkerboard, we have an 8x8 array of alternating red and white squares. Now, let's say we have a bunch of dominoes, and we idle our time by placing the dominoes on the checkerboard in the following way:
(The basic idea behind these rules is that we are tiling the checkerboard with dominoes--the problems are not about placing the dominoes in some "tricky" fashion that just barely falls within the conditions of the rules.)
Given these rules, we quickly see that it takes 32 dominoes to cover the 64 checkerboard squares, since each domino covers two squares.
Now (and here is where the puzzle begins), let's say some miscreant comes along and cuts off two of the diagonally opposite corner squares of our checkerboard, say, the upper right and lower left squares. (We can emulate this on an actual checkerboard by placing two checkers on these squares to indicate that they are unavailable.) There are only 62 squares left... can we now cover the board with exactly 31 dominoes?
If so, demonstrate an arrangement that works. If not, prove that it cannot be done.
Checkerboard problem 2
(It is recommended that you solve the above problem before attempting this one, though the problems are independent of each other.)
Once again, let's say we've got a checkerboard. This checkerboard is normal in every respect, as opposed to the mutilated checkerboard from problem 1. Still 64 squares, so it can still be covered with 32 dominoes (using the rules outlined above).
Now here is the puzzle: can we place those 32 dominoes on the checkerboard so that 19 of them are horizontally oriented and 13 of them are vertical?
Once again, if such an arrangement exists, demonstrate it, and if no such arrangement exists, prove that it can't be done.
Spoilers below! Don't look!
Solution to problem 1
It is impossible to cover the mutilated checkerboard with exactly 31 dominoes. To understand why, consider the placement of any domino on the board.
No matter where a domino is placed on the board, it must cover two horizontally- or vertically-adjacent squares. If we think about the checkerboard pattern as it relates to domino placement, we see that adjacent squares are always of alternating color--one red and one white. So every domino must cover a red square and a white square.
Now, the diagonally opposite corners of a checkerboard are necessarily the same color. This means that when our checkerboard is mutilated, we lose, say, two white squares and no red squares. This leaves 30 white squares and 32 red squares on our board.
But, considering that each domino must cover exactly one red and one white square, since we have only 30 white squares, this means we can place at most 30 dominoes on the board... and two red squares will always be left uncovered. QED.
A note on modes of reasoning:
This problem makes an excellent introduction for middle-school age kids (or older) to the idea of inductive versus deductive reasoning. To wit: the instinctive first approach to this problem is to attempt to directly find a pattern that works. However, many different arrangements might be tried, and none of these arrangements will work. Does this prove that the problem cannot be solved? No, because there are easily thousands of possible arrangements for the dominoes. However, inductively, we might suppose that after trying several dozen patterns and failing every time, we might tentatively conclude that the problem cannot be done. However, we have not proved anything. Much like a scientist positing a theory based on many observations, we have a strong "feeling" (supported by evidence) about the truth of our statement, but we need to be willing to face the fact that tomorrow someone might come along and prove us wrong with a single counterexample to our theory.
(It would still be possible to absolutely prove that no arrangement would work through a brute force approach, by testing every single possible arrangement, but this technique in general becomes increasingly impractical as the problem gets more complex, in terms of the time it would take and the difficulty in assuring that every possible arrangement has been considered.)
A deductive approach is one such as that used in the solution given above: rather than looking at specific cases, we take a property that every case has in common and show that no matter what, we will not be able to arrange the dominoes. By looking at a general case we (in a certain sense) deal with every possible arrangement at the same time. Since this conclusion is based on a logical necessity, there is no possibility that an exception might be found.
Solution to problem 2
It is impossible to place 13 dominoes horizontally and 19 vertically on a checkerboard as requested. In fact, it is impossible to have odd numbers of horizontal and vertical dominoes--both collections must be even in number.
However, the coloring trick used in the solution to problem 1 won't help you. There is another coloring trick, though, that will.
Rather than relying on the pattern of alternating red and white squares, we are going to re-color our checkerboard, in a totally different pattern, to facilitate distinguishing between horizontal and vertical dominoes: We will paint even rows red and odd rows white, so that alternating rows are entirely a single color: that is, all eight squares in the first row will be white, the entire second row will be red, the third row white, etc.
Now, a vertically oriented domino straddles two rows of different color, no matter where it is placed on the checkerboard. So every time a vertical domino is placed, one square of each color is used up.
After all 19 vertical dominoes are placed, 19 red and 19 white squares are covered, leaving 13 red and 13 white uncovered.
Now it's time to place the horizontal dominoes. However, no matter where a horizontal domino is placed, it must rest on two squares of the same color. Since there are 13 red and 13 white squares remaining, we can have at most 6 dominoes on just red squares, and 6 dominoes on just black squares--leaving one square of each color uncovered, and one horizontal domino unused. Since these must be in different rows, there is no way the last remaining horizontal domino could possibly cover both squares. QED.