Maximum is $(\frac{n+1}{2})^2$, where the optimal domino placement is in a spiral inwards.

How many partials if guessed the correct maximum, gave equality case, and proved some properties of the dominos configurations of $k(C)$? Like the $x$-coordinate of the unfilled squares must have the same parity (as well as the $y$-coordinate) and every dominos can only move maximum one step away from their original state. and then made a wild guess that for every unfilled square, only maximum one dominos configuration exists that originate from a common configuration

how many points for proving everything but the main claim (but having a somewhat incorrect proof of the main claim, but which seems to have some right ideas)

Note this problem is slightly different from AMO P3 as this only asks for the maximum while the AMO one asks for all values of $k(C)$.

Yessss I guessed the proposer Basically what I did is show the hole can only be in tiles where both “coordinates” (label rows and columns 1 thru n) are odd if the hole starts where both are odd and only even if both are even. The key claim is then that the hole can never be in two spots and from there (n+1)^2/4 is clear to find. https://artofproblemsolving.com/community/c716857h530563_rectangular_grid_with_dominoes

Holden with another grid problem!!!

grid combo>>>>>>>non-grid combo

darn this was really annoying Essentially the main claim is really easy to prove but is actually surprisingly useful: If the empty square moves from $c_1$ to $c_2$ via domino $d$: 1) The next time the empty square moves to $c_1$ can only be from $c_2$, via domino $d$ 2) Similarly, the next time domino $d$ is moved can only move the empty square from $c_2$ to $c_1$ Now we choose some sequence of moves that is minimal by inclusion, preserves the empty square, and does not preserve the configuration. Using the claim we find that the sequence can actually only have length two, else we contradict minimality. Then the configuration is preserved, contradiction.

How many points I can get if I proved a configuration that could give [(n+1)/2]^2 was possible for all nxn squares, but could not prove that there is no way to get more than that? 1 or 2?

1 $ $

asdf334 wrote: darn this was really annoying Essentially the main claim is really easy to prove but is actually surprisingly useful: If the empty square moves from $c_1$ to $c_2$ via domino $d$: 1) The next time the empty square moves to $c_1$ can only be from $c_2$, via domino $d$ 2) Similarly, the next time domino $d$ is moved can only move the empty square from $c_2$ to $c_1$ Now we choose some sequence of moves that is minimal by inclusion, preserves the empty square, and does not preserve the configuration. Using the claim we find that the sequence can actually only have length two, else we contradict minimality. Then the configuration is preserved, contradiction.

hi uh could someone answer the question posed in the remark here, im kind of worried bc i don't know if this warrants like 7 -> 5 or 7 -> 2 thanks!

Here was my proof that each hole corresponds to at most one arrangement:

I'm really worried that I'm going to be docked a point or two for how "unrigorous" this is; can somebody let me know if this is okay?

I think it’s mathematically valid unless I misunderstand something? Because if no sequence both preserves the empty square and doesn’t preserve the configuration exists then you’re just done. And if those sequences do exist then you can pick a minimal one

IAmTheHazard wrote: And if those sequences do exist then you can pick a minimal one wait oops you're right wait but if you choose something which is minimal by satisfying *both* conditions then it's not guaranteed that the sequence has size 2

How many points would I get if I just put $\left( \frac{n+1}{2} \right)^2$ with a couple examples? I failed the proof

well i feel that 1 point should be (n+1/2)^2 + you found the parity argument

imo, progress wise that seems more like 2 or 3 points. There are many different ways you can go about proving this as the answer.

Attached, thanks for asking. (Apparently, the footnote mentioned above was reiterated many times in the solution, so the error must lie elsewhere...)

but what if you have 1 domino. then wouldnt there be an infinite number of ways to cover the square bc you can keep sliding it

oh wait nvm its n by n sorry lol :bashing_head_against_wall: amateur mistake made by someone not yet in middle school. should never have posted.

paraya wrote: oh wait nvm its n by n sorry lol :bashing_head_against_wall: amateur mistake made by someone not yet in middle school. should never have posted. you could have deleted your post instead making another.

how to delete

skull emoji you can only delete the last post on a thread

