2022 China Team Selection Test for IMO

Proof: For map $f:D\to \mathbb{Z}$, we define a map $g:D\to \mathbb{Z}$ to be $$g(k)=\sum _{d|k}f(d),\forall k\in D.$$ By Möbius transform, the map $f$ is uniquely determined by $g$: $$f(k)=\sum _{d|k}\mu \left(\frac{k}{d}\right)g(d),\forall k\in D,$$ Therefore we have $$\begin{array}{rl}\sum _{d|m}f(d)\left(\genfrac{}{}{0ex}{}{n/d}{m/d}\right)& =\sum _{d|m}\sum _{x|d}\mu \left(\frac{d}{x}\right)g(x)\left(\genfrac{}{}{0ex}{}{n/d}{m/d}\right)\\ & =\sum _{x|m}g(x)\left(\sum _{x|d,d|m}\mu \left(\frac{d}{x}\right)\left(\genfrac{}{}{0ex}{}{n/d}{m/d}\right)\right)\\ & =\sum _{x|m}g(x)\left(\sum _{s|\frac{m}{x}}\mu (s)\left(\genfrac{}{}{0ex}{}{n/(xs)}{m/(xs)}\right)\right).\end{array}\text{\hspace{1em}(1)}$$ We need the following Lemma: If $b|a$, then $$\sum _{k|b}\mu (k)\left(\genfrac{}{}{0ex}{}{a/k}{b/k}\right)\equiv 0(\mathrm{mod}a).$$ Assuming this lemma temporarily, we prove that (A) and (B) are equivalent. (The proof of the lemma will be given later.) “(B) ⇒ (A)” Suppose that for every $x\in D$ we have $x\mid g(x)$. The lemma implies that $$\frac{n}{x}\mid \sum _{s|\frac{m}{x}}\mu (s)\left(\genfrac{}{}{0ex}{}{m/(xs)}{n/(xs)}\right),$$

"(A) ⇒ (B)" Suppose that (A) holds. We use induction to prove that for $k\in D$, we always have $k|g(k)$. Suppose that we have already proved $k|g(k)$ for $k<m$ and $k\in D$. Consider case of $k=m$. By Lemma and the inductive hypothesis, we have $$\begin{array}{rl}0& \equiv \sum _{d|m}f(d)\left(\genfrac{}{}{0ex}{}{n/d}{m/d}\right)\equiv \sum _{x|m}g(x)\left(\sum _{s|\frac{m}{x}}\mu (s)\left(\genfrac{}{}{0ex}{}{n/(xs)}{m/(xs)}\right)\right)\\ & \equiv g(m)\cdot \frac{n}{m}+\sum _{x|m,x<m}g(x)\left(\sum _{s|\frac{m}{x}}\mu (s)\left(\genfrac{}{}{0ex}{}{n/(xs)}{m/(xs)}\right)\right)\\ & \equiv g(m)\cdot \frac{n}{m}(\text{mod }n),\end{array}$$ From this we get $m|g(m)$, completing the induction.

