[math]2001年京都大学文系後期数学問題2

Table of Contents

問題

$1$または$-1$からなる数列$a_1, a_2, \cdots, a_n$において、そのうち$m$個が$1$で、$n-m$個は$-1$とする。$k = 1, 2, \cdots, n$に対し、$b_n = \frac{1}{2}\left(ka_n+\sum_{j=1}^{k}{a_j}\right)$とおく。集合$\{b_k(1\leq k\leq n)\}$を求めよ。

方針

とても難しい問題で何よりも実験が大切である。実験が大切なのは、そもそも問題の構造がどうなっているのかが分かりにくいからである。試験場でこういう問題を最初から美しく解こうとすると間違いなく失敗する。いくつか具体的な例を持ち出し様子に親しむことでいい方法が思い浮かぶ可能性もあるし、そうでなくとも答えの確認になるかも知れない。さらに、計算を記しておくことで、部分点を貰える可能性もある。
そんな訳で実験してみる。適当に$n,m$を設定して試してみると、$b_k$はどれも異なるのではないのかと予想される。ただし、直接この予想を示すのは難しく、試行錯誤していくと$a_k$までの$1$の個数が重要だと分かってくる。これを自分で設定できれば後は解答のように$b_k$は$x_k$か$−y_k$のどちらかになることが分かる。

解答

$a_n$の第$k$項までに現れる$1$の数を$x_n$とし、$-1$の数を$y_n$とすると、

$x_n + y_n = k$
$x_n = m$
$y_n = n-m$

である。すると、$$b_k = \frac{1}{2}\left(ka_k + \sum_{j=1}^{k}{a_k}\right)$$ $$ = \frac{1}{2}(ka_k+x_k-y_k)$$ $$ = \frac{1}{2}(ka_k + 2x_k-k)$$ $$ = x_k + \frac{k}{2}(a_k-1)$$となる。これは$a_k = 1$の時は$x_k$となり、$a_k=-1$の時は$x_k-k = -y_k$となる。すると、$$0\leq x_1\leq x_2\leq \cdots x_n = m$$ $$0\leq y_1\leq y_2\leq \cdots \leq y_n = n-m$$であるから、$m=0$のときには$x_k = 0 (1\leq k\leq n)$となり、$y_k = k$が分かる。また、$n-m = 0$のときには$y_k = 0 (1\leq k\leq n)$となり、$x_k = k$が分かる。つまり、$m = 0$の時は$b_k = \{-1, -2, \cdots, -n\}$となり、$m = n$の時は$b_k = \{1, 2, \cdots, n\}$となる。

$0 < m < n$の時を考える。$a_k = 1$の時、$b_k$は$a_1, a_2, \cdots, a_k$の中の$1$の個数を表すから、$b_k$は$1$から$m$までのすべての整数値を取る。$a_k = -1$の時、$b_k$は$a_1, a_2, \cdots, a_k$の中にある$-1$の個数$\times -1$を表すから、$b_k$は$-1$から$-(n-m)$までのすべての整数値を取る。$-(n-m)$から$m$までの整数は、$0$を除くと$n$個であるから、この時$b_k = \{-(n-m), -(n-m)+1, \cdots ,-1, 1, 2, \cdots, m-1, m\}$となる。答えは、