Here is the solution from the shortlist packet: The answer is surprisingly small: $2n$. For this problem, having a square (instead of a rectangle) is imperative. First, we give a construction with $2n$ marked squares. Just an example with $n=3$: [asy][asy] size(7cm); for (int i=0; i<=6; ++i) { draw((0,i)--(6,i), grey); draw((i,0)--(i,6), grey); } picture mark; draw(mark, (0,0)--(1,1), grey+1.3); draw(mark, (1,0)--(0,1), grey+1.3); add(shift(0,5)*mark); add(shift(0,4)*mark); add(shift(1,4)*mark); add(shift(1,3)*mark); add(shift(2,3)*mark); add(shift(2,2)*mark); pen border = black+1.5; draw(box((0,0), (2,1)), border); draw(box((2,0), (4,1)), border); draw(box((4,0), (6,1)), border); draw(box((0,5), (2,6)), border); draw(box((2,5), (4,6)), border); draw(box((4,5), (6,6)), border); draw(box((1,1), (3,2)), border); draw(box((3,1), (5,2)), border); draw(box((1,4), (3,5)), border); draw(box((3,4), (5,5)), border); draw(box((0,1), (1,3)), border); draw(box((0,3), (1,5)), border); draw(box((5,1), (6,3)), border); draw(box((5,3), (6,5)), border); draw(box((1,2), (2,4)), border); draw(box((4,2), (5,4)), border); draw(box((2,2), (4,3)), border); draw(box((2,3), (4,4)), border); [/asy][/asy] Now we show this is optimal. The main claim is the following. Lemma: In an arbitrary domino tiling of a $2n \times 2n$ square it is possible to partition the dominoes into several cycles, at least $n$ of which are nontrivial. (A cycle is a $2k$-cycle on the grid which pair off into dominoes, possibly including trivial cycles for which $k = 1$.) Proof. Take the tiling and reflect it across the main diagonal, then overlay it on the original. This gives us a bunch of cycles. Now note every cell on the main diagonal is in a nontrivial cycle, and moreover by symmetry each such cycle has exactly two cells on the main diagonal. $\blacksquare$ Thus, we can take a cycle with at most one marked square and then replace it with the overlaid image.

made a mistake

DVDthe1st wrote: Thanks to MellowMelon, we now know almost all hard chessboard problems can be solved using lazers. As the above solution notes, we are required to break the board into at least $n$ cycles. Place small mirrors centered at $(x,y)$ whenever $x+y$ is odd and align them to one of the axes of the chessboard (where $(0,0)$ is a corner of the chessboard). In particular, mirrors are not allowed to cut into dominoes. Now, fire lazers from the centers of mirrors at a 45 degree angle to the axes, until all cells have one lazer beam running between one pair of opposite corners: [asy][asy] size(7cm); for (int i=0; i<=6; ++i) { draw((0,i)--(6,i), grey); draw((i,0)--(i,6), grey); } pen lazer = red+1; for (int i=0; i<=5; ++i) {for (int j=0;j<=5;++j) {if ((i+j)%2==0){draw((i,j+1)--(i+1,j),lazer);}else{draw((i,j)--(i+1,j+1),lazer);}}} picture mark; draw(mark, (-0.2,0)--(0.2,0), black+5); add(shift(1,0)*mark); add(shift(3,0)*mark); add(shift(5,0)*mark); add(shift(2,1)*mark); add(shift(4,1)*mark); add(shift(3,2)*mark);add(shift(3,4)*mark); add(shift(1,6)*mark); add(shift(3,6)*mark); add(shift(5,6)*mark); add(shift(2,5)*mark); add(shift(4,5)*mark); picture mark; draw(mark, (0,-0.2)--(0,0.2), black+5); add(shift(0,1)*mark); add(shift(0,3)*mark); add(shift(0,5)*mark); add(shift(1,2)*mark); add(shift(1,4)*mark); add(shift(2,3)*mark);add(shift(4,3)*mark); add(shift(6,1)*mark); add(shift(6,3)*mark); add(shift(6,5)*mark); add(shift(5,2)*mark); add(shift(5,4)*mark); pen border = black+1.5; draw(box((0,0), (2,1)), border); draw(box((2,0), (4,1)), border); draw(box((4,0), (6,1)), border); draw(box((0,5), (2,6)), border); draw(box((2,5), (4,6)), border); draw(box((4,5), (6,6)), border); draw(box((1,1), (3,2)), border); draw(box((3,1), (5,2)), border); draw(box((1,4), (3,5)), border); draw(box((3,4), (5,5)), border); draw(box((0,1), (1,3)), border); draw(box((0,3), (1,5)), border); draw(box((5,1), (6,3)), border); draw(box((5,3), (6,5)), border); draw(box((1,2), (2,4)), border); draw(box((4,2), (5,4)), border); draw(box((2,2), (4,3)), border); draw(box((2,3), (4,4)), border); [/asy][/asy] This breaks down the lazers into simple loops, so let's also assume that all lazers are travelling clockwise along the loops. Now let's calculate the total turning number. Note that each mirror along the outside perimeter contributes to a quarter-turn clockwise. For the internal mirrors, we can imagine that the two loops reflecting against the mirror are either externally tangent (contributing to a half-turn clockwise overall) or internally tangent (contributing zero turning overall). Hence the total turning number is at least $n$, meaning that there are at least $n$ loops formed. Can you tell me what is the motivation for lazer :< . I really don't get it

