Determine all pairs of positive integers $(m, n)$ for which there exists a bijective function \[f : \mathbb{Z}_m \times \mathbb{Z}_n \to \mathbb{Z}_m \times \mathbb{Z}_n\]such that the vectors $f(\mathbf{v}) + \mathbf{v}$, as $\mathbf{v}$ runs through all of $\mathbb{Z}_m \times \mathbb{Z}_n$, are pairwise distinct. (For any integers $a$ and $b$, the vectors $[a, b], [a + m, b]$ and $[a, b + n]$ are treated as equal.) Poland, Wojciech Nadara
Problem
Source: 2020 RMM Shortlist N1
Tags: number theory, function, RMM, RMM 2020, RMM Shortlist
08.10.2022 22:26
This is also P12 from 1st stage of Polish MO 2020
09.10.2022 17:48
https://artofproblemsolving.com/community/c6h2799803p24680787
20.02.2023 13:35
The required pairs (call them good) are precisely those having both entries of the same parity. Clearly, entry swap preserves goodness. For convenience, a bijection satisfying the condition in the definition of a good pair will be called suitable for that pair. We first rule out pairs of positive integers of opposite parity. Let $(m, n)$ be one such, say $m{}$ is even and $n{}$ is odd. The first entry of the sum of all vectors in $\mathbb{Z}_m\times\mathbb{Z}_n$ is \[(0+1+\cdots+(m-1))\cdot n =n\cdot\frac{m(m-1)}{2}\equiv\frac{m}{2}\pmod{m}.\]Consequently, should a suitable $f{}$ exist for $(m, n)$, the first entry of the sum of $f(\mathbf{v}) + \mathbf{v}$, as $\mathbf{v}$ runs through all of $\mathbb{Z}_m \times \mathbb{Z}_n$, would be $2\cdot m/2\equiv0\bmod{m}$ which is a contradiction. Next, we show that any pair of positive odd integers is good. Let $m{}$ and $n{}$ be two such. The identity $f{}$ of $\mathbb{Z}_m \times \mathbb{Z}_n$ is suitable, since the vectors \[f(x,y)+(x,y)=(2x\bmod m,2y\bmod n),\quad (x,y)\in\mathbb{Z}_m\times\mathbb{Z}_n,\]are pairwise distinct due to $m{}$ and $n{}$ being both odd. Finally, we show that any pair of positive even integers is also good. Let $m{}$ and $n{}$ be two such. If $m = 2$, a quick check shows that $f : \mathbb{Z}_2 \times\mathbb{Z}_n\to \mathbb{Z}_2 \times\mathbb{Z}_n$, defined below for $0 \leqslant r < n/2$ by \[f(0,r)=(0,r),\quad f(1,r)=\left(0,r+\frac{n}{2}\right),\quad f\left(0,r+\frac{n}{2}\right)=(1,r+1),\quad f\left(1,r+\frac{n}{2}\right)=\left(1,r+\frac{n}{2}+1\right),\]is a suitable bijection for the pair $(2, n)$. For a generic pair of positive even integers the argument hinges on the lemma below. Lemma. If $(a, b)$ and $(c, d)$ are both good, then so is $(ac, bd)$. Proof. In this lemma, we need to deal with residue classes modulo different numbers; so it is suitable to reformulate the setting as follows. Let $[n]$ denote the set $\{0,1,\ldots n-1\}$. For pairs $(x,y),(x',y')\in\mathbb{Z}^2$ we write $(x,y)\equiv (x',y')\bmod{(m,n)}$ if and only if $x\equiv x'\bmod m$ and $y\equiv y'\bmod{n}$. A suitable bijection for a pair $(m, n)$ is a bijection $f:[m]\times[n]\to[m]\times[n]$ such that\[f(\mathbf{v})+\mathbf{v}\equiv f(\mathbf{v}')+\mathbf{v}'\bmod{(m,n)}\]yields $\mathbf{v}=\mathbf{v}'$ for all $\mathbf{v},\mathbf{v}'\in[m]\times[n]$. In this setting, given suitable bijections $f{}$ and $g{}$ for the pairs $(a, b)$ and $(c, d)$, respectively, we exhibit a suitable bijection $h{}$ for the pair $(ac, bd)$. We denote by $f_1$ and $f_2$ the components of $f$. The components of $g{}$ and $h{}$ are denoted accordingly. Each element in $[ac] \times [bd]$ is uniquely expressible in the form $(ax_1, by_1) + (x_2, y_2)$, where $(x_1,y_1)\in[c]\times[d]$ and $(x_2,y_2)\in[a]\times[b].$ Now we define \[h((ax_1,by_1)+(x_2,y_2))=(ag_1(x_1,y_1),bg_2(x_1,y_1))+f(x_2,y_2).\]The uniqueness of representation shows that $h{}$ is a well-defined bijection. To show it is suitable, assume that\[h(\mathbf{v})+\mathbf{v}\equiv h(\mathbf{v}')+\mathbf{v}'\bmod{(ac,bd)}\]for some $\mathbf{v}=(ax_1,by_1)+(x_2,y_2)$ and $\mathbf{v}'=(ax_1',by_1')+(x_2',y_2')$ in $[ac]\times [bd]$. Comparing the two vectors modulo $(a, b)$ provides \[f(x_2,y_2)+(x_2,y_2)\equiv f(x_2',y_2')+(x_2',y_2')\bmod{(a,b)},\]so $(x_2,y_2)=(x_2',y_2')$ as $f$ is suitable for $(a,b)$. Therefore, the initial congruence yields \[g(x_1,y_1)+(x_1,y_1)\equiv g(x_1',y_1')+(x_1',y_1')\bmod{(c,d)},\]so $(x_1,y_1)=(x_1',y_1')$, since $g{}$ is suitable for $(c, d)$. The conclusion follows. $\square$ Back to generic pairs of positive even integers, write $m = 2^ka$ and $n = 2^\ell b$, where $k{}$ and $\ell{}$ are both positive integers, and $a{}$ and $b{}$ are both odd. To conclude the solution, recall that entry swap preserves goodness, to assume that $k \leqslant \ell$, and apply the lemma repeatedly for the string of pairs \[\underbrace{(2,2),(2,2),\ldots,(2,2)}_{k-1},(2,2^{\ell-k+1}),(a+b),\]each of which falls in one of the previously considered cases.