The 35th Japanese Mathematical Olympiad

$858$

In this solution, $x\equiv y$ always means that $x-y$ is divisible by $9$. Furthermore, for any integer $x$, we denote by $[x]$ the unique element $x^{\prime }\in S$ satisfying $x\equiv x^{\prime }$. Note that for any integers $s$ and $t$, we have $[[s-t]+t]=[s]$ and $[s[t]]=[st]$.

Under this notation, the condition in the problem can be rewritten as $$f(x)f(y)\equiv f(f([x+y]))$$ for any elements $x,y\in S$. We denote this equation by $P(x,y)$.

Define $T=\{f(x)\mid x\in S\}$. For any elements $s=f(x)$ and $t=f(y)$ in $T$, note that $$[st]=[f(x)f(y)]=f(f([x+y]))\in T.$$

First, consider the case where $T$ contains a multiple of $3$. Let $a$ be such an element. Then, since $0=[a^2]\in T$, there exists some $b\in S$ such that $f(b)=0$. Therefore, we have $f(f(x))=0$ for any $x\in S$ since $P([x-b],b)$ gives $$f(f(x))\equiv f([x-b])f(b)=0.$$ Furthermore, $f(x)$ is a multiple of $3$ since $P(x,x)$ gives $$f(x{)}^2\equiv f(f([2x]))=0.$$ Conversely, suppose that for every $x\in S$, we have $f(f(x))=0$ and $f(x)$ is a multiple of $3$. Then such $f$ satisfies the condition because for any $x,y\in S$, both sides of $P(x,y)$ are divisible by $9$.

Since $T$ contains $0$, the condition that $f(x)$ is a multiple of $3$ for all $x\in S$ is equivalent to $T$ being one of $\{0\}$, $\{0,3\}$, $\{0,6\}$, or $\{0,3,6\}$. Furthermore, the condition that $f(f(x))=0$ for all $x\in S$ is equivalent to saying that $f(x)=0$ for all $x\in T$. In the following, we consider each of the four possible cases for $T$ and count the number of possible functions $f$ in each case.

When $T=\{0\}$, there is only one function $f$, namely $f(x)=0$ for all $x$. When $T=\{0,3\}$, the number of such functions $f$ is the number of ways to assign $f(x)=0$ or $3$ for each $x\in S\setminus T=\{1,2,4,5,6,7,8\}$, such that there is at least one $x$ with $f(x)=3$. There is exactly one way to assign all values to $0$, so the number of valid functions $f$ is $2^7-1=127$. When $T=\{0,6\}$, by the same reason, the number of such functions $f$ is also $127$. When $T=\{0,3,6\}$, the number of such functions $f$ is the number of ways to assign $f(x)=0,3$, or $6$ for each $x\in S\setminus T=\{1,2,4,5,7,8\}$ such that there is at least one $x$ with $f(x)=3$ and at least one $y$ with $f(y)=6$. There are $2^6$ ways where $f(x)\ne 3$ for all $x\in S\setminus T$, and $2^6$ ways where $f(y)\ne 6$ for all $y\in S\setminus T$, and one way where $f(x)\ne 3,6$ for all $x\in S\setminus T$. So the number of valid functions $f$ in this case is $3^6-2^6-2^6+1=602$.

$$1+127+127+602=857.$$

Next, we consider the case where $T$ does not contain any multiples of $3$. Since $T$ is nonempty, we can take an element $a$ of $T$. Because $a$ is not divisible by $3$, Euler's theorem gives $a^6\equiv 1$, so we have $1=[a^6]\in T$. Thus, there exists some $b\in S$ such that $f(b)=1$. Therefore, we have $f(0)=f(1)$ since $P(b,0)$ gives $$f(0)=f(b)f(0)\equiv f(f(b))=f(1).$$ Furthermore, for any $x\in S$, from $P(x,[-x])$ and $P([x+1],[-x])$, we obtain $$f(x)f([-x])\equiv f(f(0))=f(f(1))\equiv f([x+1])f([-x]).$$ Thus, we have $$f([-x])(f([x+1])-f(x))\equiv 0.$$ Since $f([-x])$ is not divisible by $3$, we conclude that $$f([x+1])=f(x)$$ holds for every $x\in S$. Therefore, the set $T$ has exactly one element. Since $1\in T$, we must have $T=\{1\}$, which does not contain a multiple of $3$. The constant function $f(x)=1$ is the only function with this property. Conversely, this function satisfies the condition because both sides of $P(x,y)$ equal $1$ for any $x,y\in S$.

Hence, the total number of possible functions $f$ is $857+1=858$.