does EGMO have an unhealthy obsession with domino tilings or what

Mine. Not the most novel problem, but hopefully it’s clear why I proposed this particular problem for EGMO. If you solve this problem with the Kasteleyn formula, you can get an imaginary cookie. [I don’t know if it’s possible to do so, but I imagine it is.]

We claim the answer is $n=2^m-1$ Indeed, first notice that if $n$ is even then $f(n,n)$ is always even by pairing reflections and rotations. Thus, $n$ must be odd. Now, consider the case where the tiling does not have horizontal symmetry (ie: top half and bottom half including middle row are not symmetrical) such cases come in pairs by reflecting over the horizontal axis. Thus, $f(n,2k)$ must have the same parity of the number of horizontal symmetric tilings. Notice that horizontally symmetric tilings have the entire middle row filled with dominoes. Thus, $f(n,2k)$ and $f \left (\frac{n-1}{2},2k \right )$ must have the same parity. Finally, we proceed with induction. For our base case, $n=1$ gives $f(1,2k)=1$ which is odd for all $k$ and for the inductive step, we see that $\frac{n-1}{2}$ must be in the form $2^i-1$ for $n$ to work, which implies $n$ is in the same form. $\blacksquare$

Solved with Jeffrey Chen and Max Lu., The answer is $n+1$ a power of two. Proposition: The number of domino tilings of an $m\times n$ grid is odd if and only if $\gcd(m+1,n+1)=1$. Proof. A seminar by Ricky Liu at MOP 2019, following https://arxiv.org/abs/1911.08102. $\blacksquare$ The problem then follows.

Solved with Eric Shen and Max Lu (without Ricky Liu) The answer is $n = 2^r - 1$. Assume there are $n$ rows and $2k$ columns. For $n = 2^r - 1$, consider the reflection over the middle row. For all configurations which don't map to itself, we can pair them up using this operation, resulting in an even number of configurations. Otherwise, the middle row must be completely horizontal, and the remaining two $2^{r-1} - 1$ by $2k$ must have the equivalent configuration via reflection. Therefore, $f(2^r - 1, 2k) \equiv f(2^{r-1} - 1)\pmod{2}$. By induction on $r = 1$, we win. Now, I claim no other $n$ work. We induct on $n$: For our base case of $n = 2$, take $k = 1$, and we win. Now, assume for all $t < n$, where $t\neq 2^r -1$, there exist a $k$ such that $f(t,2k)$ is even. We have two cases: Case 1: $n$ is even. Now, take $k = \frac{n}{2}$. I claim $f(n, n)$ is even. This is because, reflecting over the major diagonal, each configuration maps to a different one, and vice versa. Case 2: $n$ is odd. Now, consider the reflection across the midline. Since the configurations only map to themselves if the midline is filled with horizontal dominoes, and the resulting two rectangles have the same configuration over reflection, we have \[f(n) \equiv f(\frac{n-1}{2}) \pmod{2}\]and since if $n\neq 2^r - 1$, then $\frac{n-1}{2}\neq 2^{r} - 1$, we have $f(n)$ is even. Thus, the only solution is $n = 2^{r} - 1$.

Cliam:$f(2k,2n+1) \equiv f(2k,n)$(mod2)

Another fun(ny?) problem on the EGMO. The answer is $n=2^m-1$ for some $m \geq 1$. All congruences are taken modulo $2$, and an $m \times n$ board is taken to have $m$ (horizontal) rows and $n$ (vertical) columns. The two key claims of the problem are as follows: Claim 1: $f(n,2k) \equiv f(2n+1,2k)$. Proof: Note that any tiling of the $2n+1 \times 2k$ board which isn't vertically symmetric can be uniquely paired with its horizontal reflection, so there are an even number of these. Thus we only care about vertically symmetric tilings. It is evident that the middle column must be tiled with vertical dominoes. Then the rest of the tiling is uniquely determined by the $n \times 2k$ board on the left side of this column, since the right side is simply its reflection, and the conclusion follows. $\blacksquare$ Claim 2: $f(2n,2n)$ is even. Proof: Consider the orientation of the domino $d$ covering the top left square. By reflecting over the line joining the top left and bottom right squares, we can biject every tiling with $d$ vertical to a tiling with $d$ horizontal, so there are an even number of tilings of a $2n \times 2n$ board. Now, claim 2 implies that if $n>0$ is even we can take $k=\tfrac{n}{2}$ to get $f(n,2k)$ even. Hence if $f(n,2k)$ is always odd, iteratively applying $n \to \tfrac{n-1}{2}$ until we reach an even number should yield zero (since $f(0,2k)=1$—the only way to tile that board is to do nothing). But if $n$ odd isn't of the form $2^m-1$, then clearly $\tfrac{n-1}{2}$ isn't either, and $0=2^0-1$, so the first even we reach can't be zero. On the other hand, if $n=2^m-1$, then $\tfrac{n-1}{2}=2^{m-1}-1$ so we do eventually reach zero, which yields the desired answer. $\blacksquare$

