Given an even positive integer $m$, find all positive integers $n$ for which there exists a bijection $f:[n]\to [n]$ so that, for all $x,y\in [n]$ for which $n\mid mx-y$, $$(n+1)\mid f(x)^m-f(y).$$ Note: For a positive integer $n$, we let $[n] = \{1,2,\dots, n\}$. Proposed by Milan Haiman and Carl Schildkraut
Problem
Source: 2019 ELMO Shortlist N5
Tags: number theory, Elmo
28.06.2019 16:44
Can I get a bit of clarifications for this? The header says FE from $\mathbb{Z}_n$ to $\mathbb{Z}_{n+1}$ but the function here is of type $[n] \rightarrow [n]$. Is it actually $[n] \rightarrow [n+1]$? Thank you. Edit: Nvm kinda feel stupid now; obviously it can't be $[n] \rightarrow [n+1]$ ($f$ is said to be bijective).
28.06.2019 22:57
BlazingMuddy wrote: Can I get a bit of clarifications for this? The header says FE from $\mathbb{Z}_n$ to $\mathbb{Z}_{n+1}$ but the function here is of type $[n] \rightarrow [n]$. Is it actually $[n] \rightarrow [n+1]$? Thank you. Edit: Nvm kinda feel stupid now; obviously it can't be $[n] \rightarrow [n+1]$ ($f$ is said to be bijective). What's basically going on here is a bijection from $\mathbb{Z}_n$ to the nonzero elements of $\mathbb{Z}_{n+1}$, as the predicate on $(x,y)$ is a condition $\bmod n$ while the requirement on $(f(x),f(y))$ is a condition $\bmod (n+1)$.
17.07.2019 11:28
31.12.2019 10:03
BlazingMuddy wrote:
Why “ But since $m$ is even, there must then be more such $y$ than such $x$”?
06.11.2020 11:15
Nice problem !
16.11.2020 18:58
After long hours of grinding (m,n) such as (6,14) and (6,16) ... Also, this problem is not combi (for those who think otherwise). $\textcolor{green}{\textbf{\text{Notational convenience.}}}$ Since this is longer than necessary, I'm going to reference a number $x$ in the domain by $x_{(l)}$, but $x$ in the codomain will be referred as $x_{(r)}$ ($r$ is for "right" and "range"). For example, when $(m,n) = (6,14)$, I will say that \[ 14 \mid 6 \cdot 3_{(l)} - 4_{(l)},\ \text{and} \ 15 \mid 3_{(r)}^6-9_{(r)} \]Here we go a little bit beyond and create auxiliary graphs $G_d$ and $G_c$ (a.k.a. "fake" graphs that will, I hope, make the problem statement easier to comprehend.) In this case, I will say that $3_{(l)} \rightarrow 4_{(l)}$ forms an edge in $G_l$ and $3_{(r)} \rightarrow 9_{(r)}$ in $G_r$. To go full circle, we will say that $x_{(l)} \Rightarrow f(x)_{(r)}$ to represent the connection between a vertex $x_{(l)}$ in $G_l$ and $x_{(r)}$ in $G_r$. (If you don't get this $-$ it's totally fine, basically this is just saying to put $(l)$ under a number when we look at the left $[n]$ and $(r)$ under it when we look at the right $[n]$.) ${\color{green} \rule{25cm}{0.5pt}}$ $\textcolor{cyan}{\textbf{\text{Isomorphisms, Bijectives and elimination of cases.}}}$ First we will establish by the bijection in the problem statement that the two graphs $G_l$ and $G_r$ are isomorphic; and we first eliminate the easy cases $n+1 = p$ and $n+1$ not squarefree, using said isomorphism. Chunk 1: The problem statement goes both ways. Let it doesn't, for the sake of contradiction. Then, there exists $x_{(l)},y_{(l)}$ so that \[n+1 \mid f(x)^m - f(y), n \nmid mx - y \]However, letting $y'_{(l)} \equiv x_{(l)}$ mod $n$ yields \[n+1 \mid f(x)^m - f(y') \]so that $n+1 \mid f(y)-f(y')$, a contradiction. Chunk 2: Isomorphism. Match the vertices $x_{(l)}$ and $f(x)_{(r)}$. Note that since there exists an edge between vertices $u_{(l)}$ and $v_{(l)}$ in $G_l$ iff there exists a similar edge in $G_r$ by Chunk 1. Statement proven. Chunk 3: Easy cases. For $n+1 = p$, set $f(x) = g^x$ with $g$ primitive root of $p$, as in post $\#4$. For $n+1$ not squarefree, letting $p^2 \mid n+1$ yields a contradiction by noting that $n+1 \mid \left(\dfrac{n+1}{p}\right)_{(r)}^m - q_{(r)}$, but this is impossible since $q_{(r)} \equiv 0 \ \text{mod} \ n+1$ is not in the vertices of $G_r$. ${\color{green} \rule{25cm}{3pt}}$ So, now we can let $n+1 = \prod_{i \ne j} p_i.$ Here we proceed with a simple but central Lemma. $\textcolor{blue}{\textbf{\text{Lemma: Regularity of both graphs.}}}$ Each vertex in $G_l$ (in $G_r$, too, due to isomorphism) has outdegree $1$, and indegree either $0$ or $\text{gcd}(m,n)$. $\textbf{Proof.}$ Any $a_{(l)}$ has only one out-edge, that is with $ma_{(l)} \ (\text{mod} \ n)$. Moreover, it is easily seen that the equation \[ n \mid mx - a \]has no solutions if $(m,n) \nmid a$, implying $a_{(l)}$ has no indegree, or has $(m,n)$ solutions when $(m,n) \mid a$, implying $a_{(l)}$ has $(m,n)$ indegree. ${\color{blue} \rule{25cm}{1pt}}$ $\textcolor{red}{\textbf{\text{Finishing.}}}$ We now divide into two cases, first case being ($n$ odd, $n+1$ even) and ($n$ even, $n+1$ odd). Case 1. Note that $(m,n)$ odd. Because $n+1$ even, $n+1 = 2p_2 \ldots p_k$. Focusing on $\dfrac{n+1}{2}$, we let $(p_2 \ldots p_k)_{(r)} \rightarrow I_{(r)}$ ($I$ stands for identity and also indegree). Observe that all other $I'_{(r)} \ne I_{(r)}$ with positive indegree must have even indegree, because $x_{(r)} \rightarrow I'_{(r)}$ iff $(-x)_{(r)} \rightarrow I'_{(r)}$. Therefore, $f(x)_{(r)}^m = {(\text{any number})}_{(r)}^{m} \equiv I_{(r)} \ \text{mod} \ n+1$, so by setting $any \ number$ equal to $1$ and $2$, we get $1 \equiv 2 \ \text{mod} \ n+1$. Case 2. The idea here is to apply subtle CRT to "make" two vertices in $G_r$ have different indegrees. Noting that the equation \[ x^m \equiv 1 \ \text{mod} \ p_i \]have at least two solutions mod $p_i$, and the equation \[x^m \equiv 0\ \text{mod} \ p_i \]has only one solution ($0$) mod $p_i$, we use this idea to construct two numbers $u = 1$ and $a$ (unit, almost unit) so that \begin{align*} u &\equiv 1 \ \text{mod} \ p_1, \ldots, u \equiv 1 \ \text{mod} \ p_{k-1}, u \equiv 1 \ \text{mod} \ p_k \\ a &\equiv 1 \ \text{mod} \ p_1, \ldots, a \equiv 1 \ \text{mod} \ p_{k-1}, a \equiv 0 \ \text{mod} \ p_k \end{align*}Observe that if $x^m \equiv 1 \ \text{mod} \ p_i$ has $s_i$ solutions mod $p_i$, $u_{(r)}$ has $s_1\ldots s_{k-1} s_k$ indegree, but $a_{(r)}$ has only $s_1 \ldots s_{k-1}$ indegree. This is due to setting $f(y) = u,a$ in the original equation to get solutions in $f(x)$. We are done.
analysis90 wrote: BlazingMuddy wrote:
Why “ But since $m$ is even, there must then be more such $y$ than such $x$”? This uses a similar idea in my proof for Case 2. , as when $m$ is even, $y^m \equiv 1\pmod{p_i}, 1 \leq i \leq k-1$ has more than $1$ solution, and couple that with $y^m \equiv 1 \pmod{p_k}$ yields so many solutions in $y$ compared to the highly specific condition $p_i \mid x$ for $i \leq k-1$ which yields only $1$ solution $\pmod{p_1\ldots p_{k-1}}$.
Attachments:
ELMO 2019 N5.pdf (414kb)