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

更新 2022/02/05

第3問[場合の数]

第3問

$n$ を $2$ 以上の整数とする。

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

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

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

(1)

まずは小さい $n$ で試してみましょう．例えば $n = 3$ として集合 $T$ を $T = \{1, 3, 6\}$ とおくと，集合 $A_T$ は $\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}$ という $6$ 個の元からなる集合となります．よってこの場合 $f(T)=6$ です．また $T' = \{1, 3, 6\}$ とすると，集合 $A_{T'}$ は $\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')=5$ です． $\frac{1 + 5}{2}=\frac{3 + 3}{2}=3$ となっていることに注意しましょう．これらを見ると， $f$ の値を小さくするためには $T'$ の $\frac{1 + 5}{2}=\frac{3 + 3}{2}=3$ のように異なる組の平均が同じ値になるよう集合 $T$ をとれば良いことがわかります．

考察1

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

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

考察2

考察1のような $T$ を作るには，規則的な数列から考えると良さそう．

このようなものとして例えば $T_n=\{1,2,3,\dots,n\}$ のようなものが思いつきます．これは $\frac{1+3}{2}=\frac{2+2}{2}=2$ $\frac{2+4}{2}=\frac{3+3}{2}=3$ $\frac{1+n}{2}=\frac{2+(n-1)}{2}=\frac{3+(n-2)}{2}=\cdots$ のようにたくさんの異なる組が同じ平均を与えるような集合になっています．このとき $\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}$ となりますが，ここに登場する数は結局 $\frac{2}{2},\frac{3}{2},\frac{4}{2},\dots,\frac{2n-1}{2},\frac{2n}{2}$ の $2n-1$ 個なので， $f(T_n)=2n-1$ です．

ではこれより小さくできるでしょうか？結論から言うと，（ $n$ を固定したとき）この $2n-1$ が $f$ の最小値です．考え方のポイントは次です．

考察3

(1) $T_n$ よりも $f$ を小さくするような集合はなかなか見つからない．

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

最小値の候補 $r$ を見つける．
常に $F(x) \geq r$ であることを示す．
$F(x_0) = r$ となる $x_0$ があることを示す．

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

この2点を踏まえ，「常に $f(T) \geq 2n-1$ である」ことを示せないか？と考えてみます． $A_T$ が必ず $2n-1$ 個以上の元を含むことを示したいので， $T_n$ のときにどうやって $2n-1$ 個の平均値を作ったかを参考にしましょう． $A_{T_n}=\Bigl\{\frac{2}{2},\frac{3}{2},\frac{4}{2},\dots,\frac{2n-1}{2},\frac{2n}{2}\Bigr\}$ の数たちは例えば $\frac{1+1}{2} < \frac{1+2}{2}<\frac{2+2}{2}<\cdots<\frac{(n-1)+n}{2}<\frac{n+n}{2}$ のようにすれば得られます．これは他の $T$ のときも真似できます！ $T=\{a_1,a_2,\dots,a_n\}$ とし， $a_1< a_2< \cdots < a_n$ となるように並び替えておくと， $\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}$ となるので， $A_T$ の中に異なる $2n-1$ 個の元があることを証明できました．

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

第3問 (1)

$f$ の最小値は $2n-1$ であることを示す．

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

$T$ の元を小さい順に $a_1,a_2,\dots, a_n$ とおく．このとき $1\leq i \leq n-1$ に対して $b_{i} = \frac{a_i+a_{i+1}}{2}$ と定める．これは $A_T$ の元である．また $a_i = \frac{a_i+a_i}{2}$ だから， $a_i$ も $A_T$ の元である．そして $a_1<a_2<\cdots <a_n$ より， $a_i$ と $b_i$ の間には $a_1<b_1<a_2<b_2<\cdots<a_{n-1}<b_{n-1}<a_n$ という大小関係がある．よって $A_T$ の中にはこれらの異なる $2n-1$ 個の元があるから， $\# A_T \geq 2n-1$ である．

$f(T) = \# A_T = 2n-1$ を実現する $T$ が存在すること．

$T_n=\{1,2, \dots, n\}$ とおく．このとき $A_{T_n}=\Bigl\{\frac{2}{2},\frac{3}{2},\frac{4}{2},\dots,\frac{2n-1}{2},\frac{2n}{2}\Bigr\}$ だから $f(T_n) = \# A_{T_n} = 2n-1$ である．

以上より求める値は $2n-1$ である．

(2)

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

第3問 (2)

$g$ の最小値は $2n-3$ であることを示す．

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

$T$ の元を小さい順に $a_1,a_2,\dots, a_n$ とおく．このとき $1\leq i \leq n-1$ に対して $b_{i} = \frac{a_i+a_{i+1}}{2}$ $1\leq i \leq n-2$ に対して $c_i=\frac{a_i+a_{i+2}}{2}$ と定める．これらは $B_T$ の元である．そして $a_1<a_2<\cdots <a_n$ より， $b_i$ と $c_i$ の間には $b_1<c_1<b_2<c_2<\cdots<b_{n-2}<c_{n-2}<b_{n-1}$ という大小関係がある．よって $B_T$ の中にはこれらの異なる $2n-3$ 個の元があるから， $\# B_T \geq 2n-3$ である．

$g(T) = \# B_T = 2n-3$ を実現する $T$ が存在すること．

$T=\{1,2, \dots, n\}$ とおく．このとき $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) = \# B_T = 2n-3$ である．

以上より求める値は $2n-3$ である．

まとめ

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

考察3

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

最小値の候補 $r$ を見つける．
常に $F(x) \geq r$ であることを示す．
$F(x_0) = r$ となる $x_0$ があることを示す．

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

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