Domino covering

Consider the dominos that cover the top left and bottom right corner. Any path that connects them has at least 55 other cells, and therefore it contains at least $\lceil 55/2\rceil=28$ other dominos. Hence $N\geq 30$ .

Now, consider the following pattern for a $6\times 6$ board:

+---+---+---+---+---+---+
|       |       |       |
+---+---+---+---+---+---+
|       |       |       |
+---+---+---+---+---+---+
|       |       |   |   |
+---+---+---+---+   +   +
|       |       |   |   |
+---+---+---+---+---+---+
|       |   |   |   |   |
+---+---+   +   +   +   +
|       |   |   |   |   |
+---+---+---+---+---+---+

It is easily shown that for this pattern any pair of dominos can be connected by a path that contains at most 6 dominos, including the initial and the final one. (There is always an optimal sequence of cells where we either first go horizontally and then vertically, or vice versa.) This generalizes to any $2k\times 2k$ board. Thus the smallest possible $N$ is $\fbox{30}$ .

Since a path from one corner to the opposite corner involves at least 59 squares, it involves at least 30 dominoes, so $N \geq 30$ . I will prove that $N=30$ is possible, thereby establishing that it is the minimum value.

We will prove by induction that, for a $2n \times 2n$ board, it is possible to have $N=2n$ . For $n=1$ , it is trivially true. Now we prove that it holds for a $2n \times 2n$ board, assuming that it holds for a $2(n-1) \times 2(n-1)$ board.

Cover the rim of the board. The rest of the board is effectively a $2(n-1) \times 2(n-1)$ board; we cover it in accordance with the induction assumption.

Consider any two dominoes. From both dominoes, it takes at most $1$ domino to get to a domino that's not on the rim. By induction, there is a path of at most $2(n-1)$ dominoes between those two dominoes. Therefore, the whole path consists of at most $2n$ dominoes. Therefore, we have $N=2n$ for this configuration. This concludes the proof.

First, we count the shortest number of dominoes from the top-left to the bottom-right domino. To get to the bottom-right, you must go down 29 squares, and over 29 squares. Including the top-left square, this is 59 squares, and that is at least 30 dominoes, so N is at least 30.

We will now show that N=30 is minimal. Consider a configuration where the first and last columns have only vertical dominoes, and every other domino is horizontal. The shortest path from the top-left to the bottom-right domino connects 30 dominoes, 15 vertical, 14 horizontal, and then 1 vertical. Now, it remains to be shown that every pair of dominoes can be connected by a path of at most 30 dominoes. If both dominoes are vertical, and on the same side, the maximum path length is 15. If they are both vertical and on opposite sides, the path must consist of 14 horizontal dominoes, and a maximum of 16 vertical, if they are opposite corners. If they are both horizontal, then a shortest path will consist of a maximum of 15 horizontal dominoes and 15 vertical dominoes, since a path can be created by going to one of the left and right columns, going to the appropriate row, and going across. There cannot be more that 15 horizontal dominoes in such a path, because going one column and down, to the goal domino, to the other column and up, and back goes through 28 horizontal dominoes, so the lesser of the paths must be at most 15 horizontal dominoes, including the start domino.

Therefore, the answer is 30.

If a path of N dominoes covers two squares, those squares are of distance at most 2N-1 in the taxicab metric. The opposite corners are distance 58 apart, so no path of length less than 30 can connect dominoes covering opposite corners.

We'll show 30 is achievable by construction. Construct a horizontal brick-pattern triangle whose base is 15 horizontal dominoes along the bottom of the board, with 14 dominoes above it, then 13, etc. up to 1 horizontal domino. The center of the board is on the top edge of the top domino. Reflect this to make another triangle of horizontal dominoes from the top side of the board to the center of the board. The gaps to the left and right can be tiled by dominoes in precisely one way, with triangles of vertical dominoes in a brick pattern with 14 vertical dominoes along the left and right sides, not including the corner squares which are covered by horizontal dominoes. Equivalently, we cover a 2x2 board by horizontal dominoes, than then tile concentric 2nx2n boards to include the previous tilings plus n dominoes along the bottom, n dominoes along the top, n-1 dominoes along the left side, and n-1 dominoes along the right side.

In this tiling, any domino can be connected to one of the central dominoes by a path of length at most 15, and the central dominoes are adjacent. So, any two dominoes can be connected by taking the union of those paths to the central dominoes, which has length at most 30.

Make a 8 8 square in your notebook. Observe that if you want to reach from one corner to another, then diagonal offers the shortest path and there exist a covering such that each square on diagonal is covered with a different domino. Hence, at least minimum value of N in this case is 8. Similarly for 30 30, value of N will be 30.

The worst case happens when we want to trace a path from a domino from one corner to the opposite corner (from the lower left to the upper right, for instance).

Since each domino is 1x2, by moving only towards our goal (the ending domino) we advance 2 grids in the board. Moreover, since the board is 30x30 we gotta walk 30 times horizontally and 30 times vertically in the worst case, so we have to walk 60 grids taking 2 grids per step. Total is 60/2 = 30 steps (dominoes).