Non-slip tiles
Consider a 1 2 × 1 2 board which is to be tiled with 1 × 2 dominos. What is the minimum number of (positive) dominos which we have to place, to get an arrangement in which no domino can slip (horizontally or vertically) into another position (still entirely on the board)?
Details and assumptions
The dominos are not allowed to stick out of the board.
The dominos do not slip diagonally. They slide around as a block.
It is obvious that any domino located on the corner will always be able to slip out of the board. The restriction requires the entire domino to still be placed on the board.
The answer is 62.
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.
2 solutions
Here is an outline of a more formal proof.
Initially, say that to minimize the number of dominoes, the number of empty cells must be maximized.
First, prove that to have a blank cell, there must be dominoes in a square around it. To prove this, use the fact that each cell around an empty cell must be either occupied by a domino not pointing at the cell, or another empty cell.
It is easy to show that there cannot be two empty cells next to each other, since then the configuration causes a domino to point at an empty cell, or causes a domino to be able to slide into two adjacent empty cells.
Then, it isn't hard to show that a single cell cannot be empty unless surrounded by a square of dominoes. Show that otherwise a domino must point at the empty cell. Be careful to account for edge cases, where the empty cell is on the border.
Next, show that if an empty cell is next to a cell of dominoes, it must be in the corner as you have. To do this, show that otherwise a domino points at an empty cell.
I am not sure exactly how to make this final part rigorous, but just claim you must "pack" the squares together and end up with the configuration you describe.
On another note, I found a Go board to be helpful when solving this problem.
Log in to reply
In my solution, an important step was " If square ( a , b ) is empty, then squares ( a + 2 , b ) , ( a + 2 , b + 2 ) , ( a , b + 2 ) , ( a − 2 , b + 2 ) , ( a + 1 , b + 1 ) , ( a − 1 , b + 1 ) cannot be empty. "
I then proceeded (with more steps in-between) to show that in a 5 × 5 board, there are at most 5 empty squares, hence in the 1 0 × 1 0 internal board, there are at most 20 empty squares. Since there are no empty squares on the perimeter, there are at least 61 dominos.
I followed the same optimization technique and derived the following generalized formula for any nxn board with 1x2 dominos: Ceiling[3 (n^4+3 n^2)/(7*n^2+18)] I know reading expressions not written in latex is irritating, sorry for that.Im still working on learning latex :)
Log in to reply
I would be interested in seeing a rigorous treatment of this generalization. Note that you cannot simply assume that the generalized pattern must hold.
Log in to reply
Yes sir.and to be honest,I'm not very sure if it works for very large values of n. I explained my approach in the reply to Anis Abboud's comment. It would be really great if you make a comment on my approach and suggest where I could improve :)
Rewritten your formula in Latex: ⌈ 7 n 2 + 1 8 3 ( n 4 + 3 n 2 ) ⌉
Log in to reply
Thanx a lot :)
BTW, you forgot the 'ceiling'
Log in to reply
@Adeeb Zaman – I don't think so ( see Wikipedia ). The brackets that are open from the bottom indicate ceiling.
The formula I typed: \left\lceil \dfrac{3(n^4 + 3n^2)}{7n^2+18} \right\rceil (wrapped inside \ ( and \ ) of course).
In any case, it would be nice to explain the way you arrived at the formula, and whether you checked it say, for smaller boards (I checked a n=3, 6, and 8, and it seems to be working).
Log in to reply
@Anis Abboud – First of all,extremely sorry for misreading that ceiling notation as a bracket. And to be honest, I'm not sure about very large values of n. This is how I approached :
According to the technique used to optimize the maximum number of blank cells, we have to deal with a 9x9 'box' that contains 4 dominos and 1 blank cell. Though we can put these boxes side by side and achieve a combination where there is a blank cell in every 9 cells, we can still optimize further by merging these boxes. If two boxes are merged so that they share a domino, we can 'save' 2 cells. If there are 'k' number of boxes, there would be (k-1) 'junctions' of dominos. This means we can save 2(k-1) cells. So after optimization, we have filled 9k-2(k-1) = 7k+2 cells. The rest of the cells have to be filled with dominos. Now, as every 9-cell box contains 1 blank cell, 'k' boxes should contain 'k' blank cells. So, of every (7k+2) cells, 'k' are blank. In case of nxn grid, among the n^2 cells, (n^2)*k/(7k+2) should be blank,where k=(n^2)/9. Subtracting this value from n^2 gives the number of cells which, after dividing by 2,gives the number of dominos. This result is not necessarily integer, so we take the ceiling. This is how i derived the expression.
I have 3 basic stages to my solution:
(a) Find the optimal tiling of the plane.
(b) Modify the border of it to fit in a 12x12 rectangle.
(c) Show that no smaller tiling is possible.
Actually, for a proof, only step (c) plus an example is necessary, however it might be interesting to show the motivation for it by doing the first two steps.
Lemma: A hole on the board must be 1x1 (i.e. there cannot be two adjacent empty squares) Lemma: There cannot be a hole on the edge of the board.
These two lemmas are both fairly easy to show by exhaustion, but it is quite wordy to write it up so I am going to skip doing that. Hopefully you can satisfy yourself of this easily by playing around with dominoes.
Lemma: A hole must be surrounded by a little "circle" of four dominoes.
Proof: Consider a square adjacent to a hole. It must be covered by a domino (by the lemma about holes being 1x1), however this domino cannot "point away" from the hole, so it must also cover one of the squares diagonally touching the hole. Applying this reasoning to all four of the squares adjacent to the hole proves the lemma.
Note that there are two ways of doing this, clockwise and anticlockwise.
Lemma: In a plane tiling, there can be at most 5 1 of the plane being holes.
Proof: A domino cannot have a hole on either end of it, otherwise it could slide into that hole. A domino can have at most one hole on each side of it, otherwise there would be a 2x1 hole, which is not allowed by the first lemma.
If we count the number of dominoes by counting 4 for the four that are adjacent to each hole, then we may have counted each domino at most twice (according to the previous paragraph). So there are at least 2 dominoes for each hole, i.e. at least 4 covered squares for each hole.
Now, I found a plane tiling that actually achieves this, based on the principle that each domino can have one hole on either side of it, and all holes must be surrounded by a "circle":
Domino plane tiling
In this picture my "circles" go anticlockwise, and the plane is tiled by the 3 × 3 unit plus one external hole attached. Note that the external hole also has dominoes going around it in an anticlockwise circle.
Part (b) . In this tiling, note that on each horizontal row, there are four covered squares in between each hole. Therefore, if we select a 1 2 × 1 2 board (yellow area) , then there must be exactly two holes which lie on each row but are not on the edge of the board . This generalizes to a board of dimension ( 5 m + 2 ) × ( 5 n + 2 ) ; the proof might not be so simple for boards of other sizes.
Since there cannot be any holes on the edge, once we "fix up" the edges, this means that a "fixed" board can contain at most 1 0 × 2 = 2 0 holes, and therefore the board will contain 2 1 ( 1 4 4 − 2 0 ) = 6 2 dominoes.
The yellow board that I have selected does have the property that it is possible to "fix up" the edge: for every instance where there is a hole on the edge of the board, there is exactly one domino that half sticks off the edge of the board, and you can rotate this to fill in the hole instead of sticking off the edge of the board.
Not every possible selection of the yellow area has this property, but that doesn't matter as we have shown that this selection has a maximal number of holes.
* Part(c) * - to show that this solution is optimal. (So far it's still possible that there exists a better tiling of a 1 2 × 1 2 board which does not generalize to plane tiling).
Lemma: It is not possible to have two holes separated by a single covered square.
Proof Outline: This would contradict the lemma that each hole must be surrounded by a "circle of domino".
Now, In the optimal solution given earlier, each row has at most 2 holes not on the edge. We will show that any solution featuring a row with more than 2 holes must have a corresponding row with fewer holes, so the total number of holes does not exceed that of the optimal solution.
A row can have up to 4 holes not on the edge; the only way to do this is if there are four 3 × 3 blocks of "domino circle" lined up. However, in this case, there are 0 holes on the rows above and below, so any solution involving this scenario has only 4 holes over 3 rows, whereas the optimal solution has 6 .
If a row (of length 1 2 ) has 3 holes: consider the 1 2 × 3 strip where the middle one of the 3 rows has the 3 holes on it. This strip must contain 3 disjoint "circles of domino" . This means that there are 1 2 − 3 × 3 = 3 columns where potentially holes could be found on the top or bottom row.
By the most recent lemma, we can't have a hole on both the top and bottom row of the same column in this strip. So there can be at most 3 holes on the top and bottom rows of the strip combined, so the entire strip has at most 3 + 3 = 6 holes. This is no better than the optimal case. QED
Footnote: I'm not 100% sure that the argument in the last two paragraphs is completely rigorous , perhaps we also have to go on to show that there is no other more optimal solution for the section of board that remains when we remove the 3 x 1 2 strip. But I feel that this could be done following a similar outline.
Your argument is extremely iffy. In general, a global optimum need not result in a local optimum. A classic example would be trying to pack circles into a rectangle. In the plane, the optimum packing would be the hexagonal packing. But for certain rectangles, a slightly shifted pattern allows us to squeeze one more circle in.
My main issue with part (c) is the "row with more than 2 holes must have a corresponding row with fewer holes". Thought the argument seems fine, the corresponding row need not be a bijection. It could perform double duty, for example 3-1-3-3-1-3-3-1-3-1, (where there is a stronger requirement that the corresponding row is next to it), which gives us 22 holes and hence 61 dominos.
Log in to reply
Agree. I had a different plan for part (c) when I started writing the solution but then realized it didn't work either. I suspect it should be possible to fix this up though , with a variation of the "corresponding row with fewer holes".
This is not a very formal solution. I'll explain how I got to the answer, hoping that this might help crafting a "formal" solution.
I started with the observation that tiling 4 dominos this way will make them "support each other", while emptying up one cell in a 3x3 block.
3x3
Applying this to the whole 12x12 board results in 16 empty cells.
12x12
However, after submitting my answer I got "incorrect". So I thought more how can I "merge" two 3x3 blocks to save space while still emptying up 2 cells. Inspired by the way the knight moves in chess, I came up with this:
3x3+3x3
Applying this to the whole board didn't look as symmetric as the previous one, as the new building blocks aren't square. You get the following, where the blue cells are empty, leaving you no option but to tile a domino in each of them.
12x12 final
This tiling left 20 empty cells, and it was the correct answer ( 2 1 4 4 − 2 0 = 6 2 ).