Japan Mathematical Olympiad

We denote $$X_{\max }(f,g)=\sum _{k=1}^{3000}\max \{f(f(k)),f(g(k)),g(f(k)),g(g(k))\},$$ $$X_{\min }(f,g)=\sum _{k=1}^{3000}\min \{f(f(k)),f(g(k)),g(f(k)),g(g(k))\},$$ and $X(f,g)=X_{\max }(f,g)-X_{\min }(f,g)$. Moreover, for a finite set $T$, we denote the number of its elements by $|T|$.

First, we will prove that the answer is at most $6000000$. When the bijection $f$ is the identity map, for any bijection $g$ on $S$, we have $f\circ g=g\circ f$. For any $a\in S$, since the function $f\circ f$ is bijective, the equation $f(f(x))=a$ for $x$ has at most one solution. The same is true for the bijections $f\circ g=g\circ f$ and $g\circ g$. Therefore, the equation $\max \{f(f(x)),f(g(x)),g(f(x)),g(g(x))\}=a$ for $x$ has at most three solutions. Hence we have $$X_{\max }(f,g)\le 3\times 3000+3\times 2999+\cdots +3\times 2001=\sum _{k=2001}^{3000}3k,$$ and similarly, $$X_{\min }(f,g)\ge 3\times 1+3\times 2+\cdots +3\times 1000=\sum _{k=1}^{1000}3k.$$ Therefore, $$X(f,g)\le \sum _{k=2001}^{3000}3k-\sum _{k=1}^{1000}3k=6000000.$$ Hence, the answer is at most $6000000$.

In the following, we will prove that $X=6000000$ satisfies the condition. We denote $$S_1=\{1,2,\dots ,1000\},S_2=\{1001,1002,\dots ,2000\},S_3=\{2001,2002,\dots ,3000\}.$$ Additionally, for $a,b\in \{1,2,3\}$, let $S_{a,b}=\{x\in S_a\mid f(x)\in S_b\}$ and $n_{a,b}=|S_{a,b}|$. Now, for any $x\in S$, there exists exactly one pair $(a,b)\in \{1,2,3{\}}^2$ such that $x\in S_{a,b}$.

Lemma. For any bijection $f$ on $S$, there exists a partition $\{Z_1,Z_2,\dots ,Z_{1000}\}$ of $S$ satisfying the following condition: For any $1\le i\le 1000$, $|Z_i|=3$ and when $a_1,a_2,a_3$ denote the elements of $Z_i$ in ascending order, we have $a_1\in S_1,a_2\in S_2$ and $a_3\in S_3$. In addition, exactly one element of $\{f(a_1),f(a_2),f(a_3)\}$ belongs to $S_b$ for every $b\in \{1,2,3\}$.

Proof. Assume that there exists a tuple $(A_1,B_1,A_2,B_2,A_3,B_3)$ of non-negative integers satisfying the equations: $$\begin{array}{rlrlrlr}{A}_1+B_1& =n_{1,1},& A_2+B_2& =n_{1,2},& A_3+B_3& =n_{1,3},& \\ A_3+B_2& =n_{2,1},& A_1+B_3& =n_{2,2},& A_2+B_1& =n_{2,3},& (\ast )\\ A_2+B_3& =n_{3,1},& A_3+B_1& =n_{3,2},& A_1+B_2& =n_{3,3}.& \end{array}$$ Then, we have a partition $\{Z_1,\dots ,Z_{1000}\}$ of $S$ which satisfies the condition in the lemma and the following condition: For each $Z_i=\{a_1,a_2,a_3\}$ with $a_1<a_2<a_3$, define a permutation ${\sigma }_i$ of $\{1,2,3\}$ such that $a_k\in S_{k,{\sigma }_i(k)}$ for $k=1,2,3$. Then the number of $Z_i$ such that $({\sigma }_i(1),{\sigma }_i(2),{\sigma }_i(3))$ is equal to $(1,2,3)$, $(1,3,2)$, $(2,3,1)$, $(2,1,3)$, $(3,1,2)$, and $(3,2,1)$ is equal to $A_1,B_1,A_2,B_2,A_3$ and $B_3$, respectively. Hence it is sufficient to prove that a tuple $(A_1,B_1,A_2,B_2,A_3,B_3)$ satisfying the equations $(\ast )$ exists.

