トップ› 名古屋大学› 1976年› 理系第3問

名古屋大学 1976年理系第3問解説

方針・初手

求める和の値を $S$ とする。まずは $S$ がとり得る最小値と最大値を求める。次に、「条件を満たす $k$ 個の自然数の組において、ある1つの数を1だけ大きくする」という操作を繰り返すことで、和 $S$ が最小値から最大値までのすべての整数値を漏れなくとり得ることを論証する。

解法1

$k$ 個の自然数の和を $S = a_1 + a_2 + \cdots + a_k$ とする。

$S$ が最小となるのは、選ぶ $k$ 個の自然数が最も小さい場合、すなわち $a_1 = 1, a_2 = 2, \cdots, a_k = k$ のときである。このときの和を $S_{\min}$ とすると、

$$ S_{\min} = 1 + 2 + \cdots + k = \frac{1}{2}k(k+1) $$

である。

$S$ が最大となるのは、選ぶ $k$ 個の自然数が最も大きい場合、すなわち $a_1 = n-k+1, a_2 = n-k+2, \cdots, a_k = n$ のときである。このときの和を $S_{\max}$ とすると、等差数列の和の公式より、

$$ S_{\max} = (n-k+1) + (n-k+2) + \cdots + n = \frac{1}{2}k \{ (n-k+1) + n \} = \frac{1}{2}k(2n-k+1) $$

である。

次に、$S_{\min}$ 以上 $S_{\max}$ 以下のすべての整数が、条件を満たす和 $S$ として表せることを示す。

条件を満たす組 $(a_1, a_2, \cdots, a_k)$ があり、その和を $S$ とする。この組が和を最大にする組 $(n-k+1, n-k+2, \cdots, n)$ ではないと仮定する。このとき、隣り合う要素の差が2以上であるか、または最後の要素が $n$ に達していない箇所が少なくとも1つ存在する。すなわち、

$$ a_{i+1} - a_i \geqq 2 \quad (1 \leqq i \leqq k-1) \quad \text{または} \quad n - a_k \geqq 1 $$

を満たす $i \ (1 \leqq i \leqq k)$ が必ず存在する。そのような $i$ の中で最大のものを $j$ とし、$a_j$ を $a_j + 1$ に置き換えた新しい組を考える。 $j < k$ のときは $a_j + 1 < a_{j+1}$ を満たし、$j = k$ のときは $a_k + 1 \leqq n$ を満たす。したがって、新しい組も大小関係の条件 $1 \leqq a_1 < a_2 < \cdots < a_j+1 < \cdots \leqq n$ を満たし、その和は $S+1$ となる。

この操作を、最小値を与える組 $(1, 2, \cdots, k)$ から始めて、和が最大値を与える組になるまで繰り返すことで、和 $S$ は $S_{\min}$ から $S_{\max}$ まで $1$ ずつ増加していく。

ゆえに、$S$ は $S_{\min}$ 以上 $S_{\max}$ 以下のすべての整数値をとる。その個数は、

$$ \begin{aligned} S_{\max} - S_{\min} + 1 &= \frac{1}{2}k(2n-k+1) - \frac{1}{2}k(k+1) + 1 \\ &= \frac{1}{2}k \{ (2n-k+1) - (k+1) \} + 1 \\ &= \frac{1}{2}k(2n-2k) + 1 \\ &= k(n-k) + 1 \end{aligned} $$

となる。

解説

本問は和のとり得る値の個数を求める問題である。最小値と最大値を求めることは容易であるが、その間にあるすべての整数値をとることの証明が重要になる。解答では「1だけ和を増やす操作」を構成的に示したが、これは $n$ 個のマス目に $k$ 個の石を置くモデルにおいて「一番右側にある動かせる石を右に1つ動かす」という操作に対応している。離散的な値をとる変数のとり得る範囲を求める際、このように連続して値が変化することを示す論法は頻出である。