On a $1000\times 1000$-board we put dominoes, in such a way that each domino covers exactly two squares on the board. Moreover, two dominoes are not allowed to be adjacent, but are allowed to touch in a vertex. Determine the maximum number of dominoes that we can put on the board in this way. Attention: you have to really prove that a greater number of dominoes is impossible.
Problem
Source: Dutch NMO 2015 p2
Tags: combinatorics, combinatorial geometry, dominoes, maximum
John-Wick
07.09.2019 12:14
A maximum of 250,000 dominoes can fit on the board. We first show to place this number of dominoes on the board. In each row we put 250 dominoes with two empty squares in between consecutive dominoes. In the odd numbered rows we start with a domino and end with two empty squares (since the number of squares in a row is a multiple of four). In the even numbered rows we start with two empty squares and end with a domino. Thus, we place a total of 1000 · 250 = 250,000 dominoes, see the figure. Clearly, no two dominoes in the same row are adjacent, and dominoes in adjacent rows touch in a vertex, at most. To complete the proof, we need to show that it is not possible to place more than 250,000 dominoes on the board. Partition the board into 500×500 patches consisting of 2×2 squares each. Of each patch, at most two out of the four squares can be covered by dominoes since otherwise two dominoes would be adjacent. Hence, no more than 2·500·500 = 500,000 squares can be covered by dominoes. This shows that no more than 250,000 dominoes can fit on the board.
Attachments:
