The 35th Japanese Mathematical Olympiad

Lemma. Let $x,y,z$ be integers with $1\le x,y,z\le N$. Then at least one of $(x,y,z)$, $(y,z,x)$, or $(z,x,y)$ belongs to $S$.

proof. Consider a sequence $a_1=x,a_2=y,a_3=z,a_4=x,a_5=y,a_6=z,\dots$. Then, for every positive integer $i$, $(a_i,a_{i+1},a_{i+2})$ is one of $(x,y,z)$, $(y,z,x)$, or $(z,x,y)$. Therefore, by the assumption of the problem, at least one of these triples must belong to $S$. ■

Consider the set $$\begin{gathered} X=\{(x_1,y_1,z_1),(x_2,y_2,z_2),\dots ,(x_n,y_n,z_n),(y_1,z_1,x_1),(y_2,z_2,x_2),\dots ,(y_n,z_n,x_n), \\ (z_1,x_1,y_1),(z_2,x_2,y_2),\dots ,(z_n,x_n,y_n)\}. \end{gathered}$$ Let $p,q,r$ be integers with $1\le p,q,r\le N$. Applying Lemma to $(x,y,z)=(p,q,r)$, it follows that at least one of $(p,q,r)$, $(q,r,p)$, or $(r,p,q)$ belongs to $S$, say it is $(x_j,y_j,z_j)$ for some $1\le j\le n$. Then, $(p,q,r)$ is equal to one of $(x_j,y_j,z_j)$, $(z_j,x_j,y_j)$, or $(y_j,z_j,x_j)$, and therefore, $(p,q,r)$ belongs to $X$. Thus, it has been shown that $X$ is the set of all $N^3$ triples $(p,q,r)$ with $1\le p,q,r\le N$. By applying Lemma to $(x,y,z)=(1,1,1),(2,2,2),\dots ,(N,N,N)$, we find that these triples $(1,1,1),(2,2,2),\dots ,(N,N,N)$ all belong to $S$. If $(x_j,y_j,z_j)$ is equal to one of them, we have $(x_j,y_j,z_j)=(y_j,z_j,x_j)=(z_j,x_j,y_j)$, hence the number of elements of $X$ is less than or equal to $3n-2N$. Therefore we have $3n-2N\ge N^3$, thus $n\ge \frac{N^3+2N}{3}$.

Next, we construct a set $S$ satisfying $n=\frac{N^3+2N}{3}$. Define $S$ to be the set of triples $(x,y,z)$ with $1\le x,y,z\le N$ such that either * $x>y$ and $x\ge z$, or

$$\bullet x=y=z.$$ If we fix an integer $x$ with $1\le x\le N$, the number of pairs $(y,z)$ such that $(x,y,z)$ belongs to $S$ is equal to $x(x-1)+1$. Therefore, the number of elements in $S$, denoted by $n$, is $$n=\sum _{x=1}^N(x(x-1)+1)=\frac{N^3+2N}{3}.$$ Assume, for the sake of contradiction, that there exists a sequence $a_1,a_2,\dots$ of integers $1,2,\dots ,N$ such that none of the triples $(a_1,a_2,a_3),(a_2,a_3,a_4),\dots$ belongs to $S$. Let $a_k$ be one of the largest terms among $a_1,a_2,\dots$. Then we have $a_k\ge a_{k+1}$ and $a_k\ge a_{k+2}$. Since $(a_k,a_{k+1},a_{k+2})$ does not belong to $S$, we have $a_{k+1}=a_k$. Therefore, $a_{k+1}$ is also one of the largest terms in the sequence. Applying the same argument to $(a_{k+1},a_{k+2},a_{k+3})$, we obtain $a_{k+2}=a_{k+1}$. Hence, $a_k=a_{k+1}=a_{k+2}$, so $(a_k,a_{k+1},a_{k+2})$ belongs to $S$, a contradiction. Therefore, this set $S$ satisfies the required condition.

This shows that the minimum value of $n$ is $\frac{N^3+2N}{3}=333400$.