[F] 虹色ネックレス

解答

617284

解説

$M$ を正の整数とする。問題文の $1234567$ を $4M+3$ で置き換えたときに、最大値が $2M+2$ であることを示す。

補題1:

${a_n}$ の中に $-1$ が連続して現れることはないとする。このとき ${a_n}$ は定数列で、$a_n\equiv 0$ または $a_n\equiv 2$ である。

補題1の証明:

このとき、隣接する $2$ 項の積が $1$ になることはない。なぜなら、ある $i$ について $a_i\neq 0, a_{i+1}\neq 0, a_{i} a_{i+1}=1$ であったとすると $3$ 項間関係式と併せて $(a_{i},a_{i+1})=(-1,-1)$ が必要であり、これは数列のどこにも $-1$ が連続して現れないという仮定に反するからである。よって $3$ 項間関係式は

$$
a_{n+1}=\frac{a_{n}^2+a_{n-1}}{a_{n}a_{n-1}-1}\ \ \ (n=1,2,\ldots,4M+3)
$$

と変形できる（分母が $0$ になることは決してない）。$a_1=x, a_2=y$ とおいて計算すると $a_3=\displaystyle\frac{x+y^2}{xy-1}, a_4=\displaystyle\frac{x^2+y}{xy-1}, a_5=x, a_6=y$ となり、$a_n$ は $4$ 項ごとに循環することがわかる。一方 ${a_n}$ は周期 $4M+3$ の数列であり、$4M+3$ と $4$ は互いに素なので、${a_n}$ は定数列である。 $a_n\equiv c$ とおくと、$3$ 項間関係式より $c^3=2c+c^2$ であるから、$c=0,-1,2$ である。$c=-1$ は $-1$ が連続して現れないという仮定に反するので、 $c=0,2$ のみが条件を満たす。（証明終）

補題1より、$-1$ が連続して現れないとき、${a_n}$ には $1$ 種類の実数しか現れない。また、定数列 $a_n\equiv-1$ も条件を満たすが、この場合も $1$ 種類の実数しか現れない。
この後示すように、任意の $M$ に対して ${a_n}$ に $2$ 種類以上の実数が現れるようにできるので、${a_n}$ に現れる異なる実数の最大値を求める場合、定数列となる場合は考えなくて良い。よって、以下では $-1$ が連続して現れる箇所があり、かつ $-1$ 以外の実数も現れる場合を考える。${a_n}$ は周期列なので、$a_{4M+3}\neq -1, a_1=-1, a_2=-1$ として一般性を失わない。

以下のようにブロックを定義する。

ブロックの定義:

整数 $n\geq 2$ に対して、長さ $n+1$ のブロック $T_n$ を $T_n=[-1,-1,\ldots, -1, 2]$ と定める（$-1$ は $n$ 個並んでいる）。また、整数 $n\geq 2$ および 実数 $z\neq 2, -1$ に対して、長さ $n+2$ のブロック $S_n(z)$ を $[-1,\ldots,-1,z,1-z]$ と定める（$-1$ は $n$ 個並んでいる）。

補題2:

${a_n}$ は定数列でないとする。このとき、条件を満たす ${a_n}$ は、それぞれ任意の長さを持つブロック $T_n$ と $S_n(z)$ を長さの合計がちょうど $4M+3$ になるように任意の順番で並べたもので全てである。

補題2の証明:

$a_1=-1, a_2=-1$ なので、$3$ 項間関係式から $a_3$ は任意の実数値を取りうる。$a_3=-1$ のときは同様に $a_4$ が任意の実数値を取りうる。このように、$a_{i}\ (i=3,4,\ldots)$ が $-1$ であるかぎり、$a_{i+1}$ は任意の実数値 $z$ を取りうる。もし、ある $m=3,4,\dots, 4M+3$ に対して、$a_1,a_2,\ldots, a_{m-1}=-1,a_{m}=2$ となったとする。このとき $a_1,a_2,\ldots, a_{m}$ はブロック $T_{m}$ に等しく、$3$ 項間関係式から $a_{m+1}=-1,a_{m+2}=-1$ が得られ、再び $-1$ が連続する。また、ある $m=3,4,\dots ,4M+2$ に対して、$a_1,a_2,\ldots, a_{m-1}=-1,a_{m}=z$ となったとする($z\neq -1, 2$)。このとき $3$ 項間関係式から $a_{m+1}=1-z,a_{m+2}=-1, a_{m+3}=-1$ が得られ、再び $-1$ が連続する。このとき $a_1,a_2,\ldots, a_{m}, a_{m+1}$ はブロック $S_{m+1}(z)$ に等しい。

いずれの場合も、再び連続して現れた $-1,-1$ の部分について同じ議論を繰り返すことで、${a_n}$ は任意の長さのブロック $T_n$ と $S_n(z)$ を任意の順番で並べた場合に限って条件を満たしながら構成できる。また、$a_{4M+3}\neq -1$ より、最後の $\ldots a_{4M+1}, a_{4M+2}, a_{4M+3}$ は $\ldots -1,-1,2$ か $\ldots -1,z,1-z$ のいずれかでなければならない。よって ${a_n}$ は $T_n$ と $S_n(z)$ を長さの合計がちょうど $4M+3$ になるよう並べて構成しなければならない。逆に、このように構成した ${a_n}$ は、その構成の仕方からすべての $n=1,2,\ldots,4M+3$ について $3$ 項間関係式を満たす。(証明終)

