平方数でも立方数でもない数の個数(包除原理)

方針

解答

⓪ 発想 — どう考え始めるか。 「平方数でも立方数でもない」を数えるのは大変だが、反対側(平方数または立方数)なら数えやすい。全体から引く作戦だ。

「または」の個数は、単純に足すと両方に属するものを2回数えてしまう。両方=平方かつ立方=6乗数。

だから(平方)+(立方)−(6乗)の包除原理で「または」を数え、$1000$ から引く。

① 各個数を数える。 $1000$ 以下で

• 平方数($n^2\le 1000$)は $[\sqrt{1000}]=31$ 個($31^2=961\le 1000<32^2$)、
• 立方数($n^3\le 1000$)は $10$ 個($10^3=1000$)、
• 平方かつ立方(=$6$ 乗数 $n^6\le 1000$)は $[1000^{1/6}]=3$ 個($3^6=729\le 1000<4^6$)。

② 包除で和集合。 「平方数または立方数」は $$31+10-3=38\text{個}.$$ ③ 余事象。 平方でも立方でもないのは $$1000-38=962\text{個}.$$

まとめ 平方 $31$・立方 $10$・両方($6$ 乗)$3$ を包除で「平方または立方」$=38$、全体から引いて $962$。集合(包除)と整数の融合。

発展 — 一歩先へ。 集合が3つに増えると、包除原理は「1つずつ足す−2つの共通部分を引く+3つの共通部分を足す」と符号が交互に続く($n$ 集合でも同じ)。また「平方数で割り切れない数(無平方数)」の割合が $\frac{6}{{\pi }^2}\approx 61\%$ に近づく、という円周率の顔を出す有名な結果も、この包除の無限版から生まれる。

別解

ベン図の4部屋を全部埋める(帳簿方式)。 包除の式を覚えていなくても、ベン図の4つの部屋を1つずつ埋めれば同じ答えに着く。

• 両方(6乗数): $1^6,2^6,3^6=729$ の 3個($4^6=4096$ は超過)
• 平方数のみ: $31-3=$ 28個
• 立方数のみ: $10-3=$ 7個
• どちらでもない: $1000-(28+7+3)=$ 962個

検算として全部屋の合計 $28+7+3+962=1000$ ✓ — 帳簿が締まっていることまで確かめられる。

包除原理(本解)は部屋を埋める作業を式1本に圧縮したもの。集合が3つ以上になると帳簿(部屋)は $2^3=8$ 部屋に増え、包除の式のありがたみが効いてくる — 2集合のうちに、両方の言葉を行き来しておくとよい。