2017　東京工業大学　第４類AO総合問題MathJax

　$x_1$の値が選ばれたとき，$a_0=2$に対して，$a_1$は$a_1=a_0+x_1$で定まる．これをステップ$1$と呼ぶ．つぎに$x_2$の値が選ばれたとき，ステップ$1$で定まった$a_1$に対して，$a_2$は$a_2=a_1+x_2$で定まる．これをステップ$2$と呼ぶ．このルールを繰り返し，任意のステップ$k\text{（}k=1\text{，}2\text{，}\cdots \text{，}n\text{）}$に対して，$x_k$の値が選ばれたとき，$a_k$は漸化式$a_k=a_{k-1}+x_k$に従って定まるものとする．

　このとき，つぎの関数$f(x_1,x_2,\cdots ,x_n)$を最小にする数列$x_k\text{（}k=1\text{，}2\text{，}\cdots \text{，}n\text{）}$を求めることを考える．

$f(x_1,x_2,\cdots ,x_n)={\displaystyle \sum _{k=1}^n}({a_k}^2+{x_k}^2)$

問１　ステップ$n$での$a_n$を，$x_k\text{（}k=1\text{，}2\text{，}\cdots \text{，}n\text{）}$を用いて表せ．

問２　$a_n$が取り得る最小値と最大値を，$n$を用いて表せ．

問３　$n=2$とするとき，つぎの関数$f(x_1,x_2)$を最小にする$x_1\text{，}{x}_2$の組み合わせをすべて求めよ．

$f(x_1,x_2)={\displaystyle \sum _{k=1}^2}({a_k}^2+{x_k}^2)$

　ステップ$n$までの数列$x_k\text{（}k=1\text{，}2\text{，}\cdots \text{，}n\text{）}$は，全部で$3^n$通りあるため，$n$が大きくなると，この関数$f$を最小にする数列$x_k\text{（}k=1\text{，}2\text{，}\cdots \text{，}n\text{）}$を見つける際の計算の量は膨大になる．そこで，以下では，効率よく解く方法を考える．

　ステップ$i-1$で$a_{i-1}$が定まったとし，ステップ$i$からステップ$n$までの数列$x_k\text{，}{a}_k\text{（}k=i\text{，}i+1\text{，}\cdots \text{，}n\text{）}$を考える．このとき，つぎの関数$g_i(a_{i-1},x_i,x_{i+1},\cdots ,x_n)$を定義する．

$g_i(a_{i-1},x_i,x_{i+1},\cdots ,x_n)={\displaystyle \sum _{k=i}^n}({a_k}^2+{x_k}^2)$

この関数$g_i$を最小にする数列$x_k\text{（}k=i\text{，}i+1\text{，}\cdots \text{，}n\text{）}$を数列${x_k}^{*}\text{（}k=i\text{，}i+1\text{，}\cdots \text{，}n\text{）}$とし，関数$g_i$の最小値を${g_i}^{*}(a_{i-1})$とする．すなわち，

${g_i}^{*}(a_{i-1})=g_i(a_{i-1},{x_i}^{*},{x_{i+1}}^{*},\cdots ,{x_n}^{*})=\underset{x_k(k=i,i+1,\cdots ,n)}{\min }{g}_i(a_{i-1},x_i,x_{i+1},\cdots ,a_n)$

とする．上式の右辺の$\min$は，関数$g_i(a_{i-1},x_i,x_{i+1},\cdots ,x_n)$を数列$x_k\text{（}k=i\text{，}i+1\text{，}\cdots \text{，}n\text{）}$に関して最小にした際の関数$g_i$の最小値を意味している．このとき，以下の問いに答えよ．

問４　$n=2$とするとき，つぎの関係式が成り立つ．

${g_1}^{*}(a_0)=\underset{x_1}{\min }\{{a_1}^2+{x_1}^2+{g_2}^{*}(a_1)\}$

この関係式を証明せよ．

問５　問４の関係式を任意の$n$の場合に一般化すると，${g_i}^{*}(a_{i-1})$と${g_{i+1}}^{*}(a_i)$に対して，つぎの関係式が成り立つ．

${g_i}^{*}(a_{i-1})=\underset{x_i}{\min }\{{a_i}^2+{x_i}^2+{g_{i+1}}^{*}(a_i)\}\text{（}i=1\text{，}2\text{，}\cdots \text{，}n-1\text{）}$

この関係式の意味を簡単に説明せよ．

問６　$n=3$とするとき，問５の関係式を用いて，関数$f(x_1,x_2,x_3)$を最小にする$x_1\text{，}{x}_2\text{，}{x}_3$を求めたい．このとき，関数$f(x_1,x_2,x_3)$が関数$g_1(a_0,x_1,x_2,x_3)$（ただし，$a_0=2$）と書けることに注意して，つぎの手順で求めよ．

6-1　まず，$a_2$が取り得る値$4\text{，}3\text{，}2\text{，}1\text{，}0$のおのおのに対して，${g_3}^{*}(a_1)$を計算し，表1-1を完成せよ．同様に，$a_1$が取り得る値$3\text{，}2\text{，}1$に対して，問５の関係式を用いて${g_2}^{*}(a_1)$を計算し，表1-2を完成せよ．ここで，表1-1の${x_3}^{*}$と${a_3}^{*}$は，それぞれ，$a_2$の値が与えられたもとでの関数$g_3(a_2,x_3)$を最小にする$x_3$の値，および，それを用いた際の$a_3$の値を表す．表1-2で使われている記号も同様とする．

• 表1-1

  $a_2$	${x_3}^{*}$	${a_3}^{*}$	${g_3}^{*}(a_2)$
  $4$
  $3$
  $2$
  $1$
  $0$

• 表1-2

  $a_1$	${x_2}^{*}$	${a_2}^{*}$	${g_2}^{*}(a_1)$
  $3$
  $2$
  $1$

6-2　作成した表1-1，表1-2を用いて，関数$g_1(a_1,x_1,x_2,x_3)$を最小にする$x_1\text{，}{x}_2\text{，}{x}_3$をすべて求めよ．その際，表1-1，表1-2をどのように用いたかを説明せよ．

問７　問６において$g_1(a_0,x_1,x_2,x_3)$の最小値を$x_1\text{，}{x}_2\text{，}{x}_3$に対して総当たりで求めるには，$27$通りの組み合わせを調べればよい．一方，問５の関係式を用いると，問６の表1-1の${g_3}^{*}(a_2)$（ただし，$a_2=4\text{，}3\text{，}2\text{，}1\text{，}0$）をすべて求めるのに$15$通りの組み合わせを，表1-2の${g_2}^{*}(a_1)$（ただし，$a_1=3\text{，}2\text{，}1$）をすべて求めるのに$9$通りの組み合わせを，そして，$g_1(a_0,x_1,x_2,x_3)$を求めるのに，$x_1$に対して$3$通りの組み合わせを，すなわち，全部で$27$通りの組み合わせを調べればよい．このように$n=3$の場合は，どちらの場合でも同じ組み合わせ数を調べることになるが，$n\geqq 4$の場合には，問５の関係式を用いると，総当たりで求める場合に比べて，調べる組み合わせ数が$n$が大きくなるにつれて格段に減る．この調べる組み合わせ数を，$n$を用いて表せ．