Wrong post, ignore.

This is definitely wrong as the first deduction is not trivial. And if you prove that the answer is 2(2n choose n)

Do you know which nation has proposed this problem?

I believe 1... 1.22 3... 3.44 is valid, which breaks a lot of claims in post #2.

We can partition our $2n \times 2n$ array into $n^2$ squares of side $2$, said main squares. By the hypothesis, we have that in each main square there are at least two uncovered cells, so we can easily get exact equality; thus, in each main square there are exactly two uncovered cells. We say that a main square is north if the two uncovered units are on the top, etc. We say that a square is north-east if it is either north or east, etc. After defining all that, we can start work. If a main square is north-east, then each main square at its bottom or at its left is north-east (this is pretty boring to verify, but it works; not even that hard). So, if we draw the two paths that divide north-east from south-west and north-west from south-east, we get two minimal paths. Now it's pretty clear that what we have done is an iff (or at least I hope it's clear), so we get that the number required is exactly $\binom {2n}{ n}^2$.

I thought this was a really nice problem! Generalizing the problem slightly, the answer is $\binom{m+n}{n}^2$ for a $2m \times 2n$ rectangle, and the proof is the following nice bijection: [asy][asy] size(10cm); for (int i=1; i<=4; ++i) { draw((0,2*i-1)--(8,2*i-1), lightgrey+1); draw((2*i-1,0)--(2*i-1,8), lightgrey+1); } for (int i=0; i<=4; ++i) { draw((0,2*i)--(8,2*i), grey+1); draw((2*i,0)--(2*i,8), grey+1); } pen pp = opacity(0.6)+4; draw((0,0)--(2,0)--(2,4)--(6,4)--(6,8)--(8,8), red+pp); draw((0,8)--(4,8)--(4,2)--(6,2)--(6,0)--(8,0), blue+pp); real eps = 0.15; path dom = (eps,1-eps)--(1-eps,1-eps)--(1-eps,eps-1)--(eps,eps-1)--cycle; pen[] colors = {olive, deepmagenta, heavycyan, heavygreen}; void draw_domino(real x, real y, int n) { filldraw(shift(2*x-1,2*y-1)*rotate(90*n)*dom, colors[n]+opacity(0.7), black); } draw_domino(4,4,0); draw_domino(4,3,0); draw_domino(4,2,0); draw_domino(4,1,0); draw_domino(3,2,0); draw_domino(3,3,1); draw_domino(3,4,1); draw_domino(1,1,2); draw_domino(1,2,2); draw_domino(1,3,2); draw_domino(1,4,2); draw_domino(2,3,2); draw_domino(2,4,2); draw_domino(2,2,3); draw_domino(2,1,3); draw_domino(3,1,3); [/asy][/asy] In my opinion it is very hard to solve the problem without first guessing what the correct answer is (I suppose it may be possible if one draws a large enough square, say $n \ge 4$, to notice the pattern). (EDIT: there are ways to find this, see below.) The main reason I was able to make the correct guess was because I generalized the problems to rectangular boards rather than to square boards. I think the three main motivations I had for doing so was (a) The problem felt very recursive, in that smaller instances of the problem would appear as sub-cases. In particular, my computation for $(m,n)=(2,2)$ requires $(m,n)=(2,1)$ as a subcase anyways. (b) The problem makes it otherwise too difficult to examine small cases (see USAMO 2007 #3 for another such example). (c) $(m,n)=(2,1)$ gives another perfect square $3^2=9$ so there is good reason to believe that something is going on here too. Once you have the guess down, it becomes more clear that any recursive solution is likely to fail (due to the square), and one needs to find a "combinatorial" interpretation for the problem. The two paths as shown is a natural one, and with a little work one gets the bijection above.

I would agree with vEhance that studying small cases in general is hard. However I solved the problem with a different motivation. If one orients the top left square in a certain way notice that the rest of the grid is filled in with two tiles. This gives the "chomp" or "path" bijection. Generalizing this solves he problem as above.

Hmm, I felt the opposite about the problem. I felt like this problem was just deciphering through the conditions until you got to something easy. Observation 1: If you have the # of uncovered squares, and the 2x2 constraint, it can be tiled with dominoes in exactly one way. Therefore we can forget about the dominoes. Observation 2: The 2x2 constraint is equivalent to the fact that in every pair of diagonally touching squares, at least one is uncovered. Observation 2 allows us to consider each chessboard color seperately, and square the answer. In each of the n^2 2x2 boxes that partition the grid, exactly either the top left or bottom right corner is uncovered. Furthermore, if the bottom right corner is uncovered, then the bottom right of the squares right and down from it must be uncovered. This bijects to paths on an nxn grid.

ksun48 wrote: Observation 1: If you have the # of uncovered squares, and the 2x2 constraint, it can be tiled with dominoes in exactly one way. Therefore we can forget about the dominoes. Could you elaborate on this? I don't quite see what you mean. @mss, ksun: In retrospect you're probably right. I never actually drew a grid for $n \ge 3$, because I was dying to know what the actual answer was and was only doing small cases. I guess if you try to actually draw a "generic" $8 \times 8$ grid satisfying the condition then it becomes much clearer what's happening. The observation about thinking about each color separately is clever, I didn't see that at all. Thanks.

On #8 of page 4 of this, you can see a problem extending the idea of counting the number of colorings that avoid diagonal adjacency. That one just has 6 by 6, but it can be generalized to arbitrary sizes. The intended solution to that one was path bijections, like the ones people are using here.

v_Enhance wrote: I thought this was a really nice problem! Generalizing the problem slightly, the answer is $\binom{m+n}{n}^2$ for a $2m \times 2n$ rectangle, and the proof is the following nice bijection: [asy][asy] size(10cm); for (int i=1; i<=4; ++i) { draw((0,2*i-1)--(8,2*i-1), lightgrey+1); draw((2*i-1,0)--(2*i-1,8), lightgrey+1); } for (int i=0; i<=4; ++i) { draw((0,2*i)--(8,2*i), grey+1); draw((2*i,0)--(2*i,8), grey+1); } pen pp = opacity(0.6)+4; draw((0,0)--(2,0)--(2,4)--(6,4)--(6,8)--(8,8), red+pp); draw((0,8)--(4,8)--(4,2)--(6,2)--(6,0)--(8,0), blue+pp); real eps = 0.15; path dom = (eps,1-eps)--(1-eps,1-eps)--(1-eps,eps-1)--(eps,eps-1)--cycle; pen[] colors = {olive, deepmagenta, heavycyan, heavygreen}; void draw_domino(real x, real y, int n) { filldraw(shift(2*x-1,2*y-1)*rotate(90*n)*dom, colors[n]+opacity(0.7), black); } draw_domino(4,4,0); draw_domino(4,3,0); draw_domino(4,2,0); draw_domino(4,1,0); draw_domino(3,2,0); draw_domino(3,3,1); draw_domino(3,4,1); draw_domino(1,1,2); draw_domino(1,2,2); draw_domino(1,3,2); draw_domino(1,4,2); draw_domino(2,3,2); draw_domino(2,4,2); draw_domino(2,2,3); draw_domino(2,1,3); draw_domino(3,1,3); [/asy][/asy] In my opinion it is very hard to solve the problem without first guessing what the correct answer is (I suppose it may be possible if one draws a large enough square, say $n \ge 4$, to notice the pattern). The main reason I was able to make the correct guess was because I generalized the problems to rectangular boards rather than to square boards. I think the three main motivations I had for doing so was (a) The problem felt very recursive, in that smaller instances of the problem would appear as sub-cases. In particular, my computation for $(m,n)=(2,2)$ requires $(m,n)=(2,1)$ as a subcase anyways. (b) The problem makes it otherwise too difficult to examine small cases (see USAMO 2007 #3 for another such example). (c) $(m,n)=(2,1)$ gives another perfect square $3^2=9$ so there is good reason to believe that something is going on here too. Once you have the guess down, it becomes more clear that any recursive solution is likely to fail (due to the square), and one needs to find a "combinatorial" interpretation for the problem. The two paths as shown is a natural one, and with a little work one gets the bijection above. Can you write more details on the bijection?

The official solutions has the same bijection, so you can see the details there.

We claim the answer is $\boxed{\binom{2n}{n}^2}$. We have the following lemma: Lemma: Partition the $2n\times 2n$ into $2\times 2$ squares in the obvious way. Then, each one has exactly one domino in it. Proof of Lemma: Each $2\times 2$ square has at most $2$ covered unit squares, so at most $2n^2$ total covered squares. But the dominoes cover a total of $2n^2$, so equality in our argument must hold, and since we can't have the two opposite corners covered, each $2\times 2$ must have two consecutive squares covered. So either a domino is there like we want, or we have the exceptional case where two consecutive dominoes cover it. But it is not hard to see that this can't happen due to parity reasons, so the lemma is proven. $\blacksquare$ Therefore, we can encode the problem as an $n\times n$ grid with arrows filled in (representing which edge of the square the domino lies on). It is not hard to see that the problem is equivalent to the following two conditions: If an arrow points in direction $X$, then all squares on the ray from that square in direction $X$ have the same direction. We have no rotations or reflections of the configurations $\uparrow\downarrow$ or $\uparrow\leftarrow$. Now we have a bijection from arrow configurations to paths from opposite corners that travel along the gridlines (clearly there are $\binom{2n}{n}^2$ of these). Basically, the paths partition the square into 4 regions with natural directions N,E,S,W, so we just fill those with the arrows of that particular direction. Here is an example: [asy][asy] int N=8; unitsize(32); int[][] a = { {3,3,3,3,0,0,0,0}, {3,3,3,3,0,0,0,0}, {3,3,2,2,1,1,1,1}, {3,3,2,2,1,1,1,1}, {2,2,2,2,2,2,1,1}, {2,2,2,2,2,2,1,1}, {2,0,2,2,2,2,2,2}, {2,2,2,2,2,2,2,2} }; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { draw((i, -j)--(i+1, -j)--(i+1, -j-1)--(i, -j-1)--cycle); if (a[j][i] == 0) label("$\uparrow$", (i+0.5, -j-0.5), fontsize(16pt)); if (a[j][i] == 1) label("$\rightarrow$", (i+0.5, -j-0.5), fontsize(16pt)); if (a[j][i] == 2) label("$\downarrow$", (i+0.5, -j-0.5), fontsize(16pt)); if (a[j][i] == 3) label("$\leftarrow$", (i+0.5, -j-0.5), fontsize(16pt)); } } draw((0,0)--(4,0)--(4,-4)--(6,-4)--(6,-6)--(8,-6)--(8,-8),red+linewidth(3)); draw((8,0)--(8,-2)--(2,-2)--(2,-6)--(0,-6)--(0,-8),red+linewidth(3)); [/asy][/asy] It is not hard to see this works in general, so we are done.

Solved with fukano_2 Tile the grid with $2\times 2$ squares in the standard manner. In what follows we refer to these $2\times 2$ squares in the singular form as a baked potato. Claim. Then, each baked potato contains exactly one domino. Proof. Every baked potato described must have at least $2$ squares of blank space, but because of Pigeonhole reasons the baked potato must also have at most $2$ squares of blank space, so it has exactly two squares of blank space. The claim follows. As shown above, let $A,B,C,E$ denote the four corners and let $U,R,D,L$ denote the four positions a domino can be in. For instance, $AB=U$ and $AE=L$. We note that if a baked potato contains an $A$ (that is, the domino is either in position $U$ or $L$), then all baked potato above and to the left must also have an $A$ (of course, there may be no baked potato that contains an $A$ at all). Similar reasoning gives that if a baked potato contains a $C$, all potatoes below and to the right must also have a $C$. Now draw a path from the bottom left corner of the $2n\times 2n$ grid to the top right - every baked potato below this line must contain a $C$ and all above must contain an $A$ (this bijective argument is similar to Canada 2019/3). We similarly draw a path to figure out which baked potato have $B$'s and $E$'s; hence, the answer is just $\binom{2n}n^2$.

This is literally Canada 2019/3 but slightly more complicated. The answer is ${2n \choose n}^2$. Note that there is exactly one domino within each $2 \times 2$ squares in a partition of the grid into $2 \times 2$ squares. The idea is to assign to each $2\times 2$ square a unique signature based on two characteristics: say it has characteristic $A$ if its upper left square is part of a domino, or characteristic $B$ if its lower right square is part of a domino. Similarly, assign it characteristic $C$ if its lower left square is part of a domino, and characteristic $D$ if its upper right square is part of a domino. Note that each square satisfies one of $\{A, B\}$ and one of $\{C, D\}$. However, notice that if a square satisfies characteristic $B$, then all squares to the right or below it must also satisfy that characteristic. Similarly, if a square satisfies characteristic $D$, then all squares above it and to the right of it must also satisfy characteristic $D$. As there are no other restrictions, the placement is equivalent to drawing two paths on the grid consisting of the $2 \times 2$ squares, one from the top left corner to the bottom right corner, and one from the bottom left corner to the top right corner, which divide the large grid into regions of characteristics $A$ and $B$, and $C$ and $D$ respectively. There are thus ${2n \choose n}^2$ ways to do this.

Color the chessboard black and white in the normal fashion. Claim. Given the rest of the information in the problem, "every $2\times 2$ square contains at least two uncovered squares which lie in the same row or column" is equivalent to "for every cell filled in the grid, the (up to) four cells diagonally adjacent to it are all not filled". Proof. The forwards direction is easy via proof by contradiction. The backwards direction is trivial upon inspecting on the two pairs of "at most one is filled" diagonals in a $2\times 2$ square. Now tile the $2n\times 2n$ grid with $n^2$ of $2\times 2$ squares. Then obviously each of these $2\times 2$ squares contain exactly one domino. It now remains to choose one black and one white square from each $2\times 2$ square. Note that if the bottom right square is chosen for a $2\times 2$ square, then everything to the right of(or equal to) and below(or equal to) that square will also have the bottom right square be the same colored square it has. So the grid would be divided into a "top left" region and a "bottom right" region, and by stars and bars there are $\binom{2n}{n}$ ways to do that. So the answer is $\boxed{\binom{2n}{n}^2}$.

Color the square white and black in a checkerboard, and also divide the grid into 2x2 sub-grids. The condition that each 2x2 must have two uncovered cells in the same row or column is equivalent to no two diagonally adjacent cells both being covered. Claim: There are ${2n\choose n}$ ways to select $n^2$ of the white cells (suppose the top left is white) such that no two selected cells are diagonally adjacent. From dividing the grid into 2x2 sub-grids, obviously we can select at most one cell in each sub-grid, so we have to select one from each (as there are only $n^2$ such grids). Call a sub-grid good if we select the top left cell, and bad if we select the bottom right cell. For any sub-grid to be bad, the one to the right of it, the one below it, and the one both to the right and below it all have to be bad (since otherwise there will be two diagonally adjacent chosen cells. This sets up a "dependency chain", such that, in the ending configuration, given any bad sub-grid, all of the ones in the rectangle containing that grid and the bottom-right grid as opposite corners must also be bad. Thus, essentially we are selecting $n$ positive integers $a_1,a_2\cdots a_n$ from 0 to $n$ and making the rightmost $a_i$ grids in row $i$ bad and all of the other ones good. Furthermore, the sequence also has to be nondecreasing. By stars and bars, there are ${2n\choose n}$ ways to select a nondecreasing sequence of length $n$ where each number is from 0 to $n$, which shows the claim. In a similar way, select $n^2$ black cells in ${2n\choose n}$ ways. Given any set of $k$ chosen black cells, all $k$ are in different sub-grids, and each black cell is adjacent to both white cells in its sub-grid. Since each sub-grid also has a chosen white cell, the $k$ sub-grids that contain one of the $k$ chosen black cells must each contain a chosen white cell that is adjacent to the chosen black cell in that sub-grid, hence by Hall there exists a perfect matching from chosen white cells to chosen black cells, so each of the ${2n\choose n}^2$ ways to choose the cells does indeed correspond to a valid domino configuration, hence done.

Inspired by Canada 2019 P3. Characterize the dominos by VR,VL,HD,HU for vertical right, vertical left, horizontal down, horizontal up, and the squares in a 2x2 by UL,UR,BL,BR. Notice by the condition that each 2x2 square can have at most 1 domino, meaning in total at most mn dominoes; in particular, each one has exactly one domino. Also, the condition about two uncovered squares in same row or column implies that any diagonally adjacent cells cannot be both filled (1). Now, it's evident that if a 2x2 square A has BR covered, the 2x2 squares below and to the right of it must also have BR covered. This follows from (1) along with induction: if any 2x2 square adjacently above (resp. to the left) of a square B has BR covered, then the square B cannot have UL covered, meaning BR must be covered. Analogously to the upper and left of a UL square follows. Using this property, we can divide the grid into characteristic of UL or BR regions, which is a bijection with drawing two paths from top left to bottom right and resp. bottom left to top right, which there are then ${2n\choose n}^2$ ways to do so. $\blacksquare$ huh, these combo games arent so hard after all...

Partitioning the board into $n^2$ $2 \times 2$ squares, and notice that we have exactly one domino in each square. We now translate the problem into coloring each of these squares $U$ (up), $D$ (down), $R$ (right), and $L$ (left) to represent domino placements. When a square is colored $D$, the squares under it must also be colored $D$. Similarly, coloring a square $R$ forces the rest of the squares in the row to be colored $R$. Hence the "wall" separating the $L$, $U$ and $L$, $R$ corresponds to a path from the bottom left to the top right. In each individual subsection, we have a similar pattern, where the colors all separated by a "boundary" which only runs lefts and down. Note that if the endpoints of the two "boundaries" on the original "wall" have both different $x$- and $y$- coordinates, which will have either $L$, $R$ adjacent or $U$, $D$ adjacent, which is impossible. Thus the two "boundaries" are uniquely determined by a path running from the top left to bottom right. Hence we have a bijection to drawing the described two paths, giving our answer $\boxed{\binom{2n}{n}^2}$. $\blacksquare$

We partition the $2n \times 2n$ grid into $n^{2}$ $2 \times 2$ squares. Then, notice that there must be exactly $2$ squares filled by the dominos in each $2 \times 2$ grid. Notice that these $2$ squares must be part of the same domino, since otherwise, we get a parity issue on the borders. Now, notice that there are $4$ different orientations for each domino, the left-vertical, the right-vertical, the bottom-horizontal, and the top-horizontal (shorthanded LV, RV, BH, TH). We now partition the board into one (possibly nonempty) group of each of the orientations. Notice that the separation between the groups of RV and BH and TH and LV form a path from the top left corner to the bottom right corner, and similarly for BH and LV and RV and TH. Notice that these paths are uniquely determined by a correct grid, and conversely, the paths partition the $2n \times 2n$ square into the $4$ regions consisting of each orientation. Thus, we get ${2n \choose n}^{2}$ as our answer.

Partition the grid into $2 \times 2 $ squares. Claim: No domino can pass between two seperate $2 \times 2$ squares. Proof: Assume that it did, and WLOG it is veritcal. Then, all its not hard to see that all squares to the right and left of the domino must be left blank. There can either be a domino adjacent to the domino on either side of the short side though, but at some point this chain must end. Consider where it does end. Then it is not hard to find $n+1$ $2 \times 2$ squares which only contain $n$ dominos. But this gives a contradiction for the remaining squares, particularly in that we have too many dominos and too little squares remaining for the "at least two uncovered" condition to be satisfied. $\blacksquare$ Now label the dominos on the top, right, left, bottom as $1, 2, 3, 4$ respectively. It's not hard to see that the only dominos above a $1$ can be a $1$, only ones to the right can be a $1, 2$, only ones to the left can be a $1, 3$ and the bottom is unrestircted. Similar cases occur for the other dominos. Thus, on a vague general scale looking at the $n \times n$ grid of $2 \times 2$ squares, the "top" region is covered by $1$ dominnos, the bottom by $4$ dominos, the right by $2$ dominos and the left by $3$ dominos. After engineer inducting the answer to be $\boxed{(\binom{2n}{n})^2}$, it is very natural to consider the two diagonal paths from the corners that divide the grid into four distinct regions. It's not hard to see the bijection here which finishes.