包除原理・不等式による絞り込み

【NT04】二進数表記

$k$ 進数で表された数値 $x$ を $(x{)}_k$ と書くことにします。
(1) $(7.25{)}_{10}$ を $2$ 進数で表してください。
(2) $(7.2{)}_{10}$ を $2$ 進数で小数点以下 $7$ 桁まで表してください。
必要なら電卓を使ってください。
 
≫ 整数の k 進数展開についてはこちらの記事を参照してください。
 
【ヒント】$2$ 進数は $2$ ごとに繰り上がる $1$ と $0$ のみで表される数字です。$10$ 進数の整数 $0,1,2,3,4$ は 2 進数ではそれぞれ
 $$0,1,10,11,100$$
のように表されます。 $10$ 進数 $N$ を
 $$N=d_n{2}^n+d_{n-1}{2}^{n-1}+\cdots +d_1{2}^1+d_0{2}^0$$
と表したときの係数 $d_n$ が各桁を表すことになります：
 $$\begin{array}{rl}& (0{)}_{10}=0\times 2^0⟹(0{)}_2\\ & (1{)}_{10}=1\times 2^1⟹(1{)}_2\\ & (2{)}_{10}=1\times 2^1+0\times 2^0⟹(10{)}_2\\ & (3{)}_{10}=1\times 2^0+1\times 2^0⟹(11{)}_2\\ & (4{)}_{10}=1\times 2^2+0\times 2^1+0\times 2^0⟹(100{)}_2\end{array}$$
整数ならそれほど難しくないのですが、小数だとはたしてどうなるか … 実は (2) はかなりの難問です。
　【解答】(1) 最初に上の説明の通り $(7{)}_{10}$ を $2^n$ で表すと
 $$(7{)}_{10}=1\times 2^2+1\times 2^1+1\times 2^0=(111{)}_2$$
と表記されます。計算技術的には簡略化された方法が知られているので、記事の後半で紹介しておきます。

小数点以下は $\frac{1}{2^n}$ の項を作って表すことになります。
電卓などで $\frac{1}{2^n}$ の数値を予め並べておきます。
 $$\begin{array}{rl}& \frac{1}{2}=0.5,\frac{1}{4}=0.25,\frac{1}{8}=0.125,\frac{1}{16}=0.0625,\frac{1}{32}=0.03125\\ & \frac{1}{64}=0.015625,\frac{1}{128}=0.0078125,\frac{1}{256}=0.0390625\end{array}$$
すると $0.25$ は
 $$0.25=\frac{1}{4}=0\times \frac{1}{2^1}+1\times \frac{1}{2^2}=(0.01{)}_2$$
と表されます。したがって先の $7$ の $2$ 進数表示と合わせて
 $$(7.25{)}_{10}=(111.01{)}_2$$
と表されることがわかります。小数点以下についても簡略化された計算法がありますので、記事下の補足を読んでおいてください。

(2) $0.25$ は比較的すっきり表せましたが、$2$ 進数で $0.2$ という数字は相性が悪く、無限級数になってしまいます（これがコンピュータの浮動小数点数演算の誤差の原因となっています）。問題では小数点以下 $7$ 桁まで求めよとなっているので、(1) で並べた数字を使って近似値を計算します。
 
$0.2$ の中には $0.125$ が１つあるので、$\frac{1}{2^3}$ の位は $1$ です。
そして、$0.2$ から $0.125$ を引きます。
 $$0.2-0.125=0.075$$
したがって、$\frac{1}{2^3}$ の桁は $1$ となります。以降同じようにして各桁の数字を求めていきます。

　　$0.075－0.0625=0.0125$　　∴$\frac{1}{2^4}$ の桁は $1$
　　$0.0125<0.03125$　　∴$\frac{1}{2^5}$ の桁は $0$
　　$0.0125<0.015625$　　∴$\frac{1}{2^6}$ の桁は $0$
　　$0.0125-0.0078125$　　∴$\frac{1}{2^7}$ の桁は $1$
　
以上より、$(7.2{)}_{10}=(111.0011001{)}_2$ と近似できます。

【補足】10 進数から 2 進数への変換する手順についてまとめておきます。まず整数部分から。$6$ を例にとって計算してみます。$6$ を $2$ で割り、商が $0$ になるまで順に $2$ で割っていきます。

　　6/2 = 3　余り 0
　　3/2 = 1　余り 1
　　1/2 = 0　余り 1

　そして余りを下から順に並べて $(110{)}_2$ が得られます。小数点以下の数は整数なるまで順に小数部分に $2$ をかけていきます。そして掛け算の結果が $1$ 未満ならその桁は $0$, $1$ 以上ならその桁は $1$ となります。たとえば $10$ 進数で $0.25$ だと、

　　0.25 × 2 = 0.5　：　0　（小数点以下1位）
　　0.5 × 2 = 1　　 ：　1　（小数点以下2位）

となって、上から並べて $(0.01{)}_2$ となります。 $10$ 進数で $0.2$ ならば、

　　0.2×2 = 0.4　：　0　（小数点以下1位）
　　0.4 × 2 = 0.8　：　0　（小数点以下2位）
　　0.8 × 2 = 1.6　：　1　（小数点以下3位）
　　0.6 × 2 = 1.2　：　14　（小数点以下4位）
　　0.2 × 2 = 0.4　：　0　（小数点以下5位）

のように循環することが簡単にわかります：
　
$$(0.2{)}_{10}=(0.001100110011\dots \dots {)}_2$$

【NT05】包除原理