It remains to prove the lemma. Note that $$\sum _{k|b}\mu (k)\left(\genfrac{}{}{0ex}{}{a/k}{b/k}\right)=\frac{a}{b}\sum _{k|b}\mu (k)\left(\genfrac{}{}{0ex}{}{\frac{a}{k}-1}{\frac{b}{k}-1}\right),$$ Let $b={\prod }_{i=1}^t{p}_i^{{\beta }_i}$ be the prime factorization. Then we only need to prove $$\sum _{k|b}\mu (k)C_{\frac{b}{k}-1}^{\frac{b}{k}-1}\equiv 0(\mathrm{mod}{p}_i^{{\beta }_i}).$$ for every $1\le i\le t$. For this, we may assume that $i=1$. Denote $p_1^{{\beta }_1}=p^{\beta }$. Note that $$\begin{array}{rl}& \sum _{k|b}\mu (k)\left(\genfrac{}{}{0ex}{}{\frac{a}{k}-1}{\frac{b}{k}-1}\right)\\ & =\sum _{I\subset \{1,\dots ,t\}}(-1{)}^{|I|}\left(\frac{{\prod }_{i\in I}\frac{a}{p_i}}{{\prod }_{i\in I}\frac{b}{p_i}}-1\right)\\ & =\sum _{J\subset \{2,\dots ,t\}}(-1{)}^{|J|}\left(\left(\frac{{\prod }_{j\in J}\frac{a}{p_j}}{{\prod }_{j\in J}\frac{b}{p_j}}-1\right)-\left(\frac{{\prod }_{j\in J}\frac{a}{p_j}}{{\prod }_{j\in J}\frac{b}{p_j}}-1\right)\right)\end{array}$$ Then it suffices to show: if $u,v$ are multiples of $p^{\beta }$, then $$\left(\genfrac{}{}{0ex}{}{u-1}{v-1}\right)-\left(\genfrac{}{}{0ex}{}{\frac{u}{p}-1}{\frac{v}{p}-1}\right)\equiv 0(\mathrm{mod}{p}^{\beta }).(2)$$ Put $w=u-v$. Then $$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{u-1}{v-1}\right)& =\frac{{\prod }_{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r+w)\cdot {\prod }_{1\le y\le \frac{v}{p}-1}(yp+w)}{{\prod }_{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r)\cdot {\prod }_{1\le y\le \frac{v}{p}-1}(yp)}\\ & =\frac{{\prod }_{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r+w)}{{\prod }_{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r)}\cdot \left(\genfrac{}{}{0ex}{}{\frac{u}{p}-1}{\frac{v}{p}-1}\right).\end{array}$$

Since $w$ is divisible by $p^{\beta }$, we get $$\begin{array}{rl}& \left(\begin{array}{c}u-1\\ v-1\end{array}\right)\prod _{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r)\\ & =\left(\begin{array}{c}\frac{u}{p}-1\\ \frac{v}{p}-1\end{array}\right)\prod _{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r+w)\\ & =\left(\begin{array}{c}\frac{u}{p}-1\\ \frac{v}{p}-1\end{array}\right)\prod _{0\le x\le \frac{v}{p}-1,1\le r\le p-1}(xp+r)(\mathrm{mod}{p}^{\beta }),\end{array}$$ So (2) holds, and we complete the proof of the lemma. Another proof of the lemma: We will use the following fact. Let $X$ be a finite set, and let $h:X\to X$ be a map such that $h^{(a)}={\text{Id}}_X$. Under the action of $h$, $X$ is divided into some orbits. Each orbit looks like $\{x,h(x),h^{(2)}(x),\dots ,h^{(l)}(x)=x\}$, where $l$ is the smallest positive integer such that $h^{(l)}(x)=x$; we call $l$ the length of the orbit. Since $h^{(a)}={\text{Id}}_X$, the length $l$ of every orbit is a divisor of $a$. For every divisor $l$ of $n$, let $N(l)$ be the number of orbits with length $l$. For every positive integer $k|a$, let $$m(k)=\#\{x\in X:h^{(k)}(x)=x\},$$ then $m(k)={\sum }_{l|k}N(l)l$. Therefore we get $$\begin{array}{rl}\sum _{k|a}\mu (k)m\left(\frac{a}{k}\right)& =\sum _{k|a}\sum _{l|\frac{a}{k}}\mu (k)N(l)l\\ & =\sum _{l|a}N(l)l\sum _{k|\frac{a}{l}}\mu (k)\\ & =N(a)a.\end{array}$$ In particular, we have $$\sum _{k|a}\mu (k)m\left(\frac{a}{k}\right)\equiv 0(\mathrm{mod}a).(3)$$ We apply this to the following model. Let $X$ be the set of all subsets of $\mathbb{Z}/a$ of $b$ elements. Define $h:X\to X$ to be $$h(\{y_1,\dots ,y_b\})=\{y_1+1,\dots ,y_b+1\},\forall \{y_1,\dots ,y_b\}\in X.$$ In this model, for every divisor $k$ of $a$, we have $$m(k)=\left(\genfrac{}{}{0ex}{}{k}{b/(a/k)}\right).$$ Then (3) implies that $$\sum _{k|a}\mu (k)\left(\genfrac{}{}{0ex}{}{a/k}{b/k}\right)\equiv 0(\mathrm{mod}a).$$