max no of dominoes in a certain way in a 1000x1000 board
Source: Dutch NMO 2015 p2
September 7, 2019
combinatoricscombinatorial geometrydominoesmaximum
Problem Statement
On a -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.