[D] 自己言及的な数列

解答

$N$ を正の整数とする。$N$ 個の負でない整数からなる列 $a_0,a_1,a_2,\cdots ,a_{N-1}$ が自己言及列であるとは、$k=0,1,2,...,N-1$ に対して、$k$ がこの数列にちょうど $a_k$ 回だけ現れることであると定義する。$N=5,10$ の自己言及列をそれぞれ求めれば良い。

まず、自己言及列について $N$ によらず以下が成り立つことに注意する。

性質 $1$ : すべての $k$ について $0\leq a_k \leq N-1$
$a_k \geq N$ とすると、数列に $k$ が $N$ 個以上含まれることになり、$a_k=N,k=N$ しかあり得ない。しかし $k$ は $0$ 以上 $N-1$ の範囲しか動かないので矛盾。

性質 $2$ : $a_0+a_1+\cdots+a_{N-1}=N$
性質 $1$ と自己言及列の定義より明らか。

性質 $3$ : $a_0 \geq 1$
$a_0=0$ とすると、数列に $0$ が $1$ 個以上含まれていることに矛盾する。

性質 $4$ : $a_{N-1}=0$
$a_{N-1} \geq 1$ とすると、ある $k$ について $a_k = N-1$ となり、性質 $2$ より $a_{N-1}=1,a_k=N-1$ で他の $a_i$ がすべて $0$ の場合か、$k=N-1$ の場合のどちらかである。前者の場合、$a_1\geq1$ なので $N=2$ が必要で、$(a_0,a_1)=(1,0),(1,1)$ のいずれでも自己言及列にならない。後者の場合、数列に $N-1$ が $N-1$ 個含まれるので、 性質 $2$ より $(N-1)^2 \leq N$ である。これより $N=1,2$ でいずれの場合も不適。

（１）$N=5$ とする。性質 $1$ より $1\leq a_0\leq4$ であるから、$a_0=1,2,3,4$ をそれぞれ場合分けして調べる。

・$a_0=1$ のとき
$a_1\geq2$ なので $a_2,a_3,a_4$ のいずれかひとつのみが $0$ だが、性質 $4$ より $a_4=0$ なので $a_2,a_3\geq1$ である。よって性質 $2$ を用いると $(a_0,a_1,a_2,a_3,a_4)=(1,2,1,1,0)$ のみが候補だがこれは条件を満たさない。

・$a_0=2$ のとき
$a_2\geq1$ で、性質 $4$ より $a_4=0$ なので $a_1,a_3$ のいずれか一方のみが $0$ である。まず $a_1=0$ とすると、 $a_2\geq2,a_3\geq2$ となって性質 $2$ に反する。次に $a_3=0$ とすると、性質 $2$ より $(a_1,a_2)=(1,2),(2,1)$ のみが候補で、条件を満たすのは

$$
(a_0,a_1,a_2,a_3,a_4)=(2,1,2,0,0)
$$

だけである。

・$a_0=3$ のとき
$a_3\geq1$ なので $a_1=a_2=a_4=0$ となる。性質 $2$ より $a_3=2$ が必要だがこれは $a_2=0$ に反する。

・$a_0=4$ のとき
$a_1=a_2=a_3=a_4=0$ となるが、これは数列に $4$ が $1$ 個含まれていることに矛盾するので不適。

したがって $N=5$ の自己言及列は $(a_0,a_1,a_2,a_3,a_4)=(2,1,2,0,0)$ だけであるから、$\fbox{ア}=2, \fbox{イ}=1, \fbox{ウ}=2, \fbox{エ}=0, \fbox{オ}=0$ である。

（２） $N=10$ とする。
$a_0=m$ とおく。このとき性質 $4$ より $a_1,a_2,\cdots ,a_8$ のうちちょうど $m-1$ 個が $0$ であり、残りの $9-m$ 個が $0$ でない。$0$ でないものを

$$
a_{n_1},a_{n_2},\cdots,a_{n_{9-m}}
$$

