Given two positive integers $n$ and $m$ and a function $f : \mathbb{Z} \times \mathbb{Z} \to \left\{0,1\right\}$ with the property that \begin{align*} f\left(i, j\right) = f\left(i+n, j\right) = f\left(i, j+m\right) \qquad \text{for all } \left(i, j\right) \in \mathbb{Z} \times \mathbb{Z} . \end{align*}Let $\left[k\right] = \left\{1,2,\ldots,k\right\}$ for each positive integer $k$. Let $a$ be the number of all $\left(i, j\right) \in \left[n\right] \times \left[m\right]$ satisfying \begin{align*} f\left(i, j\right) = f\left(i+1, j\right) = f\left(i, j+1\right) . \end{align*}Let $b$ be the number of all $\left(i, j\right) \in \left[n\right] \times \left[m\right]$ satisfying \begin{align*} f\left(i, j\right) = f\left(i-1, j\right) = f\left(i, j-1\right) . \end{align*}Prove that $a = b$.
Problem
Source: German TST 2022, exam 2, problem 2
Tags: combinatorics, Enumerative Combinatorics, function
12.03.2022 01:19
I think a slightly more interesting question is when the $a$ and $b$ are only counting all such couples in $\{0,....,n-1\}\times \{0,...,m-1\}$. What the first condition is basically stating is that the function is periodic in both arguments, or in other words we may equivalently consider the same function but from $\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}$, which we may identify with $\{0,...,n-1\}\times \{0,...,m-1\}$. (Where $0,n$ and $0,m$ are considered the same respectively). We may proceed by induction on the number of $1$s in this "fundamental domain" (which we from now on call $S$). If this number is $0$, i.e. $f(x,y)=0\forall (x,y)\in S$, we trivially have $a=b=mn$. Now, consider the case where (wlog) $m=1$. In this case, since the function is periodic in the second argument, we have an L-omino if and only if we have a ┐-omino (this can happen iff $f(x,0)=f(x+1,0)\implies f(x,1)=f(x,0)=f(x+1,0)=f(x+1,-1)$). Now, consider the case when both $m,n\geq 2$, so that if we change a position its neighbours can't change. So if we change the position $(x,y)$, the only triominos it can affect are the ones with $(x+1,y),(x,y+1),(x-1,y+1),(x-1,y),(x-1,y),(x+1,y-1)$ [call this points $A_1,...,A_6$ and $(x,y)$ $P$] so that we can form triominoes with $P,A_i,A_{i+1}$, and it is a L-omino iff $i$ is odd. If $f(A_i)\neq f(A_{i+1})$ we can't create a uniform triomino (a triomino in which all three elements have the same image under $f$) neither before nor after the change, so we only care about the ones with $f(A_i)=f(A_{i+1})$. So, up to flipping all the elements (which just switches the sign of the changes in $a$ and $b$) and up to cyclic permutation/reversals we have just a few possible cases for the values of the changes of $a$ and $b$ as a function of $f(A_1),...,f(A_6)$, which we list below: I)$000000$ in this case $\Delta a=\Delta b=-3$ II)$100000$ in this case $\Delta a=\Delta b=-2$ III)$110000$ in this case $\Delta a=\Delta b=-1$ IV)$101000$ in this case $\Delta a=\Delta b=-1$ V)$100100$ in this case $\Delta a=\Delta b=-1$ VI)$111000$ in this case $\Delta a=\Delta b=0$ VII)$110100$ in this case $\Delta a=\Delta b=0$ VIII)$101010$ in this case $\Delta a=\Delta b=0$ Therefore, since in all cases the change in $a$ is always equal in $b$, it follows that in any configuration $a=b$. [Remark: in the original problem we would either have $a=b=0$ or $a=b=\infty$, since the above quantity gets multiplied for every copy of the fundamental domain $S$]
12.03.2022 01:23
Oops, fixed the unintentionally infinite sets -- I mistyped them from my own problem set... (I should probably have just copypasted, but it was in German.) Your approach is one of the possible solutions, though I'm not sure if these cases are all that can appear (I don't quite see what you mean by "up to cyclic permutations"). There are some nicer solutions.
12.03.2022 01:34
darij grinberg wrote: I don't quite see what you mean by "up to cyclic permutations" Basically, if you shift (maybe permute is a bit wrong here) by some number $k$ (i.e. $f(A_{i})$ becomes $f(A_{i+k})$) the situation doesn't change so much and the changes $\Delta a$ and $\Delta b$ (the may swap if $k$ is odd, but since in any case $\Delta a=\Delta b$ this doesn't matter) stay the same. For example, one can see that $010000$ still brings to $\Delta a=\Delta b=-2$. If one really wanted to he could check all $2^6=64$ cases but they are basically the same. Anyway I agree that there might be better solutions, maybe also based on the idea of the same "hexagon" $A_1...A_6$ i described around a certain point $P$.
12.03.2022 14:51
This is probably the easier solution: Let $S=\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}$, which of course can be identified with $[n]\times [m]$, and let $\mathcal{L}$ and $\mathcal{L}'$ the sets of L-ominoes and ┐-ominoes (which can be expressed in the form $T=\{u,v,w\}\subseteq\mathcal{P}(S)$). Now for a triomino $T$, let $\chi(T)$ be $1$ if $T$ is uniform (its three elements have equal image under $f$) and $0$ otherwise. It is easier to see that we can express it in the form $\chi(T)=f(u)f(v)f(w)+(1-f(u))(1-f(v))(1-f(w))$, since either all three elements are sent to $1$ or all three are sent to $0$. Now, let us consider $S$ as a graph where $u\sim v$ only if they belong to some common triomino; it is easy to see that if $u\sim v$, then they both belong to exactly two triominoes(and one L-omino), and that every $u\in S$ belongs to exactly $6$ triominoes ($3$ of which are L-ominoes). Therefore, $$a=\sum_{T\in\mathcal{L}}\chi(T)=\sum_{\{u,v,w\}=T\in\mathcal{L}}f(u)f(v)f(w)+(1-f(u))(1-f(v))(1-f(w))$$$$=\sum_{\{u,v,w\}=T\in\mathcal{L}} 1-(f(u)+f(v)+f(w))+(f(u)f(v)+f(v)f(w)+f(w)f(u))=$$$$=|\mathcal{L}|-3\sum_{u\in S}f(u)+\sum_{u\sim v}f(u)f(v)$$In a similar way, we obtain $$b=|\mathcal{L}'|-3\sum_{u\in S}f(u)+\sum_{u\sim v}f(u)f(v)$$Therefore, since $|\mathcal{L}|=|\mathcal{L}'|=|S|=mn$, we have the equality $a=b$.
13.03.2022 00:44
Whoa, cadaeibf, this is really nice! I used a similar approach in my second model solution, but I didn't notice the fact that cadaeibf wrote: if $u\sim v$, then they both belong to exactly two triominoes(and one L-omino) which simplifies the calculation significantly.