(1) $1$ から $99$ までの整数のうち、$2,3,5$ のいずれの数でも割り切れない数はいくつありますか。
(2) $99!$ を素因数分解したとき素因数 $5$ はいくつ含まれますか。

【ヒント】「含む含まれない」を考える問題です。混乱したらベン図などを書いて整理してみてください。ガウス記号を用いるとすっきりとした答案を作成できます。$[N]$ は $N$ を超えない整数という意味です。たとえば $[10.5]=10$ です。小問 (2) は $99!$ を素因数分解したときの $5$ の指数を求める問題です。

【考え方】$1$ から $10$ まで数を並べて $3$ の倍数に○をつけてみます。

1, 2, ③, 4, 5, ⑥, 7, 8, ⑨, 10

　$3$ の倍数は $3$ つごとに現れますから、$1$ から $10$ までに含まれる $3$ の倍数は $10$ を $3$ で割って端数を切り捨てた数 $[10/3]$ に等しいことになります。以上のことをふまえて解答を作ります。
　
　
【解答】(1) $99$ から $2$ の倍数、$3$ の倍数、$5$ の倍数の個数を引いてみます。
　
$$99-\left[\frac{99}{2}\right]-\left[\frac{99}{3}\right]-\left[\frac{99}{5}\right]=99-49-33-19=-2$$
　「マイナスの数？　計算ミス？」と驚かれるかもしれませんが、引きすぎがあるということです。$2$ と $3$ の共通倍数、$2$ と $5$ の共通倍数、$3$ と $5$ の共通倍数を二重に引いてしまっているので、今度はそれを足して戻します。
　
$$-2+\left[\frac{99}{6}\right]+\left[\frac{99}{10}\right]+\left[\frac{99}{15}\right]=-2+16+9+6=29$$
　しかし今度は $2,3,5$ の共通倍数 $30$ を足し過ぎているので再度引きます。
　
$$29-\left[\frac{99}{30}\right]=29-3=26$$
　分かりにくいと思ったら、下のベン図を参照してください。

　

(2) $99!$ を書き下しておきます。
　
$$99!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdots 24\cdot 25\cdots 74\cdot 75\cdots 97\cdot 98\cdot 99$$
　素因数 $5$ は $5$ の倍数の中にしかないので、それを抜き出してみると
　
$$5,10,15,20,25,30,35,\dots ,70,75,80,\dots ,90,95$$
　$25$ の倍数 $25,50,75$ には $5$ の倍数が $2$ つ含まれます。それ以外は $1$ つずつです。つまり $5$ の倍数について数え上げて、そのあと $25$ の倍数を数え上げて足せば、含まれる素因数 $5$ を過不足なく数えることができます。したがって、$99!$ に含まれる素因数 $5$ の数は
　
$$\left[\frac{99}{5}\right]+\left[\frac{99}{25}\right]=19+3=22$$
となります。

【NT06】分数式 4x/(2x^2+1) が整数となる条件

　次の分数式
$$f(x)=\frac{4x}{2x^2+1}$$が整数となるような実数 $x$ を求めてください。

【ヒント】二次方程式の問題に持ち込みます。
　
　
【解答】$n$ を整数として $f(x)=n$ とおくと次のような二次方程式が得られます。
　
$$\begin{array}{}\text{(1)}& 2n{x}^2-4x+n=0\end{array}$$
　$x$ は実数という条件があるので、判別式 $D/4\ge 0$ より
　
$$\frac{D}{4}=4-2n^2\ge 0$$
　これを解いて
　
$$n\le 2$$
　$n$ は整数なので、
　
$$\begin{array}{}\text{(2)}& n=-1,0,1\end{array}$$
となります。$n$ を含んだ形で二次方程式 (1) の解を表すと
　
$$x=\frac{2\pm \sqrt{4-2n^2})}{2n}$$
となります。$n=-1,0,1$ の値を代入すると、5 つの解
　
$$x=-1\pm \sqrt{2},0,1\pm \sqrt{2}$$
を得ます。

【NT07】不等式で絞り込みます

　分数式
$$f(n)=\frac{2n}{n^2+n+1}$$が整数となるような整数 $n$ を求めてください。

【ヒント】前回の問題に似ていますが、今回は整数解を求めます。
　
　
【解答】まず $n=0$ という解がすぐに見つかるので、以下では $n\ne 0$ として $0$ 以外の解を探します。$f(n)$ が整数であるためには分母が分子以下なくてはなりません。
　
$$\begin{array}{}\text{(1)}& n^2+n+1\ne |2n|\end{array}$$
　絶対値記号を外して場合分けします。

[1] $n>0$ のとき、
　
$$n^2+n+1\le 2n$$
となります。左辺が $({)}^2$ となるような形に変形して
　
$${(n-\frac{1}{2})}^2\le -\frac{3}{4}$$
このような $n$ は存在しません。

[2] $n<0$ のとき
　
$$n^2+n+1\le -2n$$
左辺が $({)}^2$ の形になるように変形すると、不等式
　
$${(n-\frac{3}{2})}^2\le \frac{5}{4}$$
を得ます。これを解くと
　
$$-\sqrt{5}\le 2n+3\le \sqrt{5}$$
　$\sqrt{5}=2.236\dots$ であり、$2n+3$ は整数なので
　
$$-n\le 2n+3\le 2$$
　これを解いて
　
$$-2\le n\le -1$$
　したがって、$-2$ と $n=-1$ が解の候補となりますが、
　
$$f(-2)=-\frac{4}{3},f(-1)=-2$$
なので、$n=-1$ が解です。以上より、$f(n)$ が整数となるような整数 $n$ は $0$ と $-1$ です。