$6 \times 6$ board using 18 dominos. Find the smallest positive integer $k$ which satisfies the following property:

Diego wants to completely cover aIt is possible for Diego to place $k$ dominos, such that there is a unique way to completely cover the remaining squares.

The answer is 3.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

First analyse the Problem.

It is evident that if you can isolate out a complete 2 x 2 square, there are at least two ways of filling it up, either both dominos horizontally or both vertically.

Consider the whole board as 3 rings. Observe the outermost ring of squares alone. For all of them to be filled, there are two ways (symmetrical), provided there are no dominos that lie both in the outer and middle ring. Same goes with both the middle and inner ring. Therefore the dominos that must be placed must restrict a block lying in two rings and ensure that any two adjacent rings have blocks that do not form a 2 x 2 square, that is, adjacent rings do not have same configuration. This implies that there must be one block in every ring (forcing the rest of the dominos to fall in one of the two possibilities of that ring) and the block must be arranged such that no squares are formed between the rings. This gives the minimum number of blocks as 3.

Lets take a case when a domino lies across two rings. Now analyse each ring. It is evident that it can’t be filled. To be able to fill a ring, an even number of dominos must lie across it. If we keep two dominos across the outer and middle ring, then the outer ring is now fixed. However, the middle ring and outer ring now have the same configuration. Any piece now placed in the outer or inner ring will form squares. To force the middle ring to a different configuration, you would need at least 2 (or an even number of) dominos on either side of the domino placed .To minimize this, you can keep the former dominos adjacent, requiring only 2 (or an even number of) dominos for middle and inner ring. However, placing dominos across rings in some case may make the board unsolvable. In other cases, there would be the formation of squares which would make the not fit the solution.

Therefore, the least possible number of dominos only comes when the initial dominos are arranged along the rings. The answer is 3.

Eg.

X X O O O O.....O X X O O O.....O O X X O O

O X X O O O.....O X O O O O.....O X X O O O

O O X X O O.....O X X O O O.....O O O O O O

O O O O O O.....O O X O O O.....O O X X O O

O O O O O O.....O O O O O O.....O O O O O O

O O O O O O.....O O O O O O.....O O O O O O

And many more...

Alfred Festus Davidson
- 7 years, 4 months ago

Log in to reply

You used a condition of "provided there are no dominos that lie both in the outer and middle ring (same goes with both the middle and inner ring).

As such, you need to deal with cases where this happens. It is possible to have 1 domino block the outer+middle ring, and another to block the middle+inner ring. Why isn't the resultant configuration unique?

The rest of your argument makes sense.

Log in to reply

Thanks! I've updated the comment. I am not able to find exactly the number of dominos required when arranged across rings. But, its definitely more that 3.

Alfred Festus Davidson
- 7 years, 4 months ago

Another example:

```
x.....
xx....
.xx...
..x...
......
......
```

Basically, the idea is to find a structure of dominoes which leads to the the existence of "pockets", (a pocket means an unoccupied cell with exactly one unoccupied neighbor). A pocket will force domino to occupy its place with exactly one way ... the above structure will force one domino after another to be placed to cover the pockets.

$k = 1$ won't give us any pockets regardless where we put the domino.

$k = 2$ , to create pockets, at least one domino has to be touching the edge of the $6 \times 6$ area, or else, there will be no pockets created. It's easy to see by trying a few combinations of 2 dominoes that the pocket generation will stop after a few moves.

Lego Haryanto
- 7 years, 4 months ago

Log in to reply

Log in to reply

Calvin, thanks for the comment. I agree the statement is a bit undermining the whole thing. Actually, I tried a few 2 dominos combination before deducing that it won't lead to continuous pocket generations. But, I just can't put it mathematically, ... I'm embarrassed to say that what I did was trial error and deduce bravely. I'd like to say that I don't need to try a lot, I just need to make sure that the first domino will be in the upper left quadrant, for instance ...

Lego Haryanto
- 7 years, 4 months ago

×

Problem Loading...

Note Loading...

Set Loading...

I cannot give a full solution, but I can give an example.

O's represent the first k dominos, already placed.