以下、2つの実数 $x,y$ が本質的に異なる とは $x\neq y$ かつ $x+y\neq 1$ であることとする。$x,y$ が本質的に異なるとき、ブロック $S_n(x)$ と $S_n(y)$ に現れる $-1$ でも $2$ でもない実数が等しくなることはない。 また、ブロック $S_n(z)$ に含まれる $-1$ でも $2$ でもない実数の個数は、$z=\displaystyle \frac{1}{2}$ のとき $1$ 個、そうでないとき $2$ 個である。

まず、${a_n}$ に現れる異なる実数の種類は $2M+2$ 以下であることを示す。整数 $K\geq 2M+3$ に対して、$K$ 種類の実数が現れるような題意を満たす ${a_n}$ があったとして矛盾を導こう。このとき ${a_n}$ は定数列ではないので、補題2より ${a_n}$ はブロック $T_n$ と $S_n(z)$ を並べたものとなる。

・${a_n}$ が $2$ を含まず、$K$ が奇数のとき

このとき ${a_n}$ はブロック $T_n$ を含まず、$-1$ でも $2$ でもない実数が合計 $K-1$ (偶数)種類現れる。よって $L=\displaystyle \frac{K-1}{2}$ とおくと、$-1$ でも $2$ でも $\displaystyle \frac{1}{2}$ でもない、本質的に相異なる実数 $z_1,z_2,\ldots z_L$ があって、ブロック $S_n(z_1),S_n(z_2),\ldots,S_n(z_L)$ をある順番で並べたものが ${a_n}$ である。その長さの合計は少なくとも $4L =2K-2 \geq 4M+4$ であるが、これは本来の ${a_n}$ の長さ $4M+3$ を超えるので矛盾。

・${a_n}$ が $2$ を含まず、$K$ が偶数のとき

このとき ${a_n}$ はブロック $T_n$ を含まず、$-1$ でも $2$ でもない実数が合計 $K-1$ (奇数)種類現れる。よって $L=\displaystyle \frac{K-2}{2}$ とおくと、$-1$ でも $2$ でも $\displaystyle \frac{1}{2}$ でもない本質的に相異なる実数 $z_1,z_2,\ldots z_L$ があって、ブロック $S_n\left(\displaystyle \frac{1}{2}\right),S_n(z_1),S_n(z_2),\ldots,S_n(z_L)$ をある順番で並べたものが ${a_n}$ である。その長さの合計は少なくとも $4(L+1) =2K \geq 4M+6$ であるが、これは本来の ${a_n}$ の長さ $4M+3$ を超えるので矛盾。

・${a_n}$ が $2$ を含み、$K$ が偶数のとき

このとき ${a_n}$ はブロック $T_n$ を少なくとも $1$ 個含み、さらに $-1$ でも $2$ でもない異なる実数が $K-2$ (偶数)種類現れる。よって $L=\displaystyle \frac{K-2}{2}$ とおくと、$-1$ でも $2$ でも $\displaystyle \frac{1}{2}$ でもない本質的に相異なる実数 $z_1,z_2,\ldots z_L$ があって、ブロック $S_n(z_1),S_n(z_2),\ldots,S_n(z_L)$ と $1$ 個以上のブロック $T_n$ をある順番で並べたものが ${a_n}$ である。その長さの合計は少なくとも $4L + 3 =2K - 1 \geq 4M+5$ であるが、これは本来の ${a_n}$ の長さ $4M+3$ を超えるので矛盾。

・${a_n}$ が $2$ を含み、$K$ が奇数のとき

このとき ${a_n}$ はブロック $T_n$ を少なくとも $1$ 個含み、さらに $-1$ でも $2$ でもない実数が合計 $K-2$ (奇数)種類現れる。よって $L=\displaystyle \frac{K-3}{2}$ とおくと、$-1$ でも $2$ でも $\displaystyle \frac{1}{2}$ でもない本質的に相異なる実数 $z_1,z_2,\ldots z_L$ があって、ブロック $S_n\left(\displaystyle \frac{1}{2}\right),S_n(z_1),S_n(z_2),\ldots,S_n(z_L)$ と $1$ 個以上のブロック $T_n$ をある順番で並べたものが ${a_n}$ である。その長さの合計は少なくとも $4(L+1) + 3 = 2K+1 \geq 4M+7$ であるが、これは本来の ${a_n}$ の長さ $4M+3$ を超えるので矛盾。

よっていずれの場合も矛盾したので、${a_n}$ に現れる異なる実数の個数は $2M+2$ 以下である。

次に $2M+2$ 種類の異なる実数が現れるような ${a_n}$ を構成する。$z_m=2+m\ (m=1,2,\ldots,M)$ として $S_2(z_1),S_2(z_2),\ldots ,S_2(z_M), T_2$ の順に繋いだものを ${a_n}$ とする。すなわち

$$
\{a_n\}=-1,-1,3,-2,-1,-1,4,-3,\ldots,-1,-1,M+1,-M, -1,-1,M+2,-M-1,-1,-1,2
$$

となる。これは全ての連続する $3$ 項で関係式を満たす長さ $4M+3$ の数列になっているので確かに条件を満たす。このとき、${a_n}$ に含まれる実数は $-1,2$ ($2$ 種類)、$3,4,\ldots M+1,M+2$ ($M$ 種類)、$-2,-3,\ldots -M, -M-1$ ($M$ 種類)であり、これらは全て相異なるので、あわせて $2M+2$ 種類の異なる実数を含んでいる。

従って、求める最大値は $2M+2$ である。もとの問題では、特に $M=308641$ であったので、最大値は $617284$ である。