Let $m$ and $n$ be positive integers. Let $S$ be the set of integer points $(x,y)$ with $1\leq x\leq 2m$ and $1\leq y\leq 2n$. A configuration of $mn$ rectangles is called happy if each point in $S$ is a vertex of exactly one rectangle, and all rectangles have sides parallel to the coordinate axes. Prove that the number of happy configurations is odd. Proposed by Serena An and Claire Zhang
Problem
Source: USAJMO 2024/2
Tags: AMC, USA(J)MO, USAJMO, xtimmyGgettingflamed
20.03.2024 07:00
Solved with SOCOURGE. Define the $V$ and $H$ operations which flip the grid on the vertical and horizontal axis. To compute the number of happy arrangements $\pmod{2}$, we can discard all arrangements that aren't fixed under both operations. Now, suppose that an arrangement contains a rectangle which WLOG isn't fixed under $V$. Let the rectangle be in columns $a, b$, with a $V$ flip giving a copy in columns $2m - a, 2m - b$. We can replace this rectangle with one in $a, 2m - b$. Call this xooking, and note that it's an involution. This gives us another involution as follows after sorting all possible rectangles, by xooking the first ordered rectangle. As such, it only remains to consider happy arrangements with all rectangles fixed under $V, H$. There's only one such arrangement, we are done.
20.03.2024 07:01
Solved with mira74 and Th3Numb3rThr33. Let \(G\) be the group (acting on configurations) generated by the actions ``swap the \((2i-1)\)th and \((2i)\)th row'' and ``swap the \((2i-1)\)th and \((2i)\)th columns.'' Then \(G\) has order \(2^{m+n}\), so by orbit-stabilizer, every configuration has orbit dividing \(|G|\), and thus is either even or 1. By parity, it suffices then to consider configurations with orbit 1, of which there is only one configuration (where each rectangle is of the form \((2i-1,2j-1)\), \((2i,2j-1)\), \((2i-1,2j)\), \((2i,2j)\)).
20.03.2024 07:03
Proposed by Claire Zhang and me.
20.03.2024 07:04
induction spam lol notice that adding 1 to either m or n is the same as the amount of happy configs of m, n * the amount of happy configs with 2, n which is odd and then you add a bunch of other configs that all have mirrors
20.03.2024 07:06
pov maa likes grid combo oops
20.03.2024 07:10
Based on intuition from this problem, this problem is 5 MOHS. I solved both p1 and p2 (outside of contest) within 10 minutes combined. Suppose a configuration is not the same when acted on once by a symmetry of order $2$. Then, we can pair up the configuration with its result under the group action. Therefore, it suffices to consider configurations which are symmetric over the midline and upon a half circle rotation. Now, we can consider a rectangle that is not the same under any of the previous symmetries. Then, it must be paired up with another rectangle. However, we can then swap the vertices while preserving symmetry. As a result, this case is also even. Finally, we are left with rectangles that must all be centered at the middle of the big rectangle, which has only $1$ case. Thus the amount is odd.
20.03.2024 07:11
anser wrote: Proposed by Claire Zhang and me.
The solution should still work if rather than swapping 2 rows from the remaining, you reflect the remaining points right? The $2\times2$ case is trivial. Now, we induct proving that $f(2m + 2, 2n)$ is odd if $f(2m, 2n)$ is odd. There are 2 cases we consider for the rectangles containing the points in the leftmost column. Case 1: All points in the rectangles formed with points in the leftmost column lie in the center column ($m + 2$th column) [asy][asy] unitsize(0.5 cm); dot((0,0), purple); dot((1,0), black); dot((2,0), black); dot((3,0), purple); dot((4,0), black); dot((5,0), black); dot((0,1), red); dot((1,1), black); dot((2,1), black); dot((3,1), red); dot((4,1), black); dot((5,1), black); dot((0,2), orange); dot((1,2), black); dot((2,2), black); dot((3,2), orange); dot((4,2), black); dot((5,2), black); dot((0,3), red); dot((1,3), black); dot((2,3), black); dot((3,3), red); dot((4,3), black); dot((5,3), black); dot((0,4), orange); dot((1,4), black); dot((2,4), black); dot((3,4), orange); dot((4,4), black); dot((5,4), black); dot((0,5), purple); dot((1,5), black); dot((2,5), black); dot((3,5), purple); dot((4,5), black); dot((5,5),black); [/asy][/asy] There are $$\frac{\binom{2n}{2} \cdot \binom{2n - 2}{2} \dots \binom{2}{2}}{n!}$$ways to pair up the 2n points. From here, there are $f(2m,2n)$ to partition the remaining points into rectangles. Both of these quanitities are odd so total ways in this case are odd. Case 2: All other points do not lie in the center column [asy][asy] unitsize(0.5 cm); dot((0,0), purple); dot((1,0), black); dot((2,0), purple); dot((3,0), black); dot((4,0), black); dot((5,0), black); dot((0,1), red); dot((1,1), black); dot((2,1), black); dot((3,1), black); dot((4,1), red); dot((5,1), black); dot((0,2), orange); dot((1,2), black); dot((2,2), black); dot((3,2), orange); dot((4,2), black); dot((5,2), black); dot((0,3), red); dot((1,3), black); dot((2,3), black); dot((3,3), black); dot((4,3), red); dot((5,3), black); dot((0,4), orange); dot((1,4), black); dot((2,4), black); dot((3,4), orange); dot((4,4), black); dot((5,4), black); dot((0,5), purple); dot((1,5), black); dot((2,5), purple); dot((3,5), black); dot((4,5), black); dot((5,5), black); [/asy][/asy] We reflect over the points over the $m + 2$th column. [asy][asy] unitsize(0.5 cm); dot((0,0), purple); dot((1,0), black); dot((2,0), black); dot((3,0), black); dot((4,0), purple); dot((5,0), black); dot((0,1), red); dot((1,1), black); dot((2,1), red); dot((3,1), black); dot((4,1), black); dot((5,1), black); dot((0,2), orange); dot((1,2), black); dot((2,2), black); dot((3,2), orange); dot((4,2), black); dot((5,2), black); dot((0,3), red); dot((1,3), black); dot((2,3), red); dot((3,3), black); dot((4,3), black); dot((5,3), black); dot((0,4), orange); dot((1,4), black); dot((2,4), black); dot((3,4), orange); dot((4,4), black); dot((5,4), black); dot((0,5), purple); dot((1,5), black); dot((2,5), black); dot((3,5), black); dot((4,5), purple); dot((5,5), black); [/asy][/asy] Note that the number of ways to partition the remaining points into rectangles before and after the reflection is the same. This implies the number of ways in this case is even. In total, there are an odd number of ways.
20.03.2024 07:18
anser wrote: Proposed by Claire Zhang and me.
Imagine if somebody proved this closed form in-contest
20.03.2024 07:25
how many points for proving that a case is odd and saying some random seemingly related things??
20.03.2024 07:36
Maybe 1? In general, random seemingly related things do not receive points although I have no idea what you mean
20.03.2024 08:11
should have been usamo1
20.03.2024 08:21
pi_is_3.14 wrote: Maybe 1? In general, random seemingly related things do not receive points although I have no idea what you mean Seeing your solution here, I successfully showed Case 1 in your solution, but didn't get much farther than that. By "random seemingly related things" i was trolling oop I meant that I kind of wrote about my attempts to solve the rest of it, but I don't expect to get much from that part. I hope to get 1-2 points, in all likelihood I'm going to get one point.
20.03.2024 14:07
TheHazard wrote: As such, it only remains to consider happy arrangements with all rectangles fixed under $V, H$. There's only one such arrangement, we are done. Can't there be more than one? Whenever we construct a rectangle, we can also construct its reflections over $V$ and $H$. For instance, any happy configuration in the $m$ by $n$ sub-rectangle (if $mn$ is divisible by 4) can be reflected to a happy configuration in the $2m$ by $2n$ sub-rectangle.
20.03.2024 14:10
pi_is_3.14 wrote: anser wrote: Proposed by Claire Zhang and me.
The solution should still work if rather than swapping 2 rows from the remaining, you reflect the remaining points right? The $2\times2$ case is trivial. Now, we induct proving that $f(2m + 2, 2n)$ is odd if $f(2m, 2n)$ is odd. There are 2 cases we consider for the rectangles containing the points in the leftmost column. Case 1: All points in the rectangles formed with points in the leftmost column lie in the center column ($m + 2$th column) [asy][asy] unitsize(0.5 cm); dot((0,0), purple); dot((1,0), black); dot((2,0), black); dot((3,0), purple); dot((4,0), black); dot((0,1), red); dot((1,1), black); dot((2,1), black); dot((3,1), red); dot((4,1), black); dot((0,2), orange); dot((1,2), black); dot((2,2), black); dot((3,2), orange); dot((4,2), black); dot((0,3), red); dot((1,3), black); dot((2,3), black); dot((3,3), red); dot((4,3), black); dot((0,4), orange); dot((1,4), black); dot((2,4), black); dot((3,4), orange); dot((4,4), black); dot((0,5), purple); dot((1,5), black); dot((2,5), black); dot((3,5), purple); dot((4,5), black); [/asy][/asy] There are $$\frac{\binom{2n}{2} \cdot \binom{2n - 2}{2} \dots \binom{2}{2}}{n!}$$ways to pair up the 2n points. From here, there are $f(2m,2n)$ to partition the remaining points into rectangles. Both of these quanitities are odd so total ways in this case are odd. Case 2: All other points do not lie in the center column [asy][asy] unitsize(0.5 cm); dot((0,0), purple); dot((1,0), black); dot((2,0), purple); dot((3,0), black); dot((4,0), black); dot((0,1), red); dot((1,1), black); dot((2,1), black); dot((3,1), black); dot((4,1), red); dot((0,2), orange); dot((1,2), black); dot((2,2), black); dot((3,2), orange); dot((4,2), black); dot((0,3), red); dot((1,3), black); dot((2,3), black); dot((3,3), black); dot((4,3), red); dot((0,4), orange); dot((1,4), black); dot((2,4), black); dot((3,4), orange); dot((4,4), black); dot((0,5), purple); dot((1,5), black); dot((2,5), purple); dot((3,5), black); dot((4,5), black); [/asy][/asy] We reflect over the points over the $m + 2$th column. [asy][asy] unitsize(0.5 cm); dot((0,0), purple); dot((1,0), black); dot((2,0), black); dot((3,0), black); dot((4,0), purple); dot((0,1), red); dot((1,1), black); dot((2,1), red); dot((3,1), black); dot((4,1), black); dot((0,2), orange); dot((1,2), black); dot((2,2), black); dot((3,2), orange); dot((4,2), black); dot((0,3), red); dot((1,3), black); dot((2,3), red); dot((3,3), black); dot((4,3), black); dot((0,4), orange); dot((1,4), black); dot((2,4), black); dot((3,4), orange); dot((4,4), black); dot((0,5), purple); dot((1,5), black); dot((2,5), black); dot((3,5), black); dot((4,5), purple); [/asy][/asy] Note that the number of ways to partition the remaining points into rectangles before and after the reflection is the same. This implies the number of ways in this case is even. In total, there are an odd number of ways. But "not all points lying on $m+2$th column" isn't the same as "the configuration is not symmetric about a reflection".
20.03.2024 14:30
My solution (bad): We build a configuration from the bottom up with the following algorithm: 1) Take the lowest row with un-assigned points and assign (unordered) pairs of points to it. Connect the pairs; they form the bottom edges of rectangles. 2) Extend these pairs up to form rectangles. Repeat steps 1 and 2 until done.
that there are always an odd number of choices in step 1. In step 2, there are always an odd number of choices for the y-coordinate to extend the rectangle up to. This is true because we start with $2n$ possibilities, remove 2 for each rectangle already there, and remove 1 for the y-coordinate we're starting from. Steps 1 and 2 both have an odd number of choices, so the total number of possible renditions of the algorithm is odd. Note that any configuration corresponds to a unique rendition of the algorithm (i.e. looking at any happy config, you can easily decompose it into steps) so we're done Idk if this works. Can anyone let me know?
20.03.2024 14:40
Jack_w wrote: My solution (bad): We build a configuration from the bottom up with the following algorithm: 1) Take the lowest row with un-assigned points and assign (unordered) pairs of points to it. Connect the pairs; they form the bottom edges of rectangles. 2) Extend these pairs up to form rectangles. Repeat steps 1 and 2 until done.
that there are always an odd number of choices in step 1. In step 2, there are always an odd number of choices for the y-coordinate to extend the rectangle up to. This is true because we start with $2n$ possibilities, remove 2 for each rectangle already there, and remove 1 for the y-coordinate we're starting from. Steps 1 and 2 both have an odd number of choices, so the total number of possible renditions of the algorithm is odd. Note that any configuration corresponds to a unique rendition of the algorithm (i.e. looking at any happy config, you can easily decompose it into steps) so we're done Idk if this works. Can anyone let me know? I think step 2 doesn't work. When considering all possible rectangles that can be formed, both of the y-coordinates must be unassigned, but I think the number of choices can be even. Consider the rectangles (1,1) (3,1) (1,n) (3,n), and (2,1) (4,1) (2,m) (3,m). Suppose we are constructing a rectangle using the "bottom points" at (1,2) and (2,2). We cannot assign the y-coordinates to y=2, y=1, y=n, or y=m, so there are an even number of choices.
20.03.2024 14:46
Yeah. Maybe I can still manage a 7- instead of 0+
20.03.2024 14:58
I first tried a reflection sol, but I ran into the issue that: a) if I take a small set of involutions, then there are too many invariant configurations to count b) if I take a large set of involutions, then the following is likely to occur: We have involutions $A$ and $B$. If $S$ under $A$ gets paired with $S'$, that's fine. However, what if $S''$ under $B$ would also get paired with $S'$? I was not able to resolve this issue... Anyway, I showed later that considering an arbitrary vertex $(a,b)$ and some $k<mn$ rectangles of the happy configuration filled in, there are an odd number of rectangles that can be formed using $(a,b)$ as a vertex. This might be false though...
20.03.2024 15:11
I think that this problem was actually pretty hard, definitely the hardest on day 1. The motivation for swapping 2 columns and inducting comes from finding an involution that fixes the least amount of happy configs as possible (so we can pair up almost all of the other configs). Swaps do a better job at this than flipping or translating.
21.03.2024 19:08
EpicBird08 wrote: If $f(m,n)$ is the number of happy configurations, would I get any points for proving that $f(m,1) = (2m-1)!!$ using induction and then proving that $f(m,n) \ge f(m,1) \cdot f(n,1)?$ wait this is exactly what i did
22.03.2024 01:23
mathboy_2023 wrote: MathPerson12321 wrote: vrondoS wrote:
Yeah that was my sol Bruh like the general idea?
22.03.2024 01:34
meduh6849 wrote: TheHazard wrote: As such, it only remains to consider happy arrangements with all rectangles fixed under $V, H$. There's only one such arrangement, we are done. Can't there be more than one? Whenever we construct a rectangle, we can also construct its reflections over $V$ and $H$. For instance, any happy configuration in the $m$ by $n$ sub-rectangle (if $mn$ is divisible by 4) can be reflected to a happy configuration in the $2m$ by $2n$ sub-rectangle. Hi! All rectangles being fixed under the operation means each rectangle itself is fixed under V and H. No one is disputing that there are more than one entire arrangement fixed under flipping, but the involutions pair up arrangements with some rectangles not fixed under all operations.
22.03.2024 08:06
Let $f$ and $g$ denote reflections about the horizontal and vertical axes of symmetry of the point set, respectively. By the means of pairing, it suffices to prove that the number of working configs such that for each rectangle $R$, $f(g(R))$ is also in the set, is odd. Consider the good configurations in which there is at least one rectangle $R$ such that $f(g(R)) \neq R$. The key idea is that there is an involution $h$ of the rectangles such that the set of points covered by $R, f(R), g(R), f(g(R))$ is the same as that of $h(R), f(h(R)), g(h(R)), f(g(h(R)))$. To convince yourself, consider the illustration in the hidden tag below, where the red rectangle denotes the image of the top-right blue rectangle under $h$. (Explicitly, $h$ maps the vertex $A$ closest to the center of the grid to its reflection over the center of the grid, the vertex $C$ farthest from the origin to itself, and the other two vertices $B$ and $D$ over its nearest axis.)
Note that $h$ allows us to pair up good configurations, so we are left with the configurations which are all fixed by $f \circ g$. However, these configurations enumerate to only one (which is indeed odd): the set of all rectangles that are symmetric both horizontally and vertically. Thus we are done.
24.03.2024 07:02
Forget about rotation and consider inducting. Claim: There are an odd number of happy tilings for $2 \times 2n$ grid. Proof. Note that the number of such tilings is clearly, \begin{align*} T = \frac{1}{n!} \binom{2n}{2} \binom{2n-2}{2} \dots \binom{2}{2} = \frac{(2n)!}{2^k \cdot n!} \end{align*}It suffices to show that $\nu_2(T) = 0$, which is obvious from Legendre's. $\square$ Now assume for $m \leq k - 1$ we have shown that there is an odd number of happy tilings of a $2m \times 2n$ grid. It suffices to show that the number of tilings for a $2k \times 2n$ grid is odd. To do this, label the $(2k - 1)^{\text{th}}$ and $(2k)^{\text{th}}$ row by the set $A$, and all other rows by $B$. There are then two cases: Each rectangle is contained strictly in $A$ or $B$. There is at least one rectangle that has vertices in both $A$ and $B$. Clearly the number of happy configurations of the first type is odd from our induction. Thus it suffices to show that the number of happy configurations of the second type are even. Call all happy configurations of the second kind special. To do this consider the involution permuting the $(2k - 1)^{\text{th}}$ and $(2k)^{\text{th}}$ rows. This is an involution (hopefully I got it right this time) from special happy configurations to special happy configurations, which finishes. Remark: Oops @below, lemme fix that real quick. This problem isn't really difficult you just have to be careful really. Unfortunately it's a bit tough to sort our the rotation invariant thing, and it's a lot easier to just swap rows, both of which I had motivated by looking at the $m = n = 2$ case.
24.03.2024 19:28
Shreyasharma wrote: However we must also account for happy configurations that map to themselves under this operation. It is clear only $1$ such configuration exists, and thus the number of happy configurations is odd. Note for all future solutions I guess: if your proof uses a reflection/rotation involution, there are many more configs that map to themselves than the $1$ configuration where each rectangle maps to itself. It is possible for $2$ different rectangles in a config to map to each other, which still allows the original config and its map to be identical. If your solution doesn't tackle these cases, your solution is incomplete.
24.03.2024 19:45
What percentage of students fakesolved this? Is it really that easy to fakesolve it?
24.03.2024 20:35
Here is the (rather overcomplicated) solution that I first found. Define $f(2m, 2n)$ in the obvious way. Given a happy configuration, consider all the rectangles whose left edge is in the first column. Highlight every column containing the right edge of such a rectangle. For example, in the figure below, there are two highlighted columns. (The rectangles are drawn crooked so one can tell them apart.) [asy][asy] real eps = 0.6; for (int x=1; x<=10; ++x) { for (int y=1; y<=6; ++y) { pair P = (x,y); dot(P); } } dotfactor *= 1; real eps = 0.3; void rect(real a, real b, real u, real v, pen p) { draw( (a,b)--((a+u)/2, b-eps)--(u,b)--(u+eps,(b+v)/2)--(u,v) --((a+u)/2, v+eps)--(a,v)--(a-eps, (b+v)/2)--cycle, p); fill(circle((a,b), 0.2), p); fill(circle((u,b), 0.2), p); fill(circle((a,v), 0.2), p); fill(circle((u,v), 0.2), p); } rect(1,1,8,3, blue + 1.5); rect(1,2,5,6, deepgreen + 1.5); rect(1,4,8,5, red + 1.5); filldraw(box((4.5, 0.6), (5.5, 6.4)), invisible, black+dashed); filldraw(box((7.5, 0.6), (8.5, 6.4)), invisible, black+dashed); [/asy][/asy] We organize happy configurations based on the set of highlighted columns are highlighted. Specifically, define the relation $\sim$ on configurations by saying that $\mathcal C \sim \mathcal C'$ if they differ by any permutation of the highlighted columns. This is an equivalence relation. And in general, if there are $k$ highlighted columns, its equivalence class under $\sim$ has $k!$ elements. Then Claim: $f(2m, 2n)$ has the same parity as the number of happy configurations with exactly one highlighted column. Proof. Since $k!$ is even for all $k \ge 2$, but odd when $k=1$. $\blacksquare$ There are $2m-1$ ways to pick a single highlighted column, and then $f(2, 2n) = (2n-1){!}{!}$ ways to use the left column and highlighted column. So the count in the claim is exactly given by \[ (2m-1) \cdot (2n-1){!}{!} f(2m-2, 2n). \]This implies $f(2m, 2n) \equiv f(2m-2,2n) \pmod 2$ and proceeding by induction solves the problem.
24.03.2024 20:50
Hi, Evan, what do you think of the difficulty level of this problem? v_Enhance wrote: Here is the (rather overcomplicated) solution that I first found. Define $f(2m, 2n)$ in the obvious way. Given a happy configuration, consider all the rectangles whose left edge is in the first column. Highlight every column containing the right edge of such a rectangle. For example, in the figure below, there are two highlighted columns. (The rectangles are drawn crooked so one can tell them apart.) [asy][asy] real eps = 0.6; for (int x=1; x<=10; ++x) { for (int y=1; y<=6; ++y) { pair P = (x,y); dot(P); } } dotfactor *= 1; real eps = 0.3; void rect(real a, real b, real u, real v, pen p) { draw( (a,b)--((a+u)/2, b-eps)--(u,b)--(u+eps,(b+v)/2)--(u,v) --((a+u)/2, v+eps)--(a,v)--(a-eps, (b+v)/2)--cycle, p); fill(circle((a,b), 0.2), p); fill(circle((u,b), 0.2), p); fill(circle((a,v), 0.2), p); fill(circle((u,v), 0.2), p); } rect(1,1,8,3, blue + 1.5); rect(1,2,5,6, deepgreen + 1.5); rect(1,4,8,5, red + 1.5); filldraw(box((4.5, 0.6), (5.5, 6.4)), invisible, black+dashed); filldraw(box((7.5, 0.6), (8.5, 6.4)), invisible, black+dashed); [/asy][/asy] We organize happy configurations based on the set of highlighted columns are highlighted. Specifically, define the relation $\sim$ on configurations by saying that $\mathcal C \sim \mathcal C'$ if they differ by any permutation of the highlighted columns. This is an equivalence relation. And in general, if there are $k$ highlighted columns, its equivalence class under $\sim$ has $k!$ elements. Then Claim: $f(2m, 2n)$ has the same parity as the number of happy configurations with exactly one highlighted column. Proof. Since $k!$ is even for all $k \ge 2$, but odd when $k=1$. $\blacksquare$ There are $2m-1$ ways to pick a single highlighted column, and then $f(2, 2n) = (2n-1){!}{!}$ ways to use the left column and highlighted column. So the count in the claim is exactly given by \[ (2m-1) \cdot (2n-1){!}{!} f(2m-2, 2n). \]This implies $f(2m, 2n) \equiv f(2m-2,2n) \pmod 2$ and proceeding by induction solves the problem.
24.03.2024 20:57
I would say that this problem is $5$ to $10$ mohs, it's not extremely difficult but from a different perspective it's easy to fakesolve; I don't really know if that contributes to the actual difficulty of solving the problem though. All my opinion though. Edit: Edited it to make the bounds $5$ mohs lower because I found an easy fix to the common fakesolve. Will add in a bit.
24.03.2024 21:22
mulberrykid wrote: Hi, Evan, what do you think of the difficulty level of this problem? Harder than JMO1, that's for sure When I did this on stream the video ended up being about 20 minutes, though about half of that was me trying to explain the mess of my white board to the understandly confused audience. The video will go up sometime today, if you want to see my stumble around a bit before I manage to find this approach --- that might be more informative than hearing me making up a MOHS number. I think it was pretty clear to me that it needed to be some sort of grouping argument, but it wasn't obvious to me which grouping was going to eventually work. It didn't occur to me to only swap two rows. Edit: VOD up at https://www.youtube.com/watch?v=eZe8tDDSx70
24.03.2024 21:34
Shreyasharma wrote: I would say that this problem is $10$ to $15$ mohs, it's not extremely difficult but from a different perspective it's easy to fakesolve; I don't really know if that contributes to the actual difficulty of solving the problem though. All my opinion though. I would say its like 5 mohs or less, but as above said, the mohs scale is a bit broken.
29.03.2024 05:14
I did the following in contest (I hope this works), and I don't think this exact sol has been mentioned in this thread though the ideas seem to be similar to those in post #24. This solution would have been a lot shorter if I done vertical symmetry, rather than only considering horizontal symmetry, but oh well. Let $f(m, n)$ denote the corresponding number of happy configurations. We first resolve when $m = 1$. In this case, we note that for $1 \le k \le 2n$, the points $(1, k)$ and $(2, k)$ must be vertices of the same rectangle, so it's equivalent to find the number of ways to form unordered pairs from $\{1, 2, \ldots, 2n\}$. By choosing which number to pair with $1$, we see for $n \ge 2$ that $f(1, n) = (2n - 1)f(1, n - 1)$. Since $f(1, 1) = 1$ is odd, by an inductive argument $f(1, n)$ is odd for any positive integer $n$. Now, we move on to the general case for $m \ge 2$. Note that for any point in $S$, its reflection across the line $x = m + \tfrac{1}{2}$ (denote this by $\ell$) is also in $S$. This lets us pair up happy configs which are asymmetric wrt $\ell$, so it now suffices to show the number of symmetric happy configs about $\ell$ is odd. For this, we let $P_1$ be some point in $S$, and $P_2$ be the unique other point in $S$ with the same $x$-coordinate and on the same rectangle as $P_1$. If we let $P_1'$, $P_2'$ be the other vertices of the rectangle s.t. $P_1, P_1'$ have the same $y$-coordinate, as do $P_2$ and $P_2'$, then we must have one of the following three cases: Case 1: $P_1P_2P_2'P_1$ is symmetric across $\ell$. We will then say $P_1$ and $P_2$ are in a couple, as are $P_1'$ and $P_2'$ Case 2: $P_1P_2P_2'P_1'$ is asymmetric across $\ell$, and all four points lie on the same side of $\ell$. We then say the four points $P_1P_2P_2'P_1'$ form a quadruple, and we also note that their corresponding reflections over $\ell$ are also all vertices of one rectangle. We also call these two rectangles a Type A pair Case 2: $P_1P_2P_2'P_1'$ is asymmetric across $\ell$, yet not all four points lie on the same side of $\ell$. Then if we let $Q_1, Q_2, Q_1', Q_2'$ be their corresponding reflections over $\ell$, we note that $Q_1Q_2Q_2'Q_1'$ is also a rectangle, and that $\{P_1, P_2, Q_1', Q_2'\}$ are on the same side of $\ell$, as are $\{P_1' P_2', Q_1, Q_2\}$. These two sets of four points will also each be a quadruple, and the two rectangles in this case will be a Type B pair Then, the following process will generate all happy configs symmetric across $\ell$: 1. Partition the $2mn$ points in $S$ to the left of $\ell$ (i.e. with $x$-coordinates less than $m + \tfrac{1}{2}$) into couples and quadruples such that every point is in either one couple or one quadruple, but not both. 2. For any points $\{P_1, P_2\}$ in a couple, reflect them over $\ell$ to $P_1', P_2'$ and draw rectangle $P_1P_2P_2'P_1$ 3. For any points $\{P_1, P_2, P_3, P_4\}$ in a quadruple, reflect them over $\ell$ so there are $8$ points in total. Then, using these $8$ points, draw either a pair of Type A or a pair of Type B rectangles, but not both. It's also evident enough that this process generates a unique happy config every time, depending on how the points are partitioned and what we choose to do in the third step. Thus, we can see that after we fix the quadruples and couples, we are able to generate $2^{\# \text{ of quadruples}}$ happy configs, so it now suffices to show that the number of happy configs with only couples is odd. But by considering the points in $S$ on $x = k$ for $1 \le k \le m$, we find there are $f(1, n)^m$ ways to do this, which is odd. So, we are done.
06.08.2024 20:35
Easy Let $C(2m, 2n)$ be the number of happy configurations on a $2m \times 2n$ lattice grid. Let column $i$ be the set of points $x = i, 1 \le y \le 2n$. Define the swiping operation as swapping column $1$ and column $2m$. In particular, any point $(1, k)$ goes to $(2m, k)$ and vice versa. Note that swiping is an involution, so we want to show the number of configurations that remain the same after being swiped (say, unswipeable configurations) is odd. Now note that in any unswipeable configuration, for any rectangle with two vertices on column $1$ or $2m$, its reflection over the line $y = \frac{2m + 1}{2}$ is also present in the configuration. It is natural to consider the operation $$\{(1, j) (1, k), (t, j), (t, k) \} \to \{(1, j) (1, k), (2m - t, j), (2m - t, k) \}$$$$\{(2m, j) (2m, k), (2m - t, j), (2m - t, k) \} \to \{ (2m, j), (2m, k), (t, j), (t, k) \}$$on any rectangles with vertices $(1, j), (1, k), (t, j), (t, k)$ and its reflection. We will call it crossing. Since it is also an involution, define all configurations that remain the same under the operation uncrossable. It suffices to show the number of such configurations is odd. But in any uncrossable configuration, all rectangles sharing two vertices on column $1$ cannot have a reflection over $y = \frac{2m + 1}{2}$ otherwise the crossing operation can be performed, hence all such rectangles must also share two vertices with column $2m$. Note that these rectangles are completely independent from the middle $(2m - 2) \times 2n$ subgrid. There are $(2n - 1)!!$ ways to choose the rectangles, and $C(2m - 2, 2n)$ ways to arrange rectangles in the subgrid. Collectively, we obtain $C(2m, 2m) \equiv (2n - 1)!! C(2m - 2, 2n) \equiv C(2m - 2, 2n) \pmod{2}$. Since we can also decrease in both $2m$ and $2n$, we can keep going down until we have $C(2m, 2n) \equiv C(2, 2) \equiv 1 \pmod {2}$ and we are done.
03.12.2024 05:49
Begin by considering the points $(1,y)$. In order for them to be placed into a happy configuration, they must be divided up into $n$ pairs of points, which can be done in \[\frac{\binom{2n}{2} \cdot \binom{2n-2}{2} \cdot \dots \cdot \binom{2}{2}}{n!}.\] Observe that this simplifies to \[\prod_{i=1}^n \frac{\frac{2i(2i-1)}{2}}{i} = \prod_{i=1}^n (2i-1),\] which is odd. We WLOG suppose that the points on $x=1$ are paired up such that $(1,2y-1)$ and $(1,2y)$ are together for $y = 1,2,\dots,n$. After ignoring $x=1$, we are left with a $(2m-1) \times 2n$ grid with $n$ segments connecting $(x_i,2i-1)$ and $(x_i,2i)$: [asy][asy] size(10cm); import geometry; for(int i = 0; i<12; ++i){ for(int j = 0; j<6; ++j){ dot((i,j)); } } draw((0.5,-0.5)--(0.5,5.5),dotted); draw((3,1)--(0,1)--(0,0)--(3,0),red+dotted); draw((3,1)--(3,0),red); draw((10,3)--(0,3)--(0,2)--(10,2),blue+dotted); draw((10,3)--(10,2),blue); draw((2,5)--(0,5)--(0,4)--(2,4),green+dotted); draw((2,5)--(2,4),green); [/asy][/asy] If any tuple $(x_1, x_2, \dots x_n)$ produces any happy configurations, then $(2(m+1)-x_1, 2(m+1)-x_2, \dots, 2(m+1)-x_n)$ produces an equal amount of happy configurations due to symmetry. The only time where the symmetry fails is when $x_1=x_2=\dots=x_n = m+1$. At this point, we can also ignore the line $x=m+1$, reducing $m$ to $m-1$ in the original problem. Hence, we can use induction on $m$ to reduce the $2m \times 2n$ grid to a $1 \times 2n$ grid; on a $1 \times 2n$ grid, the number of happy configurations is equivalent to the number of ways to split up $2n$ numbers into $n$ pairs, which we already know is odd. $\blacksquare$ Remark: The above solution is a cleaned up writeup of what I submitted in the contest.