とおく。性質 $1$ よりこれら $9-m$ 個の和は $10-m$ であり、$a_{n_i}$ たちはすべて $1$ 以上であるから、$a_{n_1},a_{n_2},\cdots,a_{n_{9-m}}$ のうちただ $1$ つが $2$ でありその他はすべて $1$ であることがわかる。

次に、$n_1,n_2,\cdots,n_{9-m}$ に $1$ が含まれないと仮定する。このとき $a_1=0$ となって、$a_{n_1},a_{n_2},\cdots,a_{n_{9-m}}$ の中に $1$ が含まれることに矛盾する。同様に $2$ が含まれないと仮定しても矛盾する。したがって、$n_1,n_2,\cdots,n_{9-m}$ は $1,2$ を共に含む。すなわち、$a_1$ と $a_2$ はどちらも $1$ 以上である。$a_{n_1},a_{n_2},\cdots,a_{n_{9-m}}$ のうちただ $1$ つが $2$ 、その他はすべて $1$ なので、$(a_1,a_2)=(1,1),(1,2),(2,1)$ の場合を調べる。

・$(a_1,a_2)=(1,1)$ のとき
これは $1$ が $2$ 個以上含まれることに反するので不適。

・$(a_1,a_2)=(1,2)$ のとき
$a_{n_1},a_{n_2},\cdots,a_{n_{9-m}}$ のうち $a_1$ を含む $8-m$ 個が $1$ である。$a_0=m=1$ のとき数列に $1$ が $8-m+1=9-m$ 個含まれるので $a_1=1=9-m$ より $m=8$ となるが矛盾。よって $m\neq1$ で、 数列に $1$ が $8-m$ 個含まれるので $a_1=1=8-m$ から $m=7$ が得られるが、このとき $a_7\geq1$ であり性質 $2$ に矛盾する。よってこの場合も不適。

・$(a_1,a_2)=(2,1)$ のとき
$a_{n_1},a_{n_2},\cdots,a_{n_{9-m}}$ のうち $a_2$ を含む $8-m$ 個が $1$ である。$a_0=m=1$ のとき数列に $1$ が $8-m+1=9-m$ 個含まれるので $a_1=2=9-m$ より$m=7$ となるが矛盾。よって $m\neq1$ で、 数列に $1$ が $8-m$ 個含まれるので $a_1=2=8-m$ から $m=6$ を得る。このとき性質 $2$ より、$a_6=1,a_3,a_4,a_5,a_7,a_8,a_9=0$ となって数列が決定される。

以上より、$N=10$ の自己言及列は

$$
(a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9)=(6,2,1,0,0,0,1,0,0,0)
$$

だけである。よって $\fbox{カ}=6, \fbox{キ}=2, \fbox{ク}=1, \fbox{ケ}=0, \fbox{コ}=0, \fbox{サ}=0, \fbox{シ}=1, \fbox{ス}=0, \fbox{セ}=0,\fbox{ソ}=0$ である。

コメント

（１）と似たように場合分けすることで、
・$N=4$ の自己言及列は $(a_0,a_1,a_2,a_3)=(1,2,1,0),(2,0,2,0)$ だけである。
・$N=1,2,6$ の自己言及列は存在しない。
ことがそれぞれ示せます。

また、（２）と同様にして、$N=7,8,9$ の自己言及列は
$$
\begin{eqnarray}
(a_0,a_1,a_2,a_3,a_4,a_5,a_6)&=&(3,2,1,1,0,0,0)\\
(a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7)&=&(4,2,1,0,1,0,0,0)\\
(a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8)&=&(5,2,1,0,0,1,0,0,0)\\
\end{eqnarray}
$$

だけであることがわかります。より一般に
・$N\geq7$ の自己言及列は $a_0=N-4,a_1=2,a_2=1,a_{N-4}=1$ （他の $a_i$ はすべて $0$ ）だけである。
ことが示せます。