入試数学コンテスト第6回第3問解答解説

更新日時 2022/02/05
目次
  • 第3問[場合の数]

第3問[場合の数]

第3問

nn22 以上の整数とする。

(1) nn 個の異なる実数からなる集合 TT に対し,実数の集合 ATA_TAT={x+y2  |  x,yT} A_T = \left\{ \dfrac{x+y}{2} \; \middle| \; x,y \in T \right\} と定める。つまり ATA_TTT の任意の2元の平均による集合である。TT の関数 f(T)f(T)f(T)=#AT=ATの元の個数f(T)=\# A_T=A_T \text{の元の個数}と定める。f(T)f(T) の最小値を nn を用いて表せ。

(2) nn 個の異なる実数からなる集合 TT に対し,実数の集合 BTB_TBT={x+y2  |  x,yT,xy} B_T = \left\{ \dfrac{x+y}{2} \; \middle| \; x,y \in T , x \neq y \right\} と定める。つまり BTB_TTT の任意の異なる2元の平均による集合である。TT の関数 g(T)g(T)g(T)=#BT=BTの元の個数g(T)=\# B_T=B_T \text{の元の個数}と定める。g(T)g(T) の最小値を nn を用いて表せ。

与えられた関数の最小値を考察する問題です.

(1)

まずは小さい nn で試してみましょう.例えば n=3n = 3 として 集合 TTT={1,3,6}T = \{1, 3, 6\}とおくと,集合 ATA_TAT={1+12,1+32,1+62,3+32,3+62,5+62}={1,2,72,3,92,6} \begin{aligned} A_T &=\Bigl\{\frac{1 + 1}{2}, \frac{1 + 3}{2},\frac{1 + 6}{2},\\ &\qquad \frac{3 + 3}{2}, \frac{3 + 6}{2},\frac{5 + 6}{2}\Bigr\}\\ &=\Bigl\{1, 2, \frac{7}{2}, 3, \frac{9}{2}, 6\Bigr\} \end{aligned} という 66 個の元からなる集合となります.よってこの場合f(T)=6f(T)=6です.またT={1,3,6}T' = \{1, 3, 6\}とすると,集合 ATA_{T'}AT={1+12,1+32,1+52,3+32,3+52,5+52}={1,2,3,4,5} \begin{aligned} A_{T'} &=\Bigl\{\frac{1 + 1}{2}, \frac{1 + 3}{2},\frac{1 + 5}{2},\\ &\qquad \frac{3 + 3}{2}, \frac{3 + 5}{2},\frac{5 + 5}{2}\Bigr\}\\ &=\{1, 2, 3, 4, 5\} \end{aligned} となるのでf(T)=5f(T')=5です.1+52=3+32=3\frac{1 + 5}{2}=\frac{3 + 3}{2}=3となっていることに注意しましょう.これらを見ると,ff の値を小さくするためには TT'1+52=3+32=3\frac{1 + 5}{2}=\frac{3 + 3}{2}=3のように異なる組の平均が同じ値になるよう集合 TT をとれば良いことがわかります.

考察1

f(T)f(T) を小さくするためには,TT の元の異なる組が同じ平均値をとるように集合 TT をとるべきである.

さらに nn 個の数を完全にランダムにとった場合,異なる組が同じ平均値をとる可能性はほとんど 00 であることも直感的にわかります.(偶然そういう組ができたとしても,数値をほんの少し動かすだけで平均はズレてしまいます!)よって nn 個の数はある程度「綺麗な並びで,規則的に」とった方が良さそうです.

考察2

考察1のような TT を作るには,規則的な数列から考えると良さそう.

このようなものとして例えばTn={1,2,3,,n}T_n=\{1,2,3,\dots,n\}のようなものが思いつきます.これは1+32=2+22=2\frac{1+3}{2}=\frac{2+2}{2}=22+42=3+32=3\frac{2+4}{2}=\frac{3+3}{2}=31+n2=2+(n1)2=3+(n2)2=\frac{1+n}{2}=\frac{2+(n-1)}{2}=\frac{3+(n-2)}{2}=\cdotsのようにたくさんの異なる組が同じ平均を与えるような集合になっています.このときATn={1+12,1+22,1+32,,1+n2,2+22,2+32,,2+n2,,(n1)+n2,n+n2} \begin{aligned} A_{T_n} =\Bigl\{&\frac{1 + 1}{2}, \frac{1 + 2}{2},\frac{1+3}{2},\dots,\frac{1 + n}{2},\\ &\qquad \quad\frac{2 + 2}{2}, \frac{2 + 3}{2},\dots,\frac{2 + n}{2},\\ &\qquad \quad \dots, \frac{(n-1)+n}{2},\frac{n+n}{2}\Bigr\} \end{aligned} となりますが,ここに登場する数は結局22,32,42,,2n12,2n2\frac{2}{2},\frac{3}{2},\frac{4}{2},\dots,\frac{2n-1}{2},\frac{2n}{2}2n12n-1 個なので,f(Tn)=2n1f(T_n)=2n-1です.

ではこれより小さくできるでしょうか?結論から言うと,(nn を固定したとき)この 2n12n-1ff の最小値です.考え方のポイントは次です.

考察3

(1) TnT_n よりも ff を小さくするような集合はなかなか見つからない.

(2)(一般に)関数 F(x)F(x) の最小値を求める手法として,

  • 最小値の候補 rr を見つける.
  • 常に F(x)rF(x) \geq r であることを示す.
  • F(x0)=rF(x_0) = r となる x0x_0 があることを示す.