peace09 wrote: Attached, thanks for asking. (Apparently, the footnote mentioned above was reiterated many times in the solution, so the error must lie elsewhere...) did you get a 5 like me ;-;

sixoneeight wrote: peace09 wrote: Attached, thanks for asking. (Apparently, the footnote mentioned above was reiterated many times in the solution, so the error must lie elsewhere...) did you get a 5 like me ;-; Yes, as with u/MathJams and u/vsamc, just to name a few. Probably a very common error, but I can't tell what...

\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\] The answer is $(n+1)^2/4$, construction omitted (what i have in my in contest half sol should work) Now we prove $k(C)\le (n+1)^2/4$. First we get some preliminary details in: Notice that the parity of the coordinates of the uncovered square stays the same, so no domino can move two times in the same direction. Claim: For each square, there is at most one valid configuration with that square uncovered. Proof: Suppose not. For each square that has multiple valid configurations with that square uncovered, let the *cycle length* of that square be denoted as the smallest number of moves between a valid configuration with that square uncovered to a new valid configuration with that square uncovered. Consider the square with a minimal *cycle length* (if multiple exist, choose any one), and the sequence of moves of minimal length between a valid config to a new valid config with this square uncovered. Notice that the last move in this sequence must be made by the domino that was used in the first move of the sequence and must move it back to its original position (this is because it cannot move twice in the same direction). Now notice that the config after the first move and before the last move have the exact same uncovered square and are different, hence we have a shorter *cycle length*, contradiction. $\square$ It suffices to show that there can be at most $(n+1)^2/4$ possible squares uncovered. Since the parity of the coordinates of the uncovered square remains constant, it can either be (odd,odd), (odd, even), (even,odd), (even,even). There are $(n+1)/2$ ways to generate an odd number between $1$ and $n$ inclusive, and $(n-1)/2$ ways to generate an even number between $1$ and $n$, inclusive. Hence we have at most $(n \pm 1)(n \pm 1)/4 \le (n+1)^2/4$ squares uncovered.

The answer is $\frac{(n+1)^2}4$. Construction is more or less obvious. For the bound, it suffices to show that for any square, there exists at most one such configuration with that square uncovered. Consider the directed graph on the black squares of the grid, with each domino representing an arrow in an obvious way. The key is the following: Claim. There are no undirected cycles in this graph, omitting the starting empty square. Proof. Direct induction; the area enclosed by the cycle is necessarily odd. $\blacksquare$ Now the idea is that for any omitted vertex picked, the orientation of the edges in the related graph is fixed as the omitted vertex has outdegree $0$ and the edges form a tree, hence the result.

Copied almost verbatim from my submitted solution, with some diagrams cut out since asy is too time consuming. Enjoy! The answer is $\left(\frac{n+1}{2}\right)^2$, with a construction being the following for $n=9$ which generalizes (note the spiral starting in the upper right corner and going down; that's what stays the same). [asy][asy] size(11cm); pen border = black + linewidth(6); filldraw(box((0, 0), (1, 1)), heavygreen, green); filldraw(box((0, 1), (1, 2)), red, red); draw(box((0, 0), (1, 2)), border); filldraw(box((0, 2), (1, 3)), heavygreen, green); filldraw(box((0, 3), (1, 4)), red, red); draw(box((0, 2), (1, 4)), border); filldraw(box((0, 4), (1, 5)), heavygreen, green); filldraw(box((0, 5), (1, 6)), red, red); draw(box((0, 4), (1, 6)), border); filldraw(box((0, 6), (1, 7)), heavygreen, green); filldraw(box((0, 7), (1, 8)), red, red); draw(box((0, 6), (1, 8)), border); filldraw(box((0, 8), (1, 9)), heavygreen, border); filldraw(box((2, 0), (3, 1)), heavygreen, green); filldraw(box((1, 0), (2, 1)), red, red); draw(box((1, 0), (3, 1)), border); filldraw(box((4, 0), (5, 1)), heavygreen, green); filldraw(box((3, 0), (4, 1)), red, red); draw(box((3, 0), (5, 1)), border); filldraw(box((6, 0), (7, 1)), heavygreen, green); filldraw(box((5, 0), (6, 1)), red, red); draw(box((5, 0), (7, 1)), border); filldraw(box((8, 0), (9, 1)), heavygreen, green); filldraw(box((7, 0), (8, 1)), red, red); draw(box((7, 0), (9, 1)), border); filldraw(box((2, 8), (3, 9)), heavygreen, green); filldraw(box((3, 8), (4, 9)), red, red); draw(box((2, 8), (4, 9)), border); filldraw(box((4, 8), (5, 9)), heavygreen, green); filldraw(box((5, 8), (6, 9)), red, red); draw(box((4, 8), (6, 9)), border); filldraw(box((6, 8), (7, 9)), heavygreen, green); filldraw(box((7, 8), (8, 9)), red, red); draw(box((6, 8), (8, 9)), border); filldraw(box((8, 2), (9, 3)), heavygreen, green); filldraw(box((8, 1), (9, 2)), red, red); draw(box((8, 1), (9, 3)), border); filldraw(box((8, 4), (9, 5)), heavygreen, green); filldraw(box((8, 3), (9, 4)), red, red); draw(box((8, 3), (9, 5)), border); filldraw(box((8, 6), (9, 7)), heavygreen, green); filldraw(box((8, 5), (9, 6)), red, red); draw(box((8, 5), (9, 7)), border); filldraw(box((8, 8), (9, 9)), heavygreen, green); filldraw(box((8, 7), (9, 8)), red, red); draw(box((8, 7), (9, 9)), border); filldraw(box((2, 2), (3, 3)), heavygreen, green); filldraw(box((2, 3), (3, 4)), red, red); draw(box((2, 2), (3, 4)), border); filldraw(box((2, 4), (3, 5)), heavygreen, green); filldraw(box((2, 5), (3, 6)), red, red); draw(box((2, 4), (3, 6)), border); filldraw(box((2, 6), (3, 7)), heavygreen, green); filldraw(box((2, 7), (3, 8)), red, red); draw(box((2, 6), (3, 8)), border); filldraw(box((4, 2), (5, 3)), heavygreen, green); filldraw(box((3, 2), (4, 3)), red, red); draw(box((3, 2), (5, 3)), border); filldraw(box((6, 2), (7, 3)), heavygreen, green); filldraw(box((5, 2), (6, 3)), red, red); draw(box((5, 2), (7, 3)), border);filldraw(box((6, 4), (7, 5)), heavygreen, green); filldraw(box((6, 3), (7, 4)), red, red); draw(box((6, 3), (7, 5)), border); filldraw(box((6, 6), (7, 7)), heavygreen, green); filldraw(box((6, 5), (7, 6)), red, red); draw(box((6, 5), (7, 7)), border);filldraw(box((4, 6), (5, 7)), heavygreen, green); filldraw(box((5, 6), (6, 7)), red, red); draw(box((4, 6), (6, 7)), border);filldraw(box((4, 4), (5, 5)), heavygreen, green); filldraw(box((4, 5), (5, 6)), red, red); draw(box((4, 4), (5, 6)), border); filldraw(box((1, 7), (2, 8)), mediumblue, mediumblue); filldraw(box((1, 8), (2, 9)), red, red); draw(box((1, 7), (2, 9)), border);filldraw(box((1, 5), (2, 6)), mediumblue, mediumblue); filldraw(box((1, 6), (2, 7)), red, red); draw(box((1, 5), (2, 7)), border);filldraw(box((1, 3), (2, 4)), mediumblue, mediumblue); filldraw(box((1, 4), (2, 5)), red, red); draw(box((1, 3), (2, 5)), border);filldraw(box((1, 1), (2, 2)), mediumblue, mediumblue); filldraw(box((1, 2), (2, 3)), red, red); draw(box((1, 1), (2, 3)), border); filldraw(box((3, 1), (4, 2)), mediumblue, mediumblue); filldraw(box((2, 1), (3, 2)), red, red); draw(box((2, 1), (4, 2)), border);filldraw(box((5, 1), (6, 2)), mediumblue, mediumblue); filldraw(box((4, 1), (5, 2)), red, red); draw(box((4, 1), (6, 2)), border);filldraw(box((7, 1), (8, 2)), mediumblue, mediumblue); filldraw(box((6, 1), (7, 2)), red, red); draw(box((6, 1), (8, 2)), border);filldraw(box((7, 2), (8, 3)), mediumblue, mediumblue); filldraw(box((7, 3), (8, 4)), red, red); draw(box((7, 2), (8, 4)), border); filldraw(box((7, 4), (8, 5)), mediumblue, mediumblue); filldraw(box((7, 5), (8, 6)), red, red); draw(box((7, 4), (8, 6)), border);filldraw(box((7, 6), (8, 7)), mediumblue, mediumblue); filldraw(box((7, 7), (8, 8)), red, red); draw(box((7, 6), (8, 8)), border);filldraw(box((5, 7), (6, 8)), mediumblue, mediumblue); filldraw(box((6, 7), (7, 8)), red, red); draw(box((5, 7), (7, 8)), border);filldraw(box((3, 7), (4, 8)), mediumblue, mediumblue); filldraw(box((4, 7), (5, 8)), red, red); draw(box((3, 7), (5, 8)), border); filldraw(box((3, 5), (4, 6)), mediumblue, mediumblue); filldraw(box((3, 6), (4, 7)), red, red); draw(box((3, 5), (4, 7)), border);filldraw(box((3, 3), (4, 4)), mediumblue, mediumblue); filldraw(box((3, 4), (4, 5)), red, red); draw(box((3, 3), (4, 5)), border);filldraw(box((5, 3), (6, 4)), mediumblue, mediumblue); filldraw(box((4, 3), (5, 4)), red, red); draw(box((4, 3), (6, 4)), border);filldraw(box((5, 5), (6, 6)), mediumblue, mediumblue); filldraw(box((5, 4), (6, 5)), red, red); draw(box((5, 4), (6, 6)), border); [/asy][/asy] To see this color squares red if the sum of their ``coordinates'' is odd, green if both are odd, and blue if both are even. From this initial configuration, every green square is the hole exactly once over all configs in $k(c)$; there are $\left(\frac{n+1}{2}\right)^2$ green cells so this holds. We now show it's the maximum. Let $n$ be any odd number, color like the construction. Claim: [Claim 1] There are two parts to this claim. The ``hole'' can never be red The ``hole'' can never switch colors Proof. We prove each part seperately. Each domino covers a red square and a green or blue square. Since there are $\frac{n^2-1}{2}$ dominoes and $\frac{n^2-1}{2}$ red squares, every red square is covered Suppose the hole is a certain color, and perform a transformation which changes its placement. One coordinate of the hole is constant, the other changes by $2$. In particular, neither changes parity, which means we're done. $\blacksquare$ Claim: [Claim 2] No two maximal grid aligned configs which can be obtained from each other via sliding have the same hole. Proof. Suppose it is possible, then let $x$ be the minimal amount of slides and the minial sequence of grid aligned configs be $P_1,P_2,\dots, P_{x+1}$. Slide $1$ is from $P_1$ to $P_2$, etc. Then, as $x$ is minimal, none of $P_2,P_3,\dots,P_{x-1},P_{x}$ have a hole in the same spot as $P_1,P_{x+1}$. Consider a close up near the hole from $P_1$ and $P_2$. I claim that the domino slid from $P_1$ to $P_2$ is not moved again until $P_x \rightarrow P_{x+1}$. Indeed, it can't move in the same direction as $P_1\rightarrow P_2$ again as that would cause the hole to be red. Also, it can't move opposite to $P_1\rightarrow P_2$ or it will contradict minimality. However, from $P_x\rightarrow P_{x+1}$, the hole needs to occur in the original spot, requiring this domino to move. Then, in the move $P_x\rightarrow P_{x+1}$ is moves opposite to $P_1\rightarrow P_2$. Thus the hole in $P_2$ is the same as in $P_x$, contradicting minimality. The claim is proven. $\blacksquare$ Combining the two claims, we see the hole must be green all the time, or blue all the time. If it is green all the time, then by claim $2$, we have $k(C)\leq \text{the number of green cells}$, which is $\frac{(n+1)^2}{4}$. If it is blue all the time, $k(C)\leq \text{the number of blue squares}$ which is $\frac{(n-1)^2}{4}$. Hence the $k(C)\leq \frac{(n+1)^2}{4}$ since $\frac{(n+1)^2}{4}>\frac{(n-1)^2}{4}$. As this is possible, we're done!!! Remark: Holden? If so, yet another Holden grid combo prob Remark: DID I SWEEP THIS DAY?? HOPE I DIDN'T FAKESOLVE (I fakesolved Holden grid combo USEMO 2022/1 but hopefully not this!)

The maximum possible value of $k(C)$ is $\left(\tfrac{n+1}{2}\right)^2$. Toss on the coordinate plane such that the unit squares correspond to coordinates in $\{1, 2, \dots, n\}^2$. We say that the friendly coordinates are those that have the same parity of the coordinates of the hole. Construction. Let the hole be in the top-left corner of the grid, and use an obvious spiral tiling. Bound. Consider the digraph $G$ on the friendly coordinates where $U \mapsto 2V-U$ if and only if $U$ and $V$ are the coordinates of a domino and $U$ is friendly. Claim: $G$ has no cycles in the undirected sense. Proof. Assume for contradiction that there exists a cycle $\mathcal{C}$. Let $\mathcal{C}$ have length $L$ (graph-theoretically) and suppose there are $I$ coordinates inside of the cycle on the board. By Pick's theorem, the area induced by the coordinates on the dominoes that $\mathcal{C}$ compromises of is \[ A = I + L - 1. \]It is easy to see that $A$ is even, so $I+L$ is odd. Since the interior coordinates must be tiled with dominoes, $I$ is even, so $L$ is odd. I contend that in fact, $L$ is even. Let $V$ be the number of vertical dominoes in $\mathcal{C}$ and $H$ be the number of horizontal dominoes in $\mathcal{C}$. Since there are as many upward vertical dominoes as downward (to complete the cycle), $V$ is even, and by similar logic $H$ is also even. Thus $L=H+V$ is even, a contradiction, so $G$ has no cycles. Thus $G$ must be the union of several disjoint trees. Consider the tree $T$ which contains the hole. Realize that sliding a domino corresponds to changing the direction of a directed edge, so it is easy to see by induction on $|V(T)|$ that $k(C) = |V(T)|$. Since $V(T)$ consists of only friendly coordinates, it must be at most $\left(\tfrac{n+1}{2}\right)^2$ (achieved when both coordinates of the hole are odd), proving our bound.

It is probably fakesolve, so if there is any mistake, let me know. Consider a graph with each vertex being a possible empty square. Then note that for every slide, the empty square moves by exactly 2. Hence the parity of the coordinates of possible empty squares are all same, which means there are at most $(\frac{n+1}{2})^2$ possible empty squares. Construction is more or less obvious. $\blacksquare$

Notice that the empty square always has the same parity as the initial empty square. Claim. Given the initial configuration, the location of the empty square determines a unique configuration. Proof. Observe that for any square, there is exactly one possible domino slide which makes it empty. Suppose square $S$ has been emptied earlier and covered by domino $D$. The only way to empty $S$ again is to slide $D$ again, in the opposite direction it slided when it covered $S$. In order for $D$ to slide, another square must be emptied. Continuing this way, it follows that to empty $S$, we must reverse the domino slides following the emptying of $S$. The same argument can be applied to show that there is only one sequence of domino slides to empty $S$ for the first time. Thus there is only one configuration for which $S$ is empty. $\square$ The maximum cardinality of a set of squares with the same parity is $\boxed{\left(\frac{n+1}{2}\right)^2}$. The construction is trivial. $\square$

thdnder wrote: It is probably fakesolve, so if there is any mistake, let me know. Consider a graph with each vertex being a possible empty square. Then note that for every slide, the empty square moves by exactly 2. Hence the parity of the coordinates of possible empty squares are all same, which means there are at most $(\frac{n+1}{2})^2$ possible empty squares. Construction is more or less obvious. $\blacksquare$ There may be multiple configurations for one empty square.