[D] Count the Survivors
解説
（１）一旦 $x_n$ の大小関係を無視して考える。各 $x_n$ について $x_n=0$ または $x_n=1$ ならば $f_n=0$ が成り立つ。$x_n$ たちの中で $0$ が $L$ 個、$1$ が $M$ 個あるとして、$0$ でも $1$ でもないものが $K=N-M-L$ 個あるとする。するとこの$K$ 個をあらためて $x_n\ (n=1,2,\ldots,K)$ として、これらに対する $f_n=0$ の条件から
$$
c(1+x_n)-M-\sum_{i=1}^{K}x_i=0 \ \ \ (n=1,2,\ldots ,K)
$$
となる。これは $x_n$ たちに対する線形方程式なので解は一意に定まり、
$$
x_n=x^{\ast}=\frac{c-M}{K-c}\ \ \ (n=1,2,\ldots ,K)
$$
となる。今 $\displaystyle c=\frac{1000}{1.23}$ なので、この $x^{\ast}$ が $0$ や $1$ に等しくなることはない。よって、$N$ 個の $x_n$ の中から $L$ 個を $0$、 $M$ 個を $1$、残りの $K=N-M-L$ 個を $x^{\ast}$ として、これらを小さい順に並べると求める $(x_1,x_2,\ldots,x_{1000})$ の組が一つできる。つまり求める個数は $N=1000$ 個の $x_n$ を3つの区別できるグループに分ける(1つも含まない組があっても良い)方法の数なので、$\displaystyle \frac{(N+2)(N+1)}{2}=501501$ 個となる。
（２）以下（１）で求めた $x_n$ の組を、$0,1,x^{\ast}$ の順番に並べて考えることにする。すなわち
$$
\begin{eqnarray}
x_n&=&0 \ \ \ (n=1,2,\ldots,L), \\
x_n&=&1 \ \ \ (n=L+1,L+2,\ldots,L+M), \\
x_n&=&x^{\ast} \ \ (n=L+M+1,L+M+2,\ldots,L+M+K=N) \\
\end{eqnarray}
$$
であるとする。この組に対して $\displaystyle \sum_{i=1}^{N}x_i =M+\frac{K(c-M)}{K-c}$ である。
$J$ の各成分を計算すると、対角成分は
$$
\frac{\partial f_n}{\partial t_n} =(1-2t_n)\left[c(1+t_n)-\sum_{i=1}^{N}t_i \right] +(c-1)t_n(1-t_n)
$$
で、非対角成分は
$$
\frac{\partial f_n}{\partial t_m} =-t_n(1-t_n)\ \ \ (n\neq m)
$$
となる。これより、まず $J(x_1,x_2,\ldots,x_{1000})$ の左上の $(L+M) \times (L+M)$ 行列部分は、対角成分に $\lambda_0=-M+c$ が $L$ 個、$\lambda_1=M-2c$ が $M$ 個並んだ対角行列 $J_{LM}$ となる。次に右上の $(L+M)\times K$ 成分は全て $0$ である。左下の部分を $A$ 、右下の部分を $J_{K}$ とおくと、$J(x_1,x_2,\ldots,x_{1000})$ は以下のような形になる:
$$
J(x_1,x_2,\ldots,x_{1000})=\begin{pmatrix} J_{LM} & O \\ A & J_{K} \end{pmatrix}
$$
この行列の固有値は $J_{LM}$ の固有値と $J_{K}$ の固有値に等しい(ブロック分けされた行列の行列式の性質より)。$J_{LM}$ の固有値は
$$
\begin{eqnarray}
\lambda_{0} &=&-M+c \\
\lambda_{1} &=& M-2c
\end{eqnarray}
$$
($\lambda_0$ が $L$ 個、$\lambda_1$ が $M$ 個)なので、あとは $J_{K}$ の形を考えよう。
$J_{K}$ の対角成分は$(c-1)x^{\ast}(1-x^{\ast})$、非対角成分は$-x^{\ast}(1-x^{\ast})$なので、
$$
J_{K}=-x^{\ast}(1-x^{\ast})\tilde{J}_{K}=-x^{\ast}(1-x^{\ast})\begin{pmatrix}
1-c & 1 & \dots & 1 \\
1 & 1-c & \dots & 1 \\
\vdots & \vdots & \ddots & \vdots \\
1 & 1 & \dots & 1-c
\end{pmatrix}
$$
となり、この $\tilde{J_{K}}$ の固有値は $K-c$ が $1$ 個、$-c$ が $K-1$ 個である(確かめよ)。なお $K=1$ のときは $K-c=1-c$ が唯一の固有値となる。よって元の $J_{K}$ の固有値は
$$
\begin{eqnarray}
\lambda_{2} &=& (c-K)x^{\ast}(1-x^{\ast}) \\
\lambda_{3} &=& cx^{\ast}(1-x^{\ast})
\end{eqnarray}
$$
($\lambda_{2}$が$1$個、$\lambda_{3}$が$K-1$個) となる。従って、$J(x_1,x_2,\ldots,x_{1000})$ の固有値は
$$
\begin{eqnarray}
\lambda_{0} &=&-M+c \ \ \ (L個)\\
\lambda_{1} &=& M-2c \ \ \ (M個)\\
\lambda_{2} &=& (c-K)x^{\ast}(1-x^{\ast}) \ \ \ (1個)\\
\lambda_{3} &=& cx^{\ast}(1-x^{\ast})\ \ \ (K-1個)
\end{eqnarray}
$$
となる。これらは全て実数なので、これらが全て負になるような 組 $(L,M,K)$ の数が求める個数である。$c=1000/1.23=813.00813..., N/2<c<N$ に注意して、$K=0,1,2\leq K \leq N-1, K=N$ で場合分けして数えることで、答えは $\lceil c \rceil =814$ 個である。
おすすめ問題
この問題を解いた人はこんな問題も解いています