の3ステップに分けるというやり方が有効である.

この2点を踏まえ,「常に f(T)2n1f(T) \geq 2n-1 である」ことを示せないか?と考えてみます.ATA_T が必ず 2n12n-1 個以上の元を含むことを示したいので,TnT_n のときにどうやって 2n12n-1 個の平均値を作ったかを参考にしましょう.ATn={22,32,42,,2n12,2n2}A_{T_n}=\Bigl\{\frac{2}{2},\frac{3}{2},\frac{4}{2},\dots,\frac{2n-1}{2},\frac{2n}{2}\Bigr\} の数たちは例えば 1+12<1+22<2+22<<(n1)+n2<n+n2\frac{1+1}{2} < \frac{1+2}{2}<\frac{2+2}{2}<\cdots<\frac{(n-1)+n}{2}<\frac{n+n}{2}のようにすれば得られます.これは他の TT のときも真似できます!T={a1,a2,,an}T=\{a_1,a_2,\dots,a_n\}とし,a1<a2<<ana_1< a_2< \cdots < a_n となるように並び替えておくと,a1+a12<a1+a22<a2+a22<<an1+an2<an+an2\frac{a_1+a_1}{2} < \frac{a_1+a_2}{2}<\frac{a_2+a_2}{2}<\cdots<\frac{a_{n-1}+a_n}{2}<\frac{a_n+a_n}{2}となるので,ATA_T の中に異なる 2n12n-1 個の元があることを証明できました.

以上をまとめて答案にします.

第3問 (1)

ff の最小値は 2n12n-1 であることを示す.

  • 任意の TT に対して f(T)=#AT2n1f(T) = \# A_T \geq 2n-1 であること.

TT の元を小さい順にa1,a2,,ana_1,a_2,\dots, a_n とおく.このとき 1in11\leq i \leq n-1 に対してbi=ai+ai+12b_{i} = \frac{a_i+a_{i+1}}{2}と定める.これは ATA_T の元である.またai=ai+ai2a_i = \frac{a_i+a_i}{2}だから,aia_iATA_T の元である.そしてa1<a2<<ana_1<a_2<\cdots <a_nより,aia_ibib_i の間には a1<b1<a2<b2<<an1<bn1<ana_1<b_1<a_2<b_2<\cdots<a_{n-1}<b_{n-1}<a_nという大小関係がある.よって ATA_T の中にはこれらの異なる 2n12n-1 個の元があるから,#AT2n1\# A_T \geq 2n-1 である.

  • f(T)=#AT=2n1f(T) = \# A_T = 2n-1 を実現する TT が存在すること.

Tn={1,2,,n}T_n=\{1,2, \dots, n\}とおく.このときATn={22,32,42,,2n12,2n2}A_{T_n}=\Bigl\{\frac{2}{2},\frac{3}{2},\frac{4}{2},\dots,\frac{2n-1}{2},\frac{2n}{2}\Bigr\}だから f(Tn)=#ATn=2n1f(T_n) = \# A_{T_n} = 2n-1 である.

以上より求める値は2n12n-1である.

(2)

(1) との違いは「平均を計算するときに同じ数を選べない」という点です.しかし,実は (1) とほとんど同じように考えることができます.

第3問 (2)

gg の最小値は 2n32n-3 であることを示す.

  • 任意の TT に対して g(T)=#BT2n3g(T) = \# B_T \geq 2n-3 であること.

TT の元を小さい順にa1,a2,,ana_1,a_2,\dots, a_nとおく.このとき 1in11\leq i \leq n-1 に対してbi=ai+ai+12b_{i} = \frac{a_i+a_{i+1}}{2}1in21\leq i \leq n-2 に対してci=ai+ai+22c_i=\frac{a_i+a_{i+2}}{2}と定める.これらは BTB_T の元である.そしてa1<a2<<ana_1<a_2<\cdots <a_nより,bib_icic_i の間には b1<c1<b2<c2<<bn2<cn2<bn1b_1<c_1<b_2<c_2<\cdots<b_{n-2}<c_{n-2}<b_{n-1}という大小関係がある.よって BTB_T の中にはこれらの異なる 2n32n-3 個の元があるから,#BT2n3\# B_T \geq 2n-3 である.

  • g(T)=#BT=2n3g(T) = \# B_T = 2n-3 を実現する TT が存在すること.

    T={1,2,,n}T=\{1,2, \dots, n\}とおく.このときBTn={32,42,52,,2n22,2n12}B_{T_n}=\Bigl\{\frac{3}{2},\frac{4}{2},\frac{5}{2},\dots,\frac{2n-2}{2},\frac{2n-1}{2}\Bigr\}だから g(T)=#BT=2n3g(T) = \# B_T = 2n-3 である.

以上より求める値は2n32n-3である.

まとめ

この問題のポイントは考察3で述べた関数の最小値を計算する手法です.

考察3

関数 F(x)F(x) の最小値を求める手法として,

  • 最小値の候補 rr を見つける.
  • 常に F(x)rF(x) \geq r であることを示す.
  • F(x0)=rF(x_0) = r となる x0x_0 があることを示す.

の3ステップに分けるというやり方が有効である.

大学入試で登場することは少ないですが,数学オリンピックなどでは頻出のテクニックです.もちろん最大値でも同様のことができます.