Brainteasers · Strategy and invariants · Medium
Dominoes on a board
A board is a 6 by 6 grid of squares with two diagonally opposite corner squares cut away, leaving 34 squares. A domino covers exactly two squares that share a side. Dominoes may not overlap or hang over the edge or over the missing corners. What is the largest number of dominoes that can be placed on the board?
Answer and solution
Answer
16
Solution
On a chessboard colouring every domino covers one square of each colour, and the two missing corners are the same colour.
The full board has 18 squares of each colour. Opposite corners share a colour, so 16 squares of that colour remain against 18 of the other. Each domino uses one of each, so at most 16 dominoes fit, leaving two squares of the commoner colour bare; 16 can be placed, for example by filling the rows in pairs and leaving one square bare in each of the two short rows. The answer is 16, not 17.
Strategy and invariants comes up in 3 firms' roundsMillennium · Point72 / Cubist · IMC
These 3 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.