YES W TITLE

I used to wonder how people could predict a 0 on a problem only to get a 7. I don't wonder anymore.

This was both JMO 3 and AMO 3? Wow don't think that's ever happened since 2017

As I said in the JMO thread, this problem is a slightly harder version of J3, as it asks for all values of $k(C)$ instead of just the maximum.

ilovepizza2020 wrote: As I said in the JMO thread, this problem is a slightly harder version of J3, as it asks for all values of $k(C)$ instead of just the maximum. "slightly"

:flushed:

Solved this as a 2nd grader on the USAMO.

dbj2015 wrote: Solved this as a 2nd grader on the USAMO.

Wait u promise no cap? u actually in SECOND GRADE? wow bro is the Luke Robitaille of the 2020s

r00tsOfUnity wrote: dbj2015 wrote: Solved this as a 2nd grader on the USAMO.

Wait u promise no cap? u actually in SECOND GRADE? wow bro is the Luke Robitaille of the 2020s no he's not in second grade this is likely an alt based on the one friend he has and this post of his over a year ago https://artofproblemsolving.com/community/c3h2714268p23602195

r00tsOfUnity wrote: dbj2015 wrote: Solved this as a 2nd grader on the USAMO.

Wait u promise no cap? u actually in SECOND GRADE? wow bro is the Luke Robitaille of the 2020s I promise.

I mean it kind of makes sense given his username which highly suggests he was born in 2015, so if that's true he would be in second grade, unless he was born after September in which case he'd be in first. But he only has four or five posts and one of them about multis looks very sus so idk :shrug: and the other thing that's very sus is that the only user on his friends list is pbj2006

maybe it's his 9 years older brother?

As someone who knows dbj2015 personally I can confirm he is legit

redacted or edited

HOW DOES LIL BRO KNOW WHERE I LIVE

don't reveal people's personal information without consent

hmmt sus

Note that if you impose coordinates on the squares, then sliding leaves the pair $(x,y) \pmod 2$ of the empty square invariant. Call such a square probable. So only dominoes that cover a probable square can ever move, so remove the rest of them, they don't matter. Further, note that any domino covering a probable square has only one other position it can be in (when it moves to cover another probable square). Suppose you fix an empty square, then I claim the configuration of dominoes is fixed. Suppose not, and there are two distinct configurations with the same empty square reachable from one another. Consider the domino that initially takes the place of the empty square. Since the empty square must be vacated again, this domino must move back to original position at some point. But this means the domino that occupied the square before it must now move back. Repeating this argument gives that any domino that moved out of its position must go back, so the configurations could not have been distinct. (You could also have started the graph theory now and proved this, but eh) Let $n = 2k+1$. Consider a graph on the probable vertices with an edge iff there is a domino that can slide between them. A square can be made empty only if there is a path from it to the empty square via the graph. Further, note that the graph satisfies the property that you can assign edges to all but one vertex such that the edge emanates from the vertex (in the $(k+1)^2$ case). Note that (by chessboard coloring), the probable vertices can only either be the outer $(k+1)^2$ or the inner $k^2$ cells. I claim $k(C)$ takes every value from $1$ to $k^2$, along with $(k+1)^2$. Clearly $k(C)$ just counts the possible number of squares that can be made vacant, and this corresponds to the number of vertices reachable through the graph from the empty square. Therefore, this is clearly at most $k^2$ if we use the inner $k^2$ cells. Suppose we use the outer $(k+1)^2$ cells. For there to be less than all the vertices reachable, the graph must be disconnected, say there are two components $A$, which contains the empty square, and $B$, which does not. Since $B$ is a separate connected component that does not contain the empty square, we can pair every edge with some vertex, so there are at least $|B|$ edges in this subgraph. But this means that there must be some cycle within $B$ itself, which I claim is impossible. This is because it can be shown by induction that any cycle of dominoes in a grid must enclose an odd area within, and so cannot be tiled by dominoes unless there is an empty square, therefore the cycle in $B$ encloses the empty square. This means that $|A|$ is bounded by the area within the $B$-cycle, which is at most $(k+1)^2 - 4k = (k-1)^2 < k^2$, so you can't have anything in between $k^2$ and $(k+1)^2$ It then suffices to show the constructions for those values. For $(k+1)^2$, we can just ensure the empty square is on the border and so is not within any cycle, so every vertex must be reachable (which is in fact a Russia problem). For $k^2$, place the empty square somewhere within and create a tree on the graph. Note that in the $k^2$ vertices graph, in the pairing of edges and vertices, the vertices on the border need not satisfy the property, so use this to cut off some region which has edges only within itself to achieve any value in between (unrigorous, but easy to see if you try it). So we're done: the answer is that for $n = 2k+1$, $k(C)$ can take any value in $\{1,2,3,\cdots,k^2,(k+1)^2\}$