I think it was inspired by MellowMelon's solution to this problem.

DVDthe1st wrote: Thanks to MellowMelon, we now know almost all hard chessboard problems can be solved using lazers. As the above solution notes, we are required to break the board into at least $n$ cycles. Place small mirrors centered at $(x,y)$ whenever $x+y$ is odd and align them to one of the axes of the chessboard (where $(0,0)$ is a corner of the chessboard). In particular, mirrors are not allowed to cut into dominoes. Now, fire lazers from the centers of mirrors at a 45 degree angle to the axes, until all cells have one lazer beam running between one pair of opposite corners: [asy][asy] size(7cm); for (int i=0; i<=6; ++i) { draw((0,i)--(6,i), grey); draw((i,0)--(i,6), grey); } pen lazer = red+1; for (int i=0; i<=5; ++i) {for (int j=0;j<=5;++j) {if ((i+j)%2==0){draw((i,j+1)--(i+1,j),lazer);}else{draw((i,j)--(i+1,j+1),lazer);}}} picture mark; draw(mark, (-0.2,0)--(0.2,0), black+5); add(shift(1,0)*mark); add(shift(3,0)*mark); add(shift(5,0)*mark); add(shift(2,1)*mark); add(shift(4,1)*mark); add(shift(3,2)*mark);add(shift(3,4)*mark); add(shift(1,6)*mark); add(shift(3,6)*mark); add(shift(5,6)*mark); add(shift(2,5)*mark); add(shift(4,5)*mark); picture mark; draw(mark, (0,-0.2)--(0,0.2), black+5); add(shift(0,1)*mark); add(shift(0,3)*mark); add(shift(0,5)*mark); add(shift(1,2)*mark); add(shift(1,4)*mark); add(shift(2,3)*mark);add(shift(4,3)*mark); add(shift(6,1)*mark); add(shift(6,3)*mark); add(shift(6,5)*mark); add(shift(5,2)*mark); add(shift(5,4)*mark); pen border = black+1.5; draw(box((0,0), (2,1)), border); draw(box((2,0), (4,1)), border); draw(box((4,0), (6,1)), border); draw(box((0,5), (2,6)), border); draw(box((2,5), (4,6)), border); draw(box((4,5), (6,6)), border); draw(box((1,1), (3,2)), border); draw(box((3,1), (5,2)), border); draw(box((1,4), (3,5)), border); draw(box((3,4), (5,5)), border); draw(box((0,1), (1,3)), border); draw(box((0,3), (1,5)), border); draw(box((5,1), (6,3)), border); draw(box((5,3), (6,5)), border); draw(box((1,2), (2,4)), border); draw(box((4,2), (5,4)), border); draw(box((2,2), (4,3)), border); draw(box((2,3), (4,4)), border); [/asy][/asy] This breaks down the lazers into simple loops, so let's also assume that all lazers are travelling clockwise along the loops. Now let's calculate the total turning number. Note that each mirror along the outside perimeter contributes to a quarter-turn clockwise. For the internal mirrors, we can imagine that the two loops reflecting against the mirror are either externally tangent (contributing to a half-turn clockwise overall) or internally tangent (contributing zero turning overall). Hence the total turning number is at least $n$, meaning that there are at least $n$ loops formed. I don't understand how you count the turning number and how you get at least $n$.

Anyone??

Bump :<<<<

Excuse me, but could somebody explain why is the sum of the turning points (in DVD's laser solution) $n$?

@above The total angle those loops rotate (we consider only in clockwise direction) is at least $4n\times \frac{\pi}{2} +0 =2\pi n$ radians. Each loop can create total $2\pi $ radians rotation, so there must be at least $n$ loops.

v_Enhance wrote: Here is the solution from the shortlist packet: The answer is surprisingly small: $2n$. For this problem, having a square (instead of a rectangle) is imperative. First, we give a construction with $2n$ marked squares. Just an example with $n=3$: [asy][asy] size(7cm); for (int i=0; i<=6; ++i) { draw((0,i)--(6,i), grey); draw((i,0)--(i,6), grey); } picture mark; draw(mark, (0,0)--(1,1), grey+1.3); draw(mark, (1,0)--(0,1), grey+1.3); add(shift(0,5)*mark); add(shift(0,4)*mark); add(shift(1,4)*mark); add(shift(1,3)*mark); add(shift(2,3)*mark); add(shift(2,2)*mark); pen border = black+1.5; draw(box((0,0), (2,1)), border); draw(box((2,0), (4,1)), border); draw(box((4,0), (6,1)), border); draw(box((0,5), (2,6)), border); draw(box((2,5), (4,6)), border); draw(box((4,5), (6,6)), border); draw(box((1,1), (3,2)), border); draw(box((3,1), (5,2)), border); draw(box((1,4), (3,5)), border); draw(box((3,4), (5,5)), border); draw(box((0,1), (1,3)), border); draw(box((0,3), (1,5)), border); draw(box((5,1), (6,3)), border); draw(box((5,3), (6,5)), border); draw(box((1,2), (2,4)), border); draw(box((4,2), (5,4)), border); draw(box((2,2), (4,3)), border); draw(box((2,3), (4,4)), border); [/asy][/asy] Now we show this is optimal. The main claim is the following. Lemma: In an arbitrary domino tiling of a $2n \times 2n$ square it is possible to partition the dominoes into several cycles, at least $n$ of which are nontrivial. (A cycle is a $2k$-cycle on the grid which pair off into dominoes, possibly including trivial cycles for which $k = 1$.) Proof. Take the tiling and reflect it across the main diagonal, then overlay it on the original. This gives us a bunch of cycles. Now note every cell on the main diagonal is in a nontrivial cycle, and moreover by symmetry each such cycle has exactly two cells on the main diagonal. $\blacksquare$ Thus, we can take a cycle with at most one marked square and then replace it with the overlaid image. Can you please elaborate a little bit on how you define a cycle? Does it have anything to do with dominoes sharing a side, they are considered adjacent in a cycle? Is this partitioning unique, then?

Just imagine that you place a vertex on each cell and join any two vertices that lie in the same dominoes. If you overlay two such configurations, you will end up with a bunch of cycles.

A similar idea (cycles formed by overlapping two distinct domino tilings) also appeared in USAMO 2009/3.

We claim the answer $k=2n$. Firstly numerate all columns and rows of square consequently by $1,2,\dots ,2n.$ For $i=1,2,\dots,n$ we mark cells $(i,i),(i,i+1)$, so by induction cells $(i,i)$ must be covered by horizontal dominoes, and cells $(i,i+1)$ (except for $i=n$) must be covered by vertical dominoes. Next it's easy to restore uniquely the desired partition; the figure below shows an example for $n=4.$ [asy][asy] unitsize(15); for(int k = 0; k < 4; ++k){ fill((k,k)--(k+1,k)--(k+1,k+2)--(k,k+2)--cycle, grey); } for(int i = 0; i < 9; ++i){ draw((i,0)--(i,8)); draw((0,i)--(8,i)); } for(int j=0; j<4; ++j){ draw((j,j)--(8-j,j)--(8-j,8-j)--(j,8-j)--(j,j),linewidth(1.5)); for(int p = j+2; p <9-j; p=p+2){ draw((p,j)--(p,j+1),linewidth(1.5)); draw((8-p,7-j)--(8-p,8-j),linewidth(1.5)); draw((j,p-1)--(j+1,p-1),linewidth(1.5)); draw((8-j,9-p)--(7-j,9-p),linewidth(1.5)); } } draw((3,4)--(5,4),linewidth(1.5)); [/asy][/asy] Now we will prove, that if $2(n-m)+1$ cells are marked for positive integer $m$, then there are at least $2^m$ different partitions on dominoes, which clearly suffices. Fix some main diagonal of square. Represent cells as vertices of multigraph (black if it is marked, and white otherwise); red edges connect pair of cells, covered by one domino; blue edges connect pair of cells, whose reflections over diagonal are covered by one domino. Each vertex is incident to exactly one red and exactly one blue edge, so we can divide the graph by disjoint cycles with alternating colors of edges. We choose $n$ of them as follows. For $i=1,2,\dots,n$ pick some cell $a_{2i-1}$, which wasn't picked before on the chosen diagonal; note that it is connected with two different cells, therefore it is included in cycle $C_i$, which (due to the symmetry over diagonal) must cross the diagonal by the unique cell $a_{2i}\neq a_{2i-1}$ (which we also pick). By Pigeonhole principle there are $m$ cycles among $C_i$, which contain at most $1$ marked cell. In all such cycles we may swap red and blues edges, which gives $2^m-1$ new partitions. Thus we are done $\blacksquare$

Here is some motivation for the solution: 1. When we see that a 2x2 square has two ways of tiling the domino, we get the "cycle" idea. Shifting the cycle is creates a new valid domino tiling. 2. By looking at the equality case, we can see that there are exactly $n$ cycles (cycles are based on $\max\{ |x-(n+1/2)|, |y-(n+1/2)|\}$ ). This motivates us to prove that there are at most $n$ cycles. 3. We have now arrived at a $n=n$ type problem. In this case it is usually not a good idea to generalize and induct but to see some patterns. In this case, I noticed that either $(1,1)$ and $(2,2)$ are in a 2x2 cycle or they are not in the same cycle. I also realized that in many of the examples I drew, the diagonal cells can be paired so that two cells are in one cycle. Since $y-x$ is a discrete continuous variable, this motivates reflection of the line $y=x$.

The answer is $2n$. First, we prove that if there are less than $2n$ marked cells, then if there exists one partition of the board, there exists a different one. First, we analyze cycles in the board, because cycles can be cyclically shifted. Consider a graph on the squares of the board, such that we draw a red edge between two adjacent squares, such that one domino occupies both those squares. Consider a main diagonal of the square. Reflect the graph across this main diagonal, but color any edge in the reflection blue. We observe that every point has degree two: a red edge and a blue edge. Therefore, our graph can be partitioned into disjoint cycles. We claim that at least $n$ of these cycles have length at least $4$. If a cycle has length two, then it must be a red edge and a blue edge between the same two vertices. Clearly, if one of these vertices is on the main diagonal, then a reflection over that diagonal results in us having a vertex on the main diagonal with degree at least four, contradiction. Therefore, each point on the main diagonal is on a cycle of length at least $4$. Furthermore, it is easy to see that since red-degree and blue-degree are both one, the cycle alternates between red and blue. Suppose there is a cycle that contains more than two points on the main diagonal. Let three of them be $A_1$, $A_2$, $A_3$, in order of appearance on the cycle. The path from $A_1$ to $A_2$ does not cross the main diagonal. Similarly, the path from $A_2$ to $A_3$ does not cross the main diagonal, and it must be a reflection of the path from $A_1$ to $A_2$ because the cycles containing the main diagonal are symmetric about the main diagonal. Thus, $A_3=A_1$, contradiction. Our proof is complete. Consider these $n$ cycles. If only $2n-1$ cells are marked, then some cycle has only one marked cell. Then, consider removing all the dominoes on this cycle, and insteading adding dominoes for blue edges. That's a different tiling. Now, we give a construction for $2n$ working: color $(1,1)$, $(1,2)$, $(2,2)$, $(2,3)$, $\dots$, $(n,n)$, $(n,n+1)$ and it is clear that this works.

Cute. The answer is $2n$. Construction: Color $(1,n),(2,n),(2,n-1) \cdots (n+1,n+1)$ clearly this works. Here is an illustration for $n=4$. [asy][asy] size(200); int rows = 8, cols = 8; fill((0, 7)--(1, 7)--(1, 8)--(0, 8)--cycle, red+white+white); fill((1, 7)--(2, 7)--(2, 8)--(1, 8)--cycle, red+white+white); fill((1, 6)--(2, 6)--(2, 7)--(1, 7)--cycle, red+white+white); fill((2, 6)--(3, 6)--(3, 7)--(2, 7)--cycle, red+white+white); fill((2, 5)--(3, 5)--(3, 6)--(2, 6)--cycle, red+white+white); fill((3, 5)--(4, 5)--(4, 6)--(3, 6)--cycle, red+white+white); fill((3, 4)--(4, 4)--(4, 5)--(3, 5)--cycle, red+white+white); fill((4, 4)--(5, 4)--(5, 5)--(4, 5)--cycle, red+white+white); for (int i = 0; i <= rows; ++i) { draw((0, i)--(cols, i), black); } for (int j = 0; j <= cols; ++j) { draw((j, 0)--(j, rows), black); } [/asy][/asy] Bound: Consider an arbitrary domino tiling of the $2n \times 2n$ board, we claim that we can partition these into atleast $n$ nontrivial cycles, indeed consider the reflection of the tiling across the main diagonal,this paritions the board into several cycles, note that each cycle crosses the main diagonal exactly twice, and now the claim follows. Now, as above, we break our board into several disjoint cycles, if some cycle contains less than $2$ marked squares, reflect over the main diagonal and we get another domino tiling, contradiction, therefore there are atleast $2 \times n = 2n$ marked squares, as claimed. $\blacksquare$