Without loss of generality, we can assume that $n_{1,1}$ is the smallest among nine integers $n_{a,b}$ ($a,b\in \{1,2,3\}$). Setting $$(A_1,B_1,A_2,B_2,A_3,B_3)=(n_{1,1},0,n_{2,3},n_{3,3}-n_{1,1},n_{3,2},n_{2,2}-n_{1,1}),$$ this is a tuple of non-negative integers by the minimality of $n_{1,1}$, and satisfies the first, fifth, sixth, eighth, and ninth equations in $(\ast )$. Furthermore, for any $a\in \{1,2,3\}$, we have $$\begin{array}{rl}{n}_{a,1}+n_{a,2}+n_{a,3}& =|S_a|=1000,\\ n_{1,a}+n_{2,a}+n_{3,a}& =|\{x\in S\mid f(x)\in S_a\}|=1000.\end{array}$$ Thus, we find that the tuple satisfies the second, third, fourth, and seventh equations in $(\ast )$: $$A_2+B_2=n_{2,3}+n_{3,3}-n_{1,1}=(n_{1,3}+n_{2,3}+n_{3,3})-(n_{1,1}+n_{1,2}+n_{1,3})+n_{1,2}=n_{1,2},$$ $$A_3+B_3=n_{3,2}+n_{2,2}-n_{1,1}=(n_{1,2}+n_{2,2}+n_{3,2})-(n_{1,1}+n_{1,2}+n_{1,3})+n_{1,3}=n_{1,3},$$ $$A_3+B_2=n_{3,2}+n_{3,3}-n_{1,1}=(n_{3,1}+n_{3,2}+n_{3,3})-(n_{1,1}+n_{2,1}+n_{3,1})+n_{2,1}=n_{2,1},$$ $$A_2+B_3=n_{2,3}+n_{2,2}-n_{1,1}=(n_{2,1}+n_{2,2}+n_{2,3})-(n_{1,1}+n_{2,1}+n_{3,1})+n_{3,1}=n_{3,1},$$ which completes the proof. ■

Let us consider $Z_j=\{a_1,a_2,a_3\}$ with $a_1<a_2<a_3$. Then $a_1\in S_1$, $a_2\in S_2$ and $a_3\in S_3$. For each $i\in \{1,2,3\}$, we define $k_i$ by $f(k_i)=a_i$. Since $g(k_i)=h(f(k_i))=h(a_i)=a_{i+1}$, we obtain $$\begin{array}{rl}\max \{f(f(k_i)),f(g(k_i)),g(f(k_i)),g(g(k_i))\}& =\max \{f(a_i),f(a_{i+1}),g(a_i),g(a_{i+1})\}\\ & =\max \{f(a_i),f(a_{i+1}),h(f(a_i)),h(f(a_{i+1}))\},\end{array}$$ where $a_4=a_1$. Let us define $F_1,F_2,F_3$ by $\{f(a_1),f(a_2),f(a_3)\}=\{F_1,F_2,F_3\}$ and $F_1<F_2<F_3$. By the condition of the lemma, we have $F_1\in S_1$, $F_2\in S_2$ and $F_3\in S_3$. Furthermore, we have $h(F_1)\in S_2$, $h(F_2)\in S_3$ and $h(F_3)\in S_1$, by the definition of $h$. Therefore, we obtain $$\begin{array}{rl}& \sum _{i=1}^3\max \{f(f(k_i)),f(g(k_i)),g(f(k_i)),g(g(k_i))\}\\ & =\max \{F_1,F_2,h(F_1),h(F_2)\}+\max \{F_2,F_3,h(F_2),h(F_3)\}+\max \{F_3,F_1,h(F_3),h(F_1)\}\\ & =h(F_2)+\max \{F_3,h(F_2)\}+F_3\\ & \ge h(F_2)+\frac{1}{2}(F_3+h(F_2))+F_3\\ & =\frac{3}{2}{F}_3+\frac{3}{2}h(F_2).\end{array}(\ast \ast )$$ Every element of $S$ appears exactly once as $a_1,a_2$ or $a_3$ for some $Z_j$. Since $f$ is bijective, the same is true for $k_1,k_2$ or $k_3$. Furthermore, since $f$ and $h$ are both bijections, each element of $S_3$ appears exactly once as $F_3$, and as $h(F_2)$, for some $Z_j$. Hence, by taking sums of both sides of $(\ast \ast )$ for $Z_1,\dots ,Z_{1000}$, we have $$X_{\max }(f,g)\ge \frac{3}{2}\sum _{k=2001}^{3000}k+\frac{3}{2}\sum _{k=2001}^{3000}k=\sum _{k=2001}^{3000}3k.$$ Similarly, we have $X_{\min }(f,g)\le {\sum }_{k=1}^{1000}3k$. Therefore, we can conclude that $$X(f,g)\ge \sum _{k=2001}^{3000}3k-\sum _{k=1}^{1000}3k=6000000.$$ This completes the proof that $X=6000000$ satisfies the condition, hence the answer is $6000000$.