トップ› 東京大学› 2011年› 文系第3問

東京大学 2011年文系第3問解説

方針・初手

与えられた条件 $-q \leqq b \leqq 0 \leqq a \leqq p$ と $b \leqq c \leqq a$ を満たす整数の組 $(a, b, c)$ を数え上げる問題である。関数 $w([a, b; c])$ は $c$ に依存せず $a, b$ だけで決まるため、まず $w$ の値から $a + b$ の値を決定し、条件を満たす $a, b$ の組を見つける。その後、各 $(a, b)$ に対して条件 $b \leqq c \leqq a$ を満たす $c$ が何通りあるかを求め、和をとるという方針で進める。

解法1

(1)

$w([a, b; c]) = -q$ となる条件を考える。

$$ p - q - (a + b) = -q \iff a + b = p $$

与えられた条件より $0 \leqq a \leqq p$ かつ $-q \leqq b \leqq 0$ であるから、これらを満たしつつ和が $p$ となる整数の組は、

$$ a = p, \quad b = 0 $$

のみである。このとき、整数 $c$ に対する条件 $b \leqq c \leqq a$ は、

$$ 0 \leqq c \leqq p $$

となる。これを満たす整数 $c$ は $p - 0 + 1 = p + 1$ 個存在する。したがって、$w([a, b; c]) = -q$ となる $(p, q)$ パターンの個数は $p + 1$ 個である。

次に、$w([a, b; c]) = p$ となる条件を考える。

$$ p - q - (a + b) = p \iff a + b = -q $$

先ほどと同様に $0 \leqq a \leqq p$ かつ $-q \leqq b \leqq 0$ であるから、和が $-q$ となる整数の組は、

$$ a = 0, \quad b = -q $$

のみである。このとき、整数 $c$ に対する条件 $b \leqq c \leqq a$ は、

$$ -q \leqq c \leqq 0 $$

となる。これを満たす整数 $c$ は $0 - (-q) + 1 = q + 1$ 個存在する。したがって、$w([a, b; c]) = p$ となる $(p, q)$ パターンの個数は $q + 1$ 個である。

(2)

$p = q$ の場合を考える。条件は $-p \leqq b \leqq 0 \leqq a \leqq p$ および $b \leqq c \leqq a$ となる。また、関数の値は、

$$ w([a, b; c]) = p - p - (a + b) = -(a + b) $$

である。これが $-p + s$ に等しいので、

$$ -(a + b) = -p + s \iff a + b = p - s $$

となる。ここで、$a, b$ の満たす条件より $0 \leqq a \leqq p$ および $-p \leqq b \leqq 0$ であるから、和 $a + b$ のとりうる範囲は、

$$ -p \leqq a + b \leqq p $$

である。したがって、

$$ -p \leqq p - s \leqq p \iff 0 \leqq s \leqq 2p $$

となる。問題の条件より $s$ は $p$ 以下の整数（$s \leqq p$）であるため、$s$ の値によって以下のように場合分けを行う。

(i)

$s < 0$ のとき

$a + b = p - s > p$ となり、$-p \leqq a + b \leqq p$ を満たす整数の組 $(a, b)$ は存在しない。したがって、パターンの個数は $0$ 個である。

(ii)

$0 \leqq s \leqq p$ のとき

$a = p - s - b$ と表せる。条件 $0 \leqq a \leqq p$ より、

$$ 0 \leqq p - s - b \leqq p \iff -p + s \leqq -b \leqq s \iff -s \leqq b \leqq p - s $$

である。さらに $-p \leqq b \leqq 0$ を満たす必要がある。 $0 \leqq s \leqq p$ であるため、$-s \leqq 0$ かつ $p - s \geqq 0$ が成り立つ。よって、これらを同時に満たす $b$ の範囲は、

$$ -s \leqq b \leqq 0 $$

となる。この範囲の各整数 $b$ に対して、$a = p - s - b$ がただ一つ定まり、条件 $-p \leqq b \leqq 0 \leqq a \leqq p$ を満たす。また、各組 $(a, b)$ に対して、条件 $b \leqq c \leqq a$ を満たす整数 $c$ の個数は、

$$ a - b + 1 = (p - s - b) - b + 1 = p - s - 2b + 1 $$

である。したがって、求めるパターンの総数は、これを $b = -s$ から $b = 0$ まで足し合わせたものになる。

$$ \sum_{b = -s}^{0} (p - s - 2b + 1) $$

ここで $k = -b$ とおくと、$k$ は $0$ から $s$ まで動き、

$$ \sum_{k=0}^{s} (p - s + 2k + 1) $$

となる。これは項数 $s + 1$、初項（$k = 0$ のとき）が $p - s + 1$、末項（$k = s$ のとき）が $p + s + 1$ の等差数列の和である。したがって、その和は、

$$ \frac{1}{2} (s + 1) \{ (p - s + 1) + (p + s + 1) \} = \frac{1}{2} (s + 1) (2p + 2) = (p + 1)(s + 1) $$

となる。

解説

複数の変数が絡む条件付きの数え上げ問題では、「独立に動かしやすい変数」や「他の変数を決定づける変数」から固定していくことが鉄則である。本問では $w$ の値が $a + b$ の値だけで決まることに着目し、先に $a, b$ の関係式を導いてから $c$ の個数を数える方針が有効である。また、(2) では $s$ が $p$ 以下の整数としか指定されていないため、$s < 0$ の場合が除外されていないことに注意が必要である。$a, b$ の変域から $a + b$ のとりうる最大値と最小値を調べることで、$s$ の範囲を絞り込むと論理の飛躍なく解答できる。(1) の結果は (2) において $s = 0$ としたときの結果と一致するため、検算として利用できる。