Browse · MathNet
PrintIMO Team Selection Test 1
Netherlands counting and probability
Problem
On a rectangular board consisting of squares (), dominos have been placed (2 × 1- or 1 × 2-tiles), not overlapping each other. Each domino covers exactly two squares of the board. Suppose that the placement of the dominos has the property that no extra domino can be placed on the board, and the four corners of the board are not all empty. Prove that at least of the squares of the board is covered by dominos.
Solution
Assign each empty square to the domino directly right of this square (unless the square is on the right edge of the board). Now suppose that two empty squares are assigned to the same domino, then this domino must be placed vertically and both squares left of this domino are empty. However, that would mean that another domino could fit, which is a contradiction. Hence, no two empty squares are assigned to the same domino.
The empty squares on the right edge of the board have not been assigned a domino yet. We try to assign these squares to dominos that do not have an empty square directly left of them (i.e. dominos which have not been assigned yet). First suppose that we succeed in assigning all empty squares on the right edge of the board in this way to different dominos. In that case, we assigned each empty square to a domino, where no domino has been assigned more than one square. Because each domino covers two squares of the board, there are two covered squares for each empty square, and hence at most of the squares is uncovered. In this case, we are done.
Now we will show that this assignment always works. Let be the number of empty squares on the right edge, and the number of empty squares on the left edge. The empty squares on the left edge cannot be adjacent, hence there are at least dominos on the left edge and these all do not have an empty square left of them. If , then there are enough dominos on the left edge to assign to all empty squares on the right edge. If , we could turn everything around and assign all empty squares to the domino left of them and we could also prove that at most of the squares on the board are uncovered. The only remaining situation is when and both on the left and right exactly dominos are on the edge. For both edges, we have that there must be an empty square between each two dominos, and there must also be empty squares in the corners. This, however, is in contradiction with the condition that not all corners are empty. Hence, this situation cannot occur.
The empty squares on the right edge of the board have not been assigned a domino yet. We try to assign these squares to dominos that do not have an empty square directly left of them (i.e. dominos which have not been assigned yet). First suppose that we succeed in assigning all empty squares on the right edge of the board in this way to different dominos. In that case, we assigned each empty square to a domino, where no domino has been assigned more than one square. Because each domino covers two squares of the board, there are two covered squares for each empty square, and hence at most of the squares is uncovered. In this case, we are done.
Now we will show that this assignment always works. Let be the number of empty squares on the right edge, and the number of empty squares on the left edge. The empty squares on the left edge cannot be adjacent, hence there are at least dominos on the left edge and these all do not have an empty square left of them. If , then there are enough dominos on the left edge to assign to all empty squares on the right edge. If , we could turn everything around and assign all empty squares to the domino left of them and we could also prove that at most of the squares on the board are uncovered. The only remaining situation is when and both on the left and right exactly dominos are on the edge. For both edges, we have that there must be an empty square between each two dominos, and there must also be empty squares in the corners. This, however, is in contradiction with the condition that not all corners are empty. Hence, this situation cannot occur.
Techniques
Pigeonhole principleCounting two waysMatchings, Marriage Lemma, Tutte's theorem