Let $n=2k+1$. The answer is $1,2,\dots , k^2,(k+1)^2$. Color each $2 \times 2$ with $1,2,3,4$ such that corners are $1$'s, as shown below. Note the hole always moves $2$ squares at a time, so it always stays on the same number. Moreover, it must start on either $1$ or $3$ by checkerboard coloring. Color a cell green if it has the same number as the hole; if $1$ is green then color all $3$'s red, and vice versa. Call a domino alive if it can ever move (these must all contain a green cell), dead if it contains a red cell (so can't move), and a zombie if it contains a green cell but still can't ever move. Notice that zombies never touch life, even if it's just at a corner, or else life would infect the zombie. Also note all life is connected. Claim: Given a starting position, the position of the hole determines the entire configuration (so $k(C)$ is just the number of possible hole positions). Proof: Notice that dominoes can only move into green cells, so any alive domino only has two places it can live. Observe that if two alive dominoes are touching (possibly at a corner) and I know where one of them is, and I also know where the hole is, then I also know where the other one is. Since all life is connected, this means that knowing where the hole is will force the location of every alive domino. Case 1: $3$ is green. There are a total of $k^2$ green cells, and we can indeed achieve everything from $1$ through $k^2$, with the below easily generalizable construction: (red dominoes are dead, stars are live green cells) Case 2: $1$ is green. There are $(k+1)^2$ green cells, and I claim that if more than $k^2$ of them are alive, then all of them must actually be alive, i.e. there are no zombies. Change the grid to be $(2k+3) \times (2k+3)$ by padding it with border of dominoes; note the border consists of all dead dominoes. Also, in order to have more than $k^2$ living green cells, life must extend all the way to touch this border. Assume for contradiction there's a zombie. Note that every zombie points to the green cell of another zombie (since zombies can't touch life). Following these pointers around, we don't ever run into the border since it's just a pad of dead cells, so we must eventually end up with a loop of zombies. Note that life cannot be contained inside this loop of zombies, or it couldn't extend all the way out to touch the dead border pad. Moreover, since every zombie is adjacent to two red cells on either side, there must be a red cell inside the loop of zombies. So there must be a dead cell inside the loop of zombies. Now similarly, note every dead domino points to the red cell of another dead domino. Take the dead domino we know exists inside the zombie loop, and follow the pointers around; we don't ever run into border issues since we're already contained inside a loop of zombies, so we must eventually end up with a dead loop inside the zombie loop. Since every dead domino is adjacent to two green cells on either side, there must exist a green cell inside this dead loop. This green cell cannot be alive, since we know there's no life inside the original zombie loop. So there must be a zombie inside the dead loop. But now we can repeat this argument indefinitely, generating indefinite numbers of concentric zombie loops and dead loops. This is clearly a contradiction. So our assumption that there existed a zombie must have been incorrect. Finally, note that $(k+1)^2$ can indeed be achieved as shown.

v_Enhance wrote: L567 wrote: Isn't this false? The interior need not be tiled by dominoes if there is an empty square within. It only works for the Russia problem because we're given the empty square is initially on the border, so no cycles can surround it. But for example, in a $5 \times 5$ grid, the entire border may compose a cycle, which is valid. Ah yeah, you're right. Too sucked in by the Russia problem. Will fix, thanks. Ah good thing I thought of this in contest, you can repair (in the $((n+1)/2)^2$ construction at least) by noting that there wouldn't be enough empty squares inside the cycle.

Note that $k(C){}$ counts the total number of possible positions of the empty cell, after sliding some dominoes. Let $\text{Spec}(C)$ be the set of positions of empty cells achievable by sliding dominoes starting with the configuration $C{}$. We want to compute the possibilities for $|\text{Spec}(C)|$. Firstly, let's see which of the cells on the board may be empty at all. To the cell $(a,b)$ assign the value $(-1)^{a+b}$. The sum of the numbers in the board is $1$ while the sum on each domino is $0{}$, hence the empty cell must be one with both coordinates of the same parity. Secondly, notice that after sliding a domino, the coordinates of the empty cell remain unchanged modulo $2{}$. Letting $n=2k+1$, it follows that $\text{Spec}(C)$ is either a subset of the $(k+1)^2$ cells with odd coordinates (in blue below), or of the $k^2$ cells with even coordinates (in red below). [asy][asy] import olympiad; import geometry; blue=RGB(212,227,255); red=RGB(237,158,160); void red(pair A) { fill(A--(A+(1,0))--(A+(1,1))--(A+(0,1))--cycle,red); } void blue(pair A) { fill(A--(A+(1,0))--(A+(1,1))--(A+(0,1))--cycle,blue); } blue((0,4)); blue((0,2)); blue((0,0)); blue((2,4)); blue((2,2)); blue((2,0)); blue((4,4)); blue((4,2)); blue((4,0)); red((1,3)); red((1,1)); red((3,3)); red((3,1)); for(int i=0;i<=5;i+=1){ draw((i,0)--(i,5)); draw((0,i)--(5,i)); } [/asy][/asy] The first case: Let's suppose that $\text{Spec}(C)$ is a subset of the $k^2$ red cells. We will show that $|\text{Spec}(C)|$ may take any value in $1,2,\ldots k^2$. Consider the spiral of dominoes, that starts to the very right of the cell $(2,2)$ and passes through all the red cells. Of course, for this configuration, we have $|\text{Spec}(C)|=k^2$. In order to get any smaller value for $|\text{Spec}(C)|$, we simply cut the spiral with a perpendicular domino. [asy][asy] import olympiad; import geometry; blue=RGB(212,227,255); red=RGB(237,158,160); green=RGB(133,238,159); void red(pair A) { fill(A--(A+(1,0))--(A+(1,1))--(A+(0,1))--cycle,red); } void blue(pair A) { fill(A--(A+(1,0))--(A+(1,1))--(A+(0,1))--cycle,blue); } void green(pair A) { fill(A--(A+(1,0))--(A+(1,1))--(A+(0,1))--cycle,green); } void yellow(pair A) { fill(A--(A+(1,0))--(A+(1,1))--(A+(0,1))--cycle,gray(0.9)); } for(int i=0;i<=4;i+=1){ for(int j=0;j<=4;j+=1){ yellow((i,j)); } } red((1,3)); green((2,3)); green((3,3)); green((3,2)); green((3,1)); green((2,1)); green((1,1)); draw((0,0)--(0,5)); draw((1,1)--(1,5)); draw((2,0)--(2,1)); draw((2,3)--(2,4)); draw((3,1)--(3,3)); draw((3,4)--(3,5)); draw((4,0)--(4,4)); draw((5,0)--(5,5)); draw((0,0)--(5,0)); draw((0,1)--(4,1)); draw((1,2)--(3,2)); draw((4,2)--(5,2)); draw((0,3)--(4,3)); draw((1,4)--(5,4)); draw((0,5)--(5,5)); label("$D_1$", (2, 1.5)); label("$D_2$", (3.5, 2)); label("$D_3$", (3, 3.5)); [/asy][/asy] The second case: Let's suppose that $\text{Spec}(C)$ is a subset of the $(k+1)^2$ red cells. By taking a spiral analogous to that of the previous case, it is possible to have $|\text{Spec}(C)|=(k+1)^2$, but this time we cannot cut the spiral like before. We will prove that if $|\text{Spec}(C)|\geqslant k^2+1$ then $|\text{Spec}(C)|=(k+1)^2$. We say that a domino $D{}$ points to another domino $D'$ if the common edge between $D{}$ and $D'$ is that of a red cell. We write this as $D\to D'$. For instance, in the figure from case one, $D_1\to D_2\to D_3$. Suppose that $|\text{Spec}(C)|\neq(k+1)^2$. Then, there exist some dominoes which are locked, that is they form a cycle $D_1\to D_2\to \cdots\to D_k\to D_1$. It can be shown inductively that the interior spanned by the domino chain has an odd area, hence the empty cell must lie inside it. Then, for this configuration $C{}$, $\text{Spec}(C)$ is a subset of the cells inside the chain of dominoes, so $|\text{Spec}(C)|\leqslant k^2$ which is a contradiction to our assumption. This concludes the second case. Therefore, the only values $|\text{Spec}(C)|$ can take are $1,2,\ldots,k^2$ and $(k+1)^2$.

Outline of my solution: 1. Clearly only squares with both odd coordinates can be reached, this gives an upper bound of $\frac{(n+1)^2}{4}$. 2. Now, each domino cannot change orientation and thus, the previous argument shows that the domino is restricted to three squares. 3. If at some state some square $a$ is blank. Then, if we want to find the position of a domino $D$, which is 'slidable' then clearly, there must be a sequence of moves to change the position of domino $D$, so their should be a path of 'slidable' dominos connecting $a$ to $D$. But then, the fact that $a$ is blank should inductively fix the position of all dominoes along this path. Note: A 'slidable' domino is one which can change its position at some time in the game. Does this work?

everythingpi3141592 wrote: Outline of my solution: 1. Clearly only squares with both odd coordinates can be reached, this gives an upper bound of $\frac{(n+1)^2}{4}$. 2. Now, each domino cannot change orientation and thus, the previous argument shows that the domino is restricted to three squares. 3. If at some state some square $a$ is blank. Then, if we want to find the position of a domino $D$, which is 'slidable' then clearly, there must be a sequence of moves to change the position of domino $D$, so their should be a path of 'slidable' dominos connecting $a$ to $D$. But then, the fact that $a$ is blank should inductively fix the position of all dominoes along this path. Note: A 'slidable' domino is one which can change its position at some time in the game. Does this work? have you shown that there cannot be more than one configuration for a given empty square?

MathWizard10 wrote: everythingpi3141592 wrote: Outline of my solution: 1. Clearly only squares with both odd coordinates can be reached, this gives an upper bound of $\frac{(n+1)^2}{4}$. 2. Now, each domino cannot change orientation and thus, the previous argument shows that the domino is restricted to three squares. 3. If at some state some square $a$ is blank. Then, if we want to find the position of a domino $D$, which is 'slidable' then clearly, there must be a sequence of moves to change the position of domino $D$, so their should be a path of 'slidable' dominos connecting $a$ to $D$. But then, the fact that $a$ is blank should inductively fix the position of all dominoes along this path. Note: A 'slidable' domino is one which can change its position at some time in the game. Does this work? have you shown that there cannot be more than one configuration for a given empty square? I said that every domino which can change position at some instance in the game has its position uniquely determined by the blank square since there is a sequence of domino moves untill we change the position of the domino we are talking about As for dominoes which cannot change position at any instance of the game, their position is fixed.

Show that the graph is acyclic and then do the stuff from there to solve

Thank you Google Sheets for finally allowing me to solve this problem. The answer is $\left[1,\frac{(n-1)^2}{4}\right]\cup \left\{m=\frac{(n+1)^2}{4}\right\}$. The constructions for $k(C)=8,k(C)=16$ when $n=7$ are attached which readily generalize in a way that's unintuitive without the first part of the solution but whatever To show that no other answers are possible: let the center of some corner be $(0,0)$, then color the cells by the parity of the $x$ and $y$ coordinates of their centers. Note that the empty cell will always be the same color. Then, we also know that each domino can only move between 2 possible positions, since otherwise we must be able to vacate two cells that have distance 3, and hence different colors, impossible. Then, draw a graph $G$ where each vertex corresponds to a cell with two even coordinates and each edge corresponds to a domino containing one vertex and adjacent to another, joining these two vertices. It has $m$ vertices and either $m$ or $m-1$ edges, the latter case possible if a vertex starts as the empty cell. Key claim: Suppose $G$ contains a cycle; then, it has an odd number of cells in its interior. Proof: Let $H$ be the closed, connected, simple region exclusively enclosed by the cycle, and let $H'$ be the region enclosed by connecting each vertex. Moreover, suppose the cycle initially contains $d$ edges, and hence $d$ dominoes. Then, note that for each cell in the boundary of the cycle, its contribution to the quantity $[H']-[H]$ is 0.75 if its a right exterior angle, 0.25 if its a right interior angle, and 0.5 otherwise. Since there are 4 more right interior angles than right exterior ones, we have $$[H]=[H']-d+1$$By the Shoelace Theorem, $[H']$ is even, and furthermore any two adjacent vertices in $G$ must have different sums of coordinates mod 4, so $d$ is even, and consequentially $[H]$ is odd. $\blacksquare$ If $G$ is acyclic, it must be a spanning tree and the empty cell is a vertex. By traversing the tree, we can obtain one unique configuration for each possible empty cell, obtaining $m$ possible configurations. Otherwise, the empty cell lies in the interior of some cycle. We can draw graph $G'$ in a similar manner to $G$ on cells at even $x$ and $y$ distance from the empty cell inside the cycle. The connected component of $G'$ containing the empty cell must then contain one less edge than vertex, hence it is also a tree, and there is one unique configuration for each possible empty cell. In this case, the number of possible empty cells is at most $\frac{(n-1)^2}{4}$ since no cell along the perimeter of the board can be inside the cycle. Since we have exhausted all cases, our answer set is complete. $\whitesquare$

Well it turns out I got a 4 on this problem so I am currently writing this solution from CMU. The solution below is a fairly natural extension of what I wrote in-contest, but (hopefully) phrased and explained much better. A surprising amount of the math content has been tweaked over time since the original thought process did not make too much sense. I am fairly confident that this is completely correct but I would not be surprised to find another hole: it would be far from the first time. I was going to write this up much, much earlier, but I was worried about the effect that posting a solution might have on my score. On one hand, if what I wrote in-contest was a mostly complete solution, posting it here might have resulted in a grader reading the solution and realizing my submission's errors. On the other hand, if what I wrote in-contest was only the beginnings of a valid proof, perhaps the grader would not have believed it to be possible to finish, and reading my solution would demonstrate that this was in fact possible. I am told that this is a somewhat infamous story among certain math competition circles. Of course, that is no longer an issue, so we may begin. We replace $n$ with $2n+1$, so we will have $2n^2+2n$ dominoes. In this case, the answer is $$k(C) \in \{1,2,\ldots,(n-1)^2,n^2\}.$$Number the grid as follows: [asy][asy] for(int i=0;i<6;++i) { draw((i,0)--(i,5)); draw((0,i)--(5,i)); } for(int i=0;i<5;++i) { for (int j=0;j<5;++j) { label("$"+string(i%2+1+(3-2*(i%2))*(j%2))+"$",(i+0.5,j+0.5)); } } [/asy][/asy] At any point, call the cell not covered by a domino removed, and say that a cell in a configuration is removable if it is possible to have it removed at some point by shifting dominoes around. Observe that all removable cells in a configuration must have the same label, and that if there is more than one removable cell, every removable cell is two cells away from another one, either vertically or horizontally. We now prove the following key lemma, which will be extremely important. Here, and throughout the rest of the solution, we will use the simple fact that if a domino $d$ covers a removable cell $c$ and therefore a non-removable cell $c'$, then when it moves, it must do so by moving off of $c$ (staying on $c'$), otherwise after moving $c'$ will be removed, but this is not allowed. This will be referred to as "fact 6". Lemma 1 (Basically USAJMO 2023/3): The value of $k(C)$ equals the number of removable cells. Equivalently, the removed cell obtained from a fixed starting configuration uniquely determines the rest of the configuration. Proof: It is sufficient to prove that, starting from a configuration where cell $c$ is removed, if $n>0$ moves are performed such that cell $c$ is removed after these moves, then the configurations are identical. This is by strong induction on $n$, with the base cases of $n=1$ being vacuously true and $n=2$ being obvious. For the inductive step, suppose that in the first move we slide domino $d$ onto $c$, making the cell $c'$ removed. For $c$ to be removed eventually, domino $d$ must be moved again, which by fact 6 can only occur by having it slide off $c$ in the opposite direction it first moved in. Consider when this first occurs. If the first occurrence is before the $n$-th move, split the sequence of moves into two smaller ones at this first occurrence and simply apply the inductive hypothesis. Otherwise, the first occurrence is the $n$-th move, where $d$ moves from $c'$ onto $c$. By inductive hypothesis to the sequence of moves formed by deleting the first and last from the original, the configurations after the first and before the $n$-th move (where $c'$ is removed) are identical, hence the first and last configurations are also clearly identical. $\blacksquare$ This lemma is sufficient to imply that $k(C) \leq n^2$, since the most frequent label ($1$) occurs exactly $n^2$ times. Using our lemma, we will now provide constructions. To see that $k(C)=n^2$ is possible, employ the following easily generalizable construction, where every cell labeled $1$ is removable. [asy][asy] for(int i=0;i<6;++i) { draw((i,0)--(i,5)); draw((0,i)--(5,i)); } for(int i=0;i<5;++i) { fill((i+0.1,3.1)--(i+0.9,3.1)--(i+0.9,4.9)--(i+0.1,4.9)--cycle,red); fill((i+0.1,1.1)--(i+0.9,1.1)--(i+0.9,2.9)--(i+0.1,2.9)--cycle,red); } fill((0.1,0.1)--(0.1,0.9)--(1.9,0.9)--(1.9,0.1)--cycle,blue); fill((2.1,0.1)--(2.1,0.9)--(3.9,0.9)--(3.9,0.1)--cycle,blue); [/asy][/asy] Now, to prove that $k(C) \leq (n-1)^2$ are all possible, we employ the following construction: write $k(C)=a(n-1)+b$ where $0 < b \leq n-1$, so $a \leq n-2$. Then create $2a$ columns of $n-1$ vertical dominoes, all next to each other, and then a final column to its right with $b$ dominoes. Finally, add $a$ horizontal dominoes to the base of the shape. For $n=4$ and $k(C)=7$ (so $(a,b)=(2,1)$), the shape will look like this: [asy][asy] for(int i=0;i<4;++i) { fill((i+0.1,5.1)--(i+0.9,5.1)--(i+0.9,6.9)--(i+0.1,6.9)--cycle,red); fill((i+0.1,3.1)--(i+0.9,3.1)--(i+0.9,4.9)--(i+0.1,4.9)--cycle,red); fill((i+0.1,1.1)--(i+0.9,1.1)--(i+0.9,2.9)--(i+0.1,2.9)--cycle,red); } fill((4.1,1.1)--(4.9,1.1)--(4.9,2.9)--(4.1,2.9)--cycle,red); fill((0.1,0.1)--(0.1,0.9)--(1.9,0.9)--(1.9,0.1)--cycle,blue); fill((2.1,0.1)--(2.1,0.9)--(3.9,0.9)--(3.9,0.1)--cycle,blue); [/asy][/asy] We then surround this shape with dominoes, essentially locking it inside. To do this, we first prove that this is doable for $b=n-1$, which is with the following easily generalizable construction: [asy][asy] for(int i=0;i<5;++i) { fill((i+0.1,5.1)--(i+0.9,5.1)--(i+0.9,6.9)--(i+0.1,6.9)--cycle,red); fill((i+0.1,3.1)--(i+0.9,3.1)--(i+0.9,4.9)--(i+0.1,4.9)--cycle,red); fill((i+0.1,1.1)--(i+0.9,1.1)--(i+0.9,2.9)--(i+0.1,2.9)--cycle,red); } fill((0.1,0.1)--(0.1,0.9)--(1.9,0.9)--(1.9,0.1)--cycle,blue); fill((2.1,0.1)--(2.1,0.9)--(3.9,0.9)--(3.9,0.1)--cycle,blue); fill((-0.9,-0.9)--(-0.9,-0.1)--(0.9,-0.1)--(0.9,-0.9)--cycle,green); fill((1.1,-0.9)--(1.1,-0.1)--(2.9,-0.1)--(2.9,-0.9)--cycle,green); fill((3.1,-0.9)--(3.1,-0.1)--(4.9,-0.1)--(4.9,-0.9)--cycle,green); fill((0.1,7.1)--(0.1,7.9)--(1.9,7.9)--(1.9,7.1)--cycle,green); fill((2.1,7.1)--(2.1,7.9)--(3.9,7.9)--(3.9,7.1)--cycle,green); fill((4.1,7.1)--(4.1,7.9)--(5.9,7.9)--(5.9,7.1)--cycle,green); fill((5.1,-0.9)--(5.9,-0.9)--(5.9,0.9)--(5.1,0.9)--cycle,green); fill((5.1,1.1)--(5.9,1.1)--(5.9,2.9)--(5.1,2.9)--cycle,green); fill((5.1,3.1)--(5.9,3.1)--(5.9,4.9)--(5.1,4.9)--cycle,green); fill((5.1,5.1)--(5.9,5.1)--(5.9,6.9)--(5.1,6.9)--cycle,green); fill((-0.9,6.1)--(-0.1,6.1)--(-0.1,7.9)--(-0.9,7.9)--cycle,green); fill((-0.9,4.1)--(-0.1,4.1)--(-0.1,5.9)--(-0.9,5.9)--cycle,green); fill((-0.9,2.1)--(-0.1,2.1)--(-0.1,3.9)--(-0.9,3.9)--cycle,green); fill((-0.9,0.1)--(-0.1,0.1)--(-0.1,1.9)--(-0.9,1.9)--cycle,green); [/asy][/asy] Then, delete the red dominoes on the rightmost row one by one, starting from the top. The top right corner can then be "folded" inwards, keeping the rest of the dominoes locked, as shown: [asy][asy] for(int i=0;i<5;++i) { if (i<4) fill((i+0.1,5.1)--(i+0.9,5.1)--(i+0.9,6.9)--(i+0.1,6.9)--cycle,red); fill((i+0.1,3.1)--(i+0.9,3.1)--(i+0.9,4.9)--(i+0.1,4.9)--cycle,red); fill((i+0.1,1.1)--(i+0.9,1.1)--(i+0.9,2.9)--(i+0.1,2.9)--cycle,red); } fill((0.1,0.1)--(0.1,0.9)--(1.9,0.9)--(1.9,0.1)--cycle,blue); fill((2.1,0.1)--(2.1,0.9)--(3.9,0.9)--(3.9,0.1)--cycle,blue); fill((-0.9,-0.9)--(-0.9,-0.1)--(0.9,-0.1)--(0.9,-0.9)--cycle,green); fill((1.1,-0.9)--(1.1,-0.1)--(2.9,-0.1)--(2.9,-0.9)--cycle,green); fill((3.1,-0.9)--(3.1,-0.1)--(4.9,-0.1)--(4.9,-0.9)--cycle,green); fill((0.1,7.1)--(0.1,7.9)--(1.9,7.9)--(1.9,7.1)--cycle,green); fill((2.1,7.1)--(2.1,7.9)--(3.9,7.9)--(3.9,7.1)--cycle,green); fill((4.1,5.1)--(4.1,5.9)--(5.9,5.9)--(5.9,5.1)--cycle,green); fill((5.1,-0.9)--(5.9,-0.9)--(5.9,0.9)--(5.1,0.9)--cycle,green); fill((5.1,1.1)--(5.9,1.1)--(5.9,2.9)--(5.1,2.9)--cycle,green); fill((5.1,3.1)--(5.9,3.1)--(5.9,4.9)--(5.1,4.9)--cycle,green); fill((4.1,6.1)--(4.9,6.1)--(4.9,7.9)--(4.1,7.9)--cycle,green); fill((-0.9,6.1)--(-0.1,6.1)--(-0.1,7.9)--(-0.9,7.9)--cycle,green); fill((-0.9,4.1)--(-0.1,4.1)--(-0.1,5.9)--(-0.9,5.9)--cycle,green); fill((-0.9,2.1)--(-0.1,2.1)--(-0.1,3.9)--(-0.9,3.9)--cycle,green); fill((-0.9,0.1)--(-0.1,0.1)--(-0.1,1.9)--(-0.9,1.9)--cycle,green); [/asy][/asy] This can be repeated again and again, each time folding in the "lower" top right corner, until we are left with $b=1$. Finally, observe that this shape will be, in any column, an odd number at most $2(n-1)+3=2n+1$ tall, so we may place this in the bottom-left corner of the grid and fill the rest with vertical dominoes. This covers $k(C) \leq n-1$. We now prove that $(n-1)^2<k(C)<n^2$ is impossible. Note that if $k(C)>(n-1)^2$, then the removable cells must be labeled $1$, and at least one of the cells on the edge of the grid must be removable, since otherwise we do not have enough cells. Now, construct a grid polygon $\mathcal{P}$ as follows: first, add every removable cell to $\mathcal{P}$. Then, if a cell is between two removable cells, add it to $\mathcal{P}$ as well. Finally, if a cell shares all four edges with $\mathcal{P}$, add it to $\mathcal{P}$. Because every removable cell is two units away from another, $\mathcal{P}$ will actually be a polygon (as opposed to, say, the union of disjoint polygons). Consider every cell labeled $1$ which is not removable and construct a graph $G$ on them, connecting two with an edge if they are two units apart. We will prove the following two key claims, which are very similar and should be thought of as two cases of the same result: Claim 1: Suppose we repeat the construction process for $\mathcal{P}$, this time on every $1$-labeled cell except for those in an arbitrary connected component $\mathcal{C}$ of $G$ (previously, our set was the removable cells) which contains some but not every cell on the edge, to form $\mathcal{T}$. Then there will be exactly one more even-label cell bordering $\mathcal{T}$ but not contained within it than odd-label cell. Also, every even-label cell on the border is adjacent to a removable cell in $\mathcal{T}$. Proof: We will use induction. This can be viewed as essentially starting off with every cell removable, and then changing some cells to non-removable (which will form $\mathcal{C}$). First, to handle the base cases, we consider the cases where $\mathcal{C}$ is a single corner cell or a single non-corner edge cell, both of which are apparent. For the inductive step, it suffices to prove that an equal change in number of odd-label and even-label cells bordering $\mathcal{T}$ occurs when we do one of the following: Add one non-corner edge cell to $\mathcal{T}$ which becomes connected to exactly one edge (possible corner) cell (in the connected component) Add one corner cell to $\mathcal{T}$ which becomes connected to exactly one non-corner edge cell (in the connected component) Add one non-edge cell adjacent to exactly one cell (either edge or non-edge) Add one non-edge cell adjacent to exactly two cells which are not "diametrically opposed" (i.e. whose centers are not collinear with the added cell) Add one non-edge cell adjacent to exactly three cells Once again, it is very easy to verify that these all work (just use a diagram). Then, to achieve an arbitrary connected component $\mathcal{C}$, we begin with a suitable base case and apply the first two inductive steps repeatedly to add every point on the border in $\mathcal{C}$. Then, we apply the third, fourth, or fifth bullet points repeatedly from the bottom of the grid towards the top, and within each row moving from the left to the right to reach $\mathcal{C}$ itself, completing the induction. $\blacksquare$ Claim 2: Suppose we repeat the construction process for $\mathcal{P}$, this time on every $1$-labeled cell except for those in an arbitrary connected component $\mathcal{C}$ of $G$ (previously, our set was the removable cells) which contains every cell on the edge, to form $\mathcal{T}$. Then there will be exactly the same number of even-label and odd-labeled cells bordering $\mathcal{T}$ but not contained within it, and there is one more even-label cell not in $\mathcal{T}$ than odd-label cell. Also, every even-label cell on the border is adjacent to a removable cell in $\mathcal{T}$. Proof: This is once again by induction, employing the same strategy, with the obvious base case where $C$ is a single non-edge cell. For the inductive step, we have the following three cases: Add one non-edge cell adjacent to exactly one cell (either edge or non-edge) Add one non-edge cell adjacent to exactly two cells which are not "diametrically opposed" (i.e. whose centers are not collinear with the added cell) Add one non-edge cell adjacent to exactly three cells The verification for these is the same process as before (except we also count total cells which is easy too). Then, to achieve $\mathcal{C}$, we begin with the lowest cell in $\mathcal{C}$ as base case, and if there are multiple pick the leftmost, and again add cells from bottom up, left to right. This completes the induction. $\blacksquare$ Now we deal with every connected component simultaneously. Construct a graph $G'$ on the connected components of $G$, drawing an edge between two connected components if two of their cells are diagonally two apart. Note that two connected components with an edge between each other share a single corner and are otherwise not only disjoint but also separated by $\mathcal{P}$. Furthermore, $G'$ is cycle-free, since otherwise $\mathcal{P}$ is disconnected, hence it is a forest. Now, orient each edge in $G$ such that $v \to w$ happens if the domino covering the shared cell between $v$ and $w$ lies completely in $w$. We will need the following independent lemma: Lemma 2: If the edges of a tree are oriented, some vertex has all of its edges pointing inwards. Proof: Induct on the number of vertices, with small cases being clear. For the inductive step, consider a leaf of the tree. If the unique edge of that leaf points towards it, we are done, else delete the tree and its edge and induct down. $\blacksquare$ This implies that some connected component $\mathcal{C}$ exists such that any dominoes which overlap with other connected components are actually fully contained in $\mathcal{C}$. This implies that we may readily apply either claim 1 or claim 2 to $\mathcal{C}$, depending on its properties, since the other connected components no longer matter. If claim 1 is applied, this means that we cannot cover every cell bordering $\mathcal{P}$ (but not within it) with dominoes that don't cover cells not bordering $\mathcal{P}$: some domino $d$ covering an even-label cell $c$ bordering $\mathcal{P}$ must either contain some cell in $\mathcal{P}$, or some cell not in $\mathcal{P}$ and not bordering it either; call this point $c'$, and let its reflection over $c$ be $c''$. Then $c'$ is removable in the first case and $c''$ is removable in the second. If the former case holds, rearrange the configuration $C$ such that $c'$ becomes removed. At some point, $d$ must be slid off $c'$, and by fact 6 it remains on $c$ when this occurs. Therefore, the move right before $d$ is slid off, $c''$ must be removed, but it is not in $\mathcal{P}$: contradiction. If the latter case holds, rearrange the configuration $C$ such that $c''$ becomes removed. If $d$ is slid off $c'$ at some point, then we obtain a contradiction, since $c'$ is not removable. Otherwise, after $c''$ becomes removed, $d$ cannot have moved, so it can be slid into $c''$, making $c'$ removed: also a contradiction. If claim 2 is applied, but there exists some domino $d$ covering exactly one even-label cell $c$ bordering $\mathcal{P}$, the same reasoning as before applies. Otherwise, the interior of $\mathcal{C}$, i.e. the shape obtained by removing its border cells, has an odd number of cells in it, since we removed an even number of cells on the border. However, no domino can cover this interior and the border, nor can it cover the interior and $\mathcal{P}$, so some cell in the interior must be unoccupied, meaning it is removable: this is a contradiction, since it is not in $\mathcal{P}$. By combining these two cases, we eliminate the possibility that $(n-1)^2 < k(C) < n^2$, so the answer is exactly what was given. We are done. $\blacksquare$

Indeed, the story of this solution is very notorious, with a certain roommate deciding to not force IAmTheHazard to write-up his ideas before witnessing IAmTheHazard nearly fall off of his bed at 3 AM. Said roommate is very glad that IAmTheHazard has completed his proof.

The power of bad writeups. Let $n = 2a + 1$. We claim that the image of $k(C)$ is $\{0, 1, \dots, a^2\} \cup \{(a+1)^2\}$. Claim: A config slided from an initial $C$ is uniquely identifiable by its empty square. Proof. FTSOC supposed not. Then it must follow that the empty square can travel a cycle, moving two at a time. Take the smallest disjoint cycle $C$ starting and ending at the same point. However, going to the next square in the cycle is only possible if that square is initially covered. This is impossible for the starting square. $\blacksquare$ Claim: $k(C) = \{0, 1, \dots, a^2\}$ is achievable. Proof. Take an outside loop of the entire grid and fill it with dominos. Then make a snake through it in the remaining $(n-2) \times (n-2)$ square, blocking it off early with a domino. Details are slightly more annoying. $\blacksquare$ Claim: If $k(C) > a^2$, then $k(C) = (a+1)^2$. Proof. Note that by a checkerboard coloring it follows that the empty square has coordinates with the same parity. This corresponds to the case of having odd parity. Consider the grid of size $(a+1) \times (a+1)$ between odd coordinate squares. Suppose that $m$ and $n$ are two adjacent vertices of the grid, and $x$ lies between them. If the domino through $x$ goes through $m$ or $n$, being at $m$ allows for movement toward $n$ and vice versa. Else, the domino goes through one of the centers with both even coordinates. Connect two vertices in the first case. FTSOC suppose that the grid is disconnected. Let $C$ be the connected component through the top left corner. Color all squares in the grid with one vertex in $C$ green, and take the border path of the squares, extended to hit the edges of the grid. Then this border path passes through $N$ even centers, but $N + 1$ edges that need to be destroyed by these centers, which is a contradiction by pigeonhole. $\blacksquare$

Solved with a 5x5 Rubik's Cube (yes, the physical thing). The answer is $k(C)\in \{1,\dots,m^2\}\cup\{(m+1)^2\}$ where $n=2m+1$. We assign colours to the squares of the $n\times n$ grid as follows: Red, if the square is under a domino that can never move. Yellow, if the square can ever be the empty square. Blue, if the square is under a domino that can move, but can never be the empty square. The Rubik's Cube was used to analyse the 5x5 case with these colours as I did not have paper. We make a number of observations: All the yellow squares are the same parity $(\bmod\ 2, \bmod\ 2)$. If a set of dominoes $d_1$ through $d_j$ forms a cycle where $d_i$ "points" to $d_{i+1}$ (indices mod $j$), then the area inside the cycle is odd. This is a consequence of Pick's theorem as proven in other solutions in this thread. Consider the graph formed by the yellow and blue squares. It must be connected. If it has a cycle, then the interior has odd area but must be completely filled with dominoes, which is a contradiction. Thus it is not, and therefore a tree. $k(C)$ is the number of yellow squares, as every yellow square can be unoccupied in a unique way. Suppose that the red dominoes form a cycle. Then the interior has odd area, which means that the empty square must always stay inside. So the entire yellow/blue configuration of squares is completely contained in the interior. Now we prove that $k(C)$ must be within the set described at the start of the solution. If $k(C)>m^2$, then the yellow squares must be the same parity as the corner squares. If there exists a red cycle, then the yellow squares must be completely contained inside, so none of the yellows can be on the perimeter. There are at most $(m-1)^2$ yellow squares now. If there exists no red cycle, suppose that there is a red square which is the same parity as the corner. Now from this domino, consider what it's pointing to, which must be a new red square as it should not be able to move. But repeating this process, we can never actually stop as we can't point to the outside of the square. Thus there must exist no red squares on that parity, i.e. there are $(m+1)^2$ yellow squares (since all the blue squares are also on different parity. It just remains to construct. For $(m+1)^2$ create an arbitrary tree on the yellow vertices and fill the rest with dominoes; choose an arbitrary yellow square to be empty and place uniquely the remaining dominoes. For $k(C)\leq m^2$, let it equal to $mr+s$ where $0\leq s<m$. Now on the opposite parity from the corner, choose $r$ full rows of yellow squares and $s$ additional ones. Around the perimeter of this shape, lay down red dominoes. Now the yellow squares are the only possible yellow squares, and we can perform the same process as above to make all yellow squares reachable. Finally, on the exterior, fill everything arbitrarily with red dominoes. This completes the construction.

that's probably allowed on the test right

Let $n=2m+1$. Notice that after a number of moves if the empty square is in the same position $p$ than the 2 configurations are the same. Because if the first move consists of sliding a domino $d$ the first time the empty cell returns to be $p$ we have just moved the domino $d$ so the first and the last move slide the same domino and now is only necessary to prove that the second and the second-last positions are the same and we can do the same argument. So the number of possible configurations is the number of possible positions that the empty square can reach. Divide the squares $(x,y)$ in 3 groups: $S_1=\{ (x,y) | x+y \; is \; odd \} \; ;S_2=\{ (x,y) | x \; and \; y \; are \; odd \} \; ;S_3=\{ (x,y) | x \; and \; y \; are \; even \}$. The empty square can be only in a square in $S_2 $ or $ S_3$ and after every move it remains in the same set because from $(x,y)$ it can go only in $(x+2,y),(x-2,y),(x,y+2),(x,y-2)$. So divide into 2 cases. Case 1 The empty square is in $S_3$ [asy][asy] size(6cm); pen border = black+1.5; filldraw(box((1, 1), (2, 2)), yellow); filldraw(box((0, 2), (1, 4)), red, border); filldraw(box((0, 4), (2, 5)), red, border); filldraw(box((0, 0), (1, 2)), red, border); filldraw(box((0, 5), (1, 7)), blue, border); filldraw(box((1, 5), (2, 7)), blue, border); filldraw(box((2, 5), (3, 7)), blue, border); filldraw(box((3, 5), (4, 7)), blue, border); filldraw(box((4, 5), (5, 7)), blue, border); filldraw(box((5, 5), (6, 7)), blue, border); filldraw(box((6, 5), (7, 7)), blue, border); filldraw(box((1, 0), (3, 1)), red, border); filldraw(box((3, 0), (5, 1)), red, border); filldraw(box((5, 0), (7, 1)), red, border); filldraw(box((6, 1), (7, 3)), red, border); filldraw(box((6, 3), (7, 5)), blue, border); filldraw(box((2, 4), (4, 5)), red, border); filldraw(box((6, 5), (7, 7)), blue, border); filldraw(box((3, 2), (4, 4)), white, border); filldraw(box((4, 2), (6, 3)), red, border); filldraw(box((4, 3), (5, 5)), red, border); filldraw(box((5, 3), (6, 5)), blue, border); filldraw(box((1, 2), (2, 4)), white, border); filldraw(box((4, 1), (6, 2)), white, border); filldraw(box((2, 1), (4, 2)), white, border); filldraw(box((3, 1), (4, 2)), yellow); filldraw(box((5, 1), (6, 2)), yellow); filldraw(box((1, 3), (2, 4)), yellow); filldraw(box((3, 3), (4, 4)), yellow); [/asy][/asy] $|S_3|=m^2$ so $k(C)$ must be in $\{ 1,2,...,m^2 \} $. We will show that it can be every value in this set. If we want $k(C)=am+b$ with $0 \leq a \leq m-1$ and $1 \leq b \leq m$ we chose the square in the first $a$ rows and the first $b$ elements in the $a+1th$ row (in figure in yellow). Around this square we create a ring (in red) so that this domino cannot be moved because they occupy only square in $S_1$ and $S_2$. Outside of the ring we put dominoes that occupy all of this zone and we can do that because this region is connected and the number of square in this zone that are also in $S_1$ is equal to the number of squares in $S_2$ and $S_3$. Inside the ring we left the empty square in the left-down square, we complete the first line with horizontal dominoes and we cover all the remaining squares with vertical dominoes. Now all the yellow square can became empty by sliding some of the horizontal dominoes so that the empty square is in the correct column and than by sliding the vertical dominoes we can bring the empty square in the wanted position. Obviously we cannot have the empty cell in other positions because it can never go outside the ring. Case 2 the empty square is in $S_2$ In this case we can assume that the empty square is at the border of the square because if it cannot reach the border than the maximum value that $k(C)$ can reach is $(m-1)^2$ but we have already prove that all the value $ \leq (m-1)^2$ are reachable so this case is not interesting. So assume that the empty square is on the border. Given any square in $S_2$ we consider the following path. [asy][asy] size(2cm); pen border = black+1.5; filldraw(box((0,0), (2, 1)), white); filldraw(box((2, 0), (3, 1)), white); pair A = (0.5, 0.5); pair B = (2.5, 0.5); dotfactor *= 1; dot(A); dot(B); draw(A--B, EndArrow, Margin(1,1)); [/asy][/asy] By a point $p$ in $S_2$ we consider the domino $d$ that contains it and we go in the point adjacent with the shortest edge of $d$ further from $p$. And we do the same process by this point. The point never goes outside the figure because the square outside the figure adiacent to it are all either in $S_1$ or in $S_3$. If this path forms a cycle we have a contradiction because there is a poligon with all the verteces in $S_2$ and so it has odd area but its interior is filled by dominoes $2 \times 1$ (the empty square cannot be inside because is at the border) so it must have even area. So all the path end in the empty square and by following the path starting by the empty square and going to the starting point we find a sequense of move that brings the empty square in the wanted position. Therefore the number of possible configurations is $(m+1)^2$. So the answer is $ \{ 1,2,...,m^2 \} \cup \{ (m+1)^2 \} $ This is a very easy problem; I solved it in less than 15 minutes.

r00tsOfUnity wrote: This was both JMO 3 and AMO 3? Wow don't think that's ever happened since 2017 I think it happened? Lots of times before. Didn’t know why stopped.

dbj2015 wrote: r00tsOfUnity wrote: dbj2015 wrote: Solved this as a 2nd grader on the USAMO.

Wait u promise no cap? u actually in SECOND GRADE? wow bro is the Luke Robitaille of the 2020s I promise. If you were in second grade and managed to complete this problem, you are the dude with more years of experience then the amount of years you were alive, and you are the person every asian parent wants as a child