トップ› 東京大学› 1970年› 文系第1問

東京大学 1970年文系第1問解説

方針・初手

（1） 10進法の数を2進法で表すには、商が0になるまで2で割り続け、そのときに出た余りを逆順（下から上）に並べるのが基本である。

（2） 2進法のまま筆算をして積を求める方法と、一旦10進法に直して計算してから2進法に戻す方法がある。ここでは2進法のまま計算する解法を第一とし、別解で10進法を経由する解法を示す。

（3） 2進数において右から3桁（問題文の「行」は文脈より「桁」の意）ずつ区切って得られる数は、元の数を $2^3 = 8$ を基数とした8進法で展開したときの各桁の数字に相当する。7を法とする合同式を利用して、8と7の関係から倍数判定の仕組みを証明する。

解法1

(1)

365 を商が 0 になるまで 2 で割り、余りを求める。

$$ \begin{aligned} 365 &= 2 \times 182 + 1 \\ 182 &= 2 \times 91 + 0 \\ 91 &= 2 \times 45 + 1 \\ 45 &= 2 \times 22 + 1 \\ 22 &= 2 \times 11 + 0 \\ 11 &= 2 \times 5 + 1 \\ 5 &= 2 \times 2 + 1 \\ 2 &= 2 \times 1 + 0 \\ 1 &= 2 \times 0 + 1 \end{aligned} $$

出てきた余りを下から順に並べることで、2進法表記が得られる。したがって、求める数は $101101101$ である。

(2)

2進法のまま掛け算を計算する。$1011 = 1000 + 10 + 1$ （2進法表記）であることを利用して計算する。

$$ \begin{aligned} 101101 \times 1011 &= 101101 \times (1000 + 10 + 1) \\ &= 101101000 + 1011010 + 101101 \end{aligned} $$

これを足し合わせる。まず下2つの項を足す。

$$ 1011010 + 101101 = 10000111 $$

次に一番上の項と足し合わせる。

$$ 101101000 + 10000111 = 111101111 $$

したがって、積は 2進法で $111101111$ と書かれる。

(3)

正の整数 $x$ の2進法表記を右から3桁ずつ区切ったものを順に $y_0, y_1, \cdots, y_m$ とする。これは、各 $y_i$ ($0 \leqq i \leqq m$) が $0 \leqq y_i < 2^3$ を満たす整数であり、$x$ が次のように表せることを意味している。

$$ x = y_0 + y_1 \times 2^3 + y_2 \times (2^3)^2 + \cdots + y_m \times (2^3)^m $$

すなわち、和の記号を用いて表すと以下のようになる。

$$ x = \sum_{i=0}^{m} y_i \cdot 8^i $$

ここで、7を法とする合同式を考える。$8 \equiv 1 \pmod 7$ であるから、任意の非負整数 $i$ に対して

$$ 8^i \equiv 1^i \equiv 1 \pmod 7 $$

が成り立つ。これを $x$ の式に適用すると、

$$ x = \sum_{i=0}^{m} y_i \cdot 8^i \equiv \sum_{i=0}^{m} y_i \cdot 1 \equiv \sum_{i=0}^{m} y_i \pmod 7 $$

となる。問題の仮定より、和 $y_m + \cdots + y_1 + y_0$、すなわち $\sum_{i=0}^{m} y_i$ は 7 で割り切れるので、

$$ \sum_{i=0}^{m} y_i \equiv 0 \pmod 7 $$

である。よって、

$$ x \equiv 0 \pmod 7 $$

が成り立ち、$x$ も 7 で割り切れることが証明された。

解法2

(2)の別解

与えられた2進数の数を10進法に直してから計算する。

$$ 101101_{(2)} = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 32 + 8 + 4 + 1 = 45 $$

$$ 1011_{(2)} = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 2 + 1 = 11 $$

これらの積を10進法で計算すると、

$$ 45 \times 11 = 495 $$

となる。この $495$ を2進法に直す。$495$ 以下の最大の $2$ の累乗は $2^8 = 256$ であることから、次のように分解できる。

$$ \begin{aligned} 495 &= 256 + 239 \\ &= 2^8 + 128 + 111 \\ &= 2^8 + 2^7 + 64 + 47 \\ &= 2^8 + 2^7 + 2^6 + 32 + 15 \\ &= 2^8 + 2^7 + 2^6 + 2^5 + 8 + 7 \\ &= 2^8 + 2^7 + 2^6 + 2^5 + 2^3 + 4 + 3 \\ &= 2^8 + 2^7 + 2^6 + 2^5 + 2^3 + 2^2 + 2 + 1 \\ &= 2^8 + 2^7 + 2^6 + 2^5 + 2^3 + 2^2 + 2^1 + 2^0 \end{aligned} $$

係数が $1$ となるのは $2^8, 2^7, 2^6, 2^5, 2^3, 2^2, 2^1, 2^0$ の項であり、$2^4$ の項の係数は $0$ である。したがって、これを2進法で表記すると $111101111$ となる。

解説

記数法（$n$進法）の基本原理を問う問題である。 (1) と (2) は $n$進法における変換と四則演算の標準的な手順を確認するものである。(2) は解法1のように2進法のまま繰り上がりに注意して計算する方が、10進法と行き来する手間や変換ミスのリスクを減らせることが多い。

(3) は倍数判定法の原理を証明する問題である。10進法における「各桁の数字の和が9の倍数ならば、その数は9の倍数である」という判定法を証明するのと同じアプローチである。右から3桁ずつ区切ることは、基数を $2^3 = 8$ とした8進法とみなすことに等しい。この見方に気づき、合同式を用いて $8 \equiv 1 \pmod 7$ を活用できるかどうかが鍵となる。