Ru83n05 wrote: Call such an integer $n$ nice. Claim 1: If $n$ is nice, then $n$ is odd. Proof: Since $f(n, 2k)\equiv 1 \pmod 2$ for every $k$, then it must hold for $k=1$. But we know that $f(n, 2)=F_n$, the $n$-th Fibonacci number. This is odd only for odd $n$. $\blacksquare$ Claim 2: $2n+1$ is nice iff $n$ is nice. Proof: Pair two tiling configurations of an $n\times 2k+1$ board up if they are symmetric along the middle ($k+1$-th) row. The only boards that we cannot pair up are those with only horitzontal dominoes along the $k+1$- th row; there are $f(n, 2k)$ of these. Hence $f(2n+1, 2k)\equiv f(n, 2k)\pmod 2$, and the conclusion follows. $\blacksquare$ Notice that $n=1$ is good, so combining these two claims we see that the only good integers are those of the form $n=2^t-1$. (Straightforward induction). $\square$ you have an error in cliam1.

The answer is $\boxed{2^i-1}$ for positive integers $i$. Claim: $n$ is odd. Proof: We will show that if $n$ is even, then $f(n,n)$ is even. Reflect over diagonal going from top left corner to bottom right corner. Clearly we get a different tiling that's still valid. Since each tiling has it's unique mapping, there are an even number of tilings. $\blacksquare$ Claim: If $f(n,2k)$ is odd for each $k$, then $f(2n+1,2k)$ is odd for each $k$. Proof: Basically, if a tiling isn't vertically symmetric, we can pair it up with its horizontal reflection. Clearly even number of these. So we only care about vertically symmetric tilings. The midline has to be vertically tiled. Note that the midline divides the board into two $n\times 2k$ boards. There are $f(n,2k)^2$ ways to tile these, which is odd. $\blacksquare$ If an odd $n$ works that's not a power of $2$, we can subtract $1$ and then divide by $2$ until we reach some positive even number, which is a contradiction. All we have to show is that $n=1$ works, but $f(1,2k)=2k-1$, which is odd.

We first prove two key claims, which together will solve the problem. Claim 1: $f(2a,2a)$ is even for every positive integer $a$. Proof: It suffices to partition the tilings of a $2a\times 2a$ grid into sets of even cardinality. Fix a tiling $T$. Consider the $2\times 2$ square in the center of the grid. If there are two dominoes completely within this square, then the set of tilings obtained by rotating $T$ $0^\circ$, $90^\circ$, $180^\circ$, and $270^\circ$ clockwise about the center of the grid has either $2$ or $4$ distinct elements. Otherwise, we can pair $T$ with the tiling obtained by reflecting $T$ over the bottom left to upper right diagonal. Claim 2: $f(2a+1, 2b)\equiv f(a, 2b)\pmod{2}$ for all positive integers $a$ and $b$. Proof: Consider a grid with $2a+1$ rows and $2b$ columns. Clearly $f(2a+1,2b)$ is equivalent mod $2$ to the number of tilings symmetric about the $a+1^{\text{st}}$ row. However, in all such tilings, the $a+1^{\text{st}}$ row must contain only horizontal dominoes. Hence, $f(2a+1,2b)\equiv f(a,2b)^2\pmod{2}$ and the claim is proved. Now we have all the tools to finish. Call positive integers $n$ for which $f(n,2k)$ is odd for every positive integer $k$ $\emph{good}$. By claim $1$, even numbers are not good. Since $1$ is good, by claim $2$ all numbers one less than a power of $2$ are good. Let $n$ be any odd number not one less than a power of $2$, and let $n'$ be the number obtained by truncating all $1$s in the binary representation of $n$ after the last $0$. Then by claim $2$, we have $f(n,n')\equiv f\left(\frac{n-1}{2},n'\right)\equiv \dots\equiv f(n',n')\equiv 0\pmod{2}$ so $n$ is not good. In summary, a number is good if and only if it is one less than a power of $2$.

This solution is same in spirit with the above solutions, only posting for storage purposes.

Lemma. For any positive integers $n$ and $k$, parities of $f(2n+1, 2k)$ and $f(n, 2k)$ are the same. Proof. Consider the reflection along the $(n+1)$-th row of the $(2n+1) \times 2k$ grid. A tiling is mapped onto itself under this reflection if and only if the $(n+1)$-th row is tiled with horizontal dominoes. Therefore, \[ f(2n+1, 2k) \equiv f(n, 2k)^2 \equiv f(n, 2k) \pmod{2}. \square\] Now, if $n = 2^m - 1$ for some positive integer $m$, then our lemma shows that $f(n, 2k) \equiv f(1, 2k) = 1 \pmod{2}$ for all positive integers $k$. Otherwise, if $n$ is not of the form $2^m - 1$, our lemma shows that there exists an even number $M$ such that $f(n, 2k) \equiv f(M, 2k) \pmod{2}$ for all positive integers $k$. However, note that $f(M, M)$ is even since no tiling is preserved under the reflection along the diagonal of a $M \times M$ grid. Hence, we are done.

A solution using some ideas from the proof of Kasteleyn's formula and some ideas from the official proof. It's my solution but the write up is from the coordinators of Problem 5. (I only changed color to colour.) Colour the board as a chessboard. Consider the bipartite graph whose vertices are the squares and the neighbors are connected by an edge. Notice that a domino tiling described in the problem corresponds to a perfect matching in this bipartite graph, so we are interested in the number of perfect matchings. And that is the permanent of the (bipartite) adjacency matrix. However we need to compute it mod 2 (over $F_2$), so that is the determinant of that matrix. So our goal is to decide whether the determinant is 0 or $1 \bmod 2$, or in other world, that matrix is singular or not. From now we compute everything $mod 2$. Now we understand what does it mean, that a vector $v$ is in the nullspace (has eigenvalue $0$). But each entry of $v$ is 0-1, so in other words we choose a subset of the black squares ($v$ is the characteristic vector of that subset). So in the language of the board, there is a nontrivial $v$ in the nullspace iff we have a subspace of black square such a way that each white square has even number of black chosen neighbors. If $n$ is even, then we can choose a subset such a way in the $n \times n$ square: the diagonal. Now we prove similar connection between $n$ and $2n + 1$: there is a construction for $n$ iff we have one for $2n + 1$. $k$ is always even. If we have a construction in $n × k$ then we have one in $(2n + 1) \times k$: we mirror the construction to the middle row. Now we prove that from a construction in $(2n+1)\times k$ we can make a construction in $n\times k$. First, we don’t have any chosen black square in the middle row. Then the chosen black squares in the upper (or lower) $n \times k$ rectangle is a construction for $n \times k$. Second, we have some chosen black square in the middle row. Because we can find a white square in the middle row such that is has only one chosen black neighbor in the middle row. Thus this construction isn’t symmetric to the horizontal line the symmetric difference of the construction and its reflection (to the vertical line) is a nontrivial vector in the nullspace, thus we can use the first case.

Snark_Graphique wrote: This solution is same in spirit with the above solutions, only posting for storage purposes.

Lemma. For any positive integers $n$ and $k$, parities of $f(2n+1, 2k)$ and $f(n, 2k)$ are the same. Proof. Consider the reflection along the $(n+1)$-th row of the $(2n+1) \times 2k$ grid. A tiling is mapped onto itself under this reflection if and only if the $(n+1)$-th row is tiled with horizontal dominoes. Therefore, \[ f(2n+1, 2k) \equiv f(n, 2k) \equiv f(n, 2k) \pmod{2}. \square\] Now, if $n = 2^m - 1$ for some positive integer $m$, then our lemma shows that $f(n, 2k) \equiv f(1, 2k) = 1 \pmod{2}$ for all positive integers $k$. Otherwise, if $n$ is not of the form $2^m - 1$, our lemma shows that there exists an even number $M$ such that $f(n, 2k) \equiv f(M, 2k) \pmod{2}$ for all positive integers $k$. However, note that $f(M, M)$ is even since no tiling is preserved under the reflection along the diagonal of a $M \times M$ grid. Hence, we are done. erm i am a newbie, but what does saving storage mean?

I claim the answer is all $n$ of the form $\boxed{2^m-1}$. Claim: $n$ is odd Proof: If $n$ was even, then we need $f(n, n)$ to be odd. But take the top left square; we can have it facing two orientations both are symmetric which is a contradiction. Claim: $f(n, 2k) \equiv f(2n+1, 2k) \pmod{2}$. Proof: Take the $n+1$th row (or column depending on orientation). We can pair up configurations not symmetric about this by reflection, so modulo 2 we only consider the ones symmetric about that column/row. This splits it into two $f(n, 2k)$ ones, establishing that $f(2n+1, 2k) \equiv f(n, 2k)^2$ which implies the claimed. Then, if $n$ works we have $\frac{n-1}{2}$ works etc. This process stops only when we reach an even number or one. By the first claim it must be the latter case. Now its trivial to see that $n$ is of the claimed form. To show that $1$ works, notice that it is always $1$. This finishes.