# When Beatrix stops placing dominoes on a 5x5 board, what is the largest possible number of squares that may still be uncovered?

Beatrix places dominoes on a 5x5 board, either horizontally or vertically, so that each domino covers two small squares. She stops when she cannot place another domino, as in the example shown in the diagram.

When Beatrix stops, what is the largest possible number of squares that may still be uncovered?

Clarification 1: The number of horizontal dominoes is not necessarily the same as the number of vertical dominoes.

Clarification 2: When Beatrix places the dominoes she doesn’t necessarily alternate between horizontal and vertical dominoes.

Clarification 3: Once a domino is placed it can’t be moved.

Attribution: UK Junior Mathematical Challenge 2016

Another way to do the proof of optimality:

If you split it like this:

Notice you cannot have three uncovered square in any of the four 2x3 rectangles, since they would need to be in a checkboard pattern but that leaves no room for a domino one place or another. Therefore, if there are nine uncovered squares, there must be exactly two in each 2x3 rectangle, and one in the middle.

Could there be a domino here?

No, because no there is no way to add two uncovered squares in the lower left 2x3. So in order for the center square to be uncovered, we'd need to do something like this:

Now to put two uncovered squares in each 2x3 requires them to be as far as possible apart as possible, but that would be uncovered squares from neighboring 2x3 regions right next to each other, a contradiction.

7 squares.

Proof of optimality:

Because there are 25 squares and the dominos must take up an even amount, there's no solution with 8 squares. Suppose there's a solution with 9 empty squares. We can colour the grid with a checkerboard pattern like so, and each domino must colour one dark square and one light square.
There are 13 light squares and 12 dark squares, so if there's a solution with 9 squares it must have 5 light squares and 4 dark squares uncovered.
Let's take a look at those four dark squares. There are two meaningfully distinct positions each one can be placed on - on the edge or in the center. A dark square on the edge removes three potential light square positions, a dark square in the center removes four. Additionally, we can't have two dark squares in the same corner as the corner square would be blocked off and couldn't have a domino placed on it.

There are 13 potential light square positions, so we need at least five of them to be unblocked, i.e. at most eight can be blocked. As the dark squares block off at least 12 total light squares, we need at least four of them to overlap. In practice, since we can't have two dark squares in the same corner, we need at least one square to be in the centre to have two squares overlapping (while we could have two dark squares on the same edge that blocks off too many squares):

Which means that this these (thanks, AxiomaticSystem)are the only configuration (up to rotation) that leaves enough light squares unblocked:
But it's clearly impossible to place dominoes around these light squares, so no solution with 9 tiles exists.

• There is a second valid arrangement of dark-square gaps - the path isolating a T - but it has exactly the same problems as the first. Commented Aug 4 at 0:16
• Maybe add in a sentence why you can't have 8 uncovered tiles because of parity. Commented Aug 4 at 1:03

7 holes are optimal

In the Book Knotted Doughnuts, Chapter 15 by Martin Gardner, it says "Sands was able to prove the number of holes cannot exceed the number of dominoes." for boards with width and height $$>1$$.

• Presumably that last result doesn't apply to trivial boards such as 1×1 and 1×4?
– Neil
Commented Aug 4 at 8:39