Problem

Source: Dutch NMO 2015 p2

Tags: combinatorics, combinatorial geometry, dominoes, maximum



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.