トップ› 大阪大学› 1982年› 理系第2問

大阪大学 1982年理系第2問解説

方針・初手

不等式で表された領域内の格子点（座標がともに整数である点）の個数を求める問題である。格子点の数え上げの基本は、「どちらかの変数を固定して、もう一方の変数の個数を数え、最後に足し合わせる」ことである。

本問では、$x$ を固定して各 $x$ に対する $y$ の個数を数える方針（解法2）と、$y$ を固定して各 $y$ に対する $x$ の個数を数える方針（解法1）のどちらでも解くことができる。領域の境界が対数関数 $y = \log_2 x$ であり、底が $2$ であることから、 $x = 2^k$ のような区切りで考えることがポイントとなる。

解法1

$y$ を正の整数 $k$ に固定して、$x$ の個数を数える。

条件より、 $y$ は正の整数であるから、$y = k$ ($k = 1, 2, 3, \dots$) とおく。このとき、条件 $0 < y \leqq \log_2 x$ は次のようになる。

$$ k \leqq \log_2 x $$

底 $2$ は $1$ より大きいので、これを解くと $x \geqq 2^k$ となる。また、問題の条件から $x < 2^{n+1}$ であるため、$x$ の満たすべき範囲は次のようになる。

$$ 2^k \leqq x < 2^{n+1} $$

これを満たす整数 $x$ が存在するためには、$2^k < 2^{n+1}$ でなければならない。すなわち $k < n+1$ であり、$k$ と $n$ はともに整数であるから、$1 \leqq k \leqq n$ となる。

このとき、$y=k$ 上にある格子点 $(x, y)$ の個数は、不等式 $2^k \leqq x < 2^{n+1}$ を満たす整数 $x$ の個数に等しいから、

$$ (2^{n+1} - 1) - 2^k + 1 = 2^{n+1} - 2^k $$

個となる。求める格子点の総数を $S$ とすると、$S$ は $k$ を $1$ から $n$ まで動かしたときの総和であるから、

$$ S = \sum_{k=1}^{n} (2^{n+1} - 2^k) $$

$$ S = \sum_{k=1}^{n} 2^{n+1} - \sum_{k=1}^{n} 2^k $$

$$ S = n \cdot 2^{n+1} - \frac{2(2^n - 1)}{2 - 1} $$

$$ S = n \cdot 2^{n+1} - 2^{n+1} + 2 $$

$$ S = (n - 1)2^{n+1} + 2 $$

解法2

$x$ を固定して、$y$ の個数を数える。

条件 $1 < x < 2^{n+1}$ を満たす整数 $x$ の範囲は、$2 \leqq x \leqq 2^{n+1} - 1$ である。各 $x$ に対して、条件 $0 < y \leqq \log_2 x$ を満たす整数 $y$ の個数は、$\log_2 x$ 以下の最大の整数であるから、ガウス記号を用いて $[\log_2 x]$ と表せる。

したがって、求める格子点の総数 $S$ は次のように表せる。

$$ S = \sum_{x=2}^{2^{n+1}-1} [\log_2 x] $$

ここで、$k$ を $1 \leqq k \leqq n$ を満たす整数とする。 $2^k \leqq x < 2^{k+1}$ を満たす整数 $x$ については、$k \leqq \log_2 x < k+1$ となるため、$[\log_2 x] = k$ である。また、この範囲に含まれる整数 $x$ の個数は、

$$ (2^{k+1} - 1) - 2^k + 1 = 2^k $$

個である。よって、総和 $S$ は $x$ ごとの和から $k$ ごとの和に書き換えることができる。

$$ S = \sum_{k=1}^{n} k \cdot 2^k $$

これは「等差数列 $\times$ 等比数列」の形の和であるから、$S - 2S$ を計算して求める。

$$ \begin{aligned} S &= 1 \cdot 2^1 + 2 \cdot 2^2 + 3 \cdot 2^3 + \dots + n \cdot 2^n \\ 2S &= 1 \cdot 2^2 + 2 \cdot 2^3 + \dots + (n-1) \cdot 2^n + n \cdot 2^{n+1} \end{aligned} $$

辺々を引くと、

$$ \begin{aligned} -S &= 2^1 + 2^2 + 2^3 + \dots + 2^n - n \cdot 2^{n+1} \\ &= \frac{2(2^n - 1)}{2 - 1} - n \cdot 2^{n+1} \\ &= 2^{n+1} - 2 - n \cdot 2^{n+1} \\ &= (1 - n)2^{n+1} - 2 \end{aligned} $$

両辺に $-1$ を掛けて、

$$ S = (n - 1)2^{n+1} + 2 $$