Canada National Olympiad Problem 1
What is the maximum number of non-overlapping
dominoes that can be placed on a
checkerboard if six of them are placed as shown?
Each domino must be placed horizontally or vertically so as to cover two adjacent squares of the board.
The answer is 34.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
For the sake of reference, let's introduce a chess board pattern on the board, with the lower left corner being black. (By "corners" we will always mean the lower left and the upper right.) Disregarding the corners, we observe that there are only 13 black fields in the upper left region and only 13 white fields in the lower right. This shows that we can place at most 28 additional dominoes on the field: two that involve the corners, and at most 13 in each of the two remaining regions, since each domino must cover a white and a black field. The best strategy is to place the dominoes in the corners vertically (as not to steal any of the scarce fields from the regions)... then we can place all the other dominoes horizontally, for a total of 28 (plus the six that were there already).