集合と命題 実戦編の問題 全8問

方針

解答

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

「または」の個数は、単純に足すと両方に属するものを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集合のうちに、両方の数え方を行き来しておくとよい。

方針

解答

⓪ 発想(どう考え始めるか) 無理数であることの証明は、背理法を使うのが基本だ。「有理数 $\frac{p}{q}$ だ」と仮定して、矛盾を探す。

${\log }_{2}3=\frac{p}{q}$ は、対数の定義から $2^{p/q}=3$、両辺を $q$ 乗して $2^p=3^q$(${\log }_{2}3>0$ より $p,q$ は正の整数にとれる)。ここで左辺は偶数、右辺は奇数なので、等しくなれるはずがない。素因数 $2$ と $3$ が共通しないことから、矛盾が生じる。

① 有理数と仮定。 ${\log }_{2}3$ が有理数なら、正の整数 $p,q$ を用いて ${\log }_{2}3=\frac{p}{q}$ と書ける(${\log }_{2}3>0$ より $p,q>0$)。

② 整数の等式に。 定義より $2^{p/q}=3$、両辺を $q$ 乗して $$2^p=3^q.$$ ③ 矛盾。 左辺 $2^p$($p\ge 1$)は素因数として $2$ のみをもち、右辺 $3^q$($q\ge 1$)は素因数として $3$ のみをもつ。同じ整数が異なる素因数分解をもつことになり、素因数分解の一意性に反する。よって仮定が誤りで、${\log }_{2}3$ は無理数。

まとめ有理数と仮定すると $2^p=3^q$、左辺は $2$ の累乗・右辺は $3$ の累乗で素因数が食い違い矛盾。${\log }_{2}3$ は無理数。命題(背理法)と整数の融合。

発展。 同じ偶奇(素因数)の議論で、${\log }_{10}2,{\log }_{3}5,{\log }_{2}6$ などの無理性もすぐに示せる($10^q=2^p$ は $5$ の素因数で破綻、など)。逆に ${\log }_{8}4=\frac{2}{3}$ のように有理数になる対数は「両辺が同じ素因数の組でできている」場合に限る。素因数の指数を比べれば、対数が有理数か無理数かを見分けられる。

別解

割った余りの1行で(素因数分解の大定理を使わない)。 $2^p=3^q$($p,q$ は正の整数)が成り立たないことは、2で割った余りだけで言い切れる。左辺 $2^p$ は($p\ge 1$ だから)2で割り切れる: 余り $0$。

右辺 $3^q$ は奇数×奇数×…×奇数で奇数: 余り $1$。余り $0=$ 余り $1$ はあり得ないので、矛盾する。素因数分解の一意性という大定理を使わずに、偶奇だけで示せる。

なお $p,q>0$ にとれる理由(${\log }_{2}3>0$、実際 $1<{\log }_{2}3<2$)を先に押さえるのが作法。この「両辺を素数で割った余りで見る」手筋は、${\log }_{10}2$(右辺 $10^q$ を $5$ で見る)など、対数の無理性証明の全部に通用する。

方針

解答

⓪ 発想(どう考え始めるか) 「必ず存在する」の証明は鳩の巣原理(引き出し論法)をよく使う。箱の数より多くを選べば、同じ箱に2つ入る。

決め手は箱の作り方だ。各整数を $2^k\times (\text{奇数})$ の形に一意に書き、「奇数部分」で分類する。$1$ から $100$ の奇数は $1,3,\dots ,99$ の50個なので、箱は50個。

$51$ 個選べば同じ箱の2数がある。同じ箱の2数は $2^{i}d$ と $2^{j}d$($i<j$)の形で、前者が後者を割り切る。

① 奇数部分で分類。 $1$ から $100$ の各整数を $2^k\times m$($m$ は奇数)と一意に表す。奇数部分 $m$ は $1,3,5,\dots ,99$ の $50$ 通り。これを箱とする。

② 鳩の巣。 $51$ 個の数を、その奇数部分($50$ 通り)で分けると、$51>50$ より、同じ奇数部分 $m$ をもつ $2$ 数 $a=2^{i}m,b=2^{j}m$($i<j$)が必ずある。

③ 割り切る。 $a=2^{i}m,b=2^{j}m$($i<j$)なら $\frac{b}{a}=2^{j-i}$ は整数だから、$a$ は $b$ を割り切る。よって割り切る対が存在する。

まとめ整数を $2^k\times$奇数と書き、奇数部分($50$ 通り)を箱に。$51$ 個なら鳩の巣で同じ奇数部分の $2$ 数があり、一方が他方を割り切る。命題(鳩の巣)と整数の融合。

発展。 「割り切る」という関係で並べた鎖と、その反対の「どの2つも割り切らない」集まり(反鎖)の関係は、順序集合の理論(ディルワースの定理)で扱われる。本問は「最長の反鎖が50個($51\sim 100$)」「鎖が50本で全体を覆える」という2つの50がぴったり一致する実例だ。この一致は偶然ではない。一般に成り立つ定理の一例である。

別解

「鎖」で見る+50個ではダメなことの実例(問題の鋭さ)。 各箱の中身を書き出すと、奇数 $d$ の箱は

$$\{d,2d,4d,8d,\dots \}\cap \{1,\dots ,100\}$$

倍々の鎖であり、鎖の中のどの2数も「一方が他方を割り切る」関係にある。つまり本問は「50本の鎖に51個を配れば、どこかの鎖に2個入る」という形だ。

さらに、51という数が最良であることも確かめられる。$51,52,\dots ,100$ の50個を選ぶと、どの2数も比が2未満なので割り切る対が存在しない(倍以上でないと割り切れない)。50個なら回避できて、51個なら不可能だ。鳩の巣による評価がこれ以上改善できないことまで確かめて、この問題は完結する。

方針

解答

⓪ 発想(どう考え始めるか) これも背理法。$\sqrt{p}=\frac{m}{n}$(既約分数)と仮定して、両辺を2乗すると $m^2=p{n}^2$。

右辺は $p$ の倍数だから $p\mid m^2$。ここで $p$ が素数であることを使う。素数が積を割るなら、因数のどれかを割るので $p\mid m$。$m=pk$ と書いて戻すと、今度は $p\mid n$ も出てしまう。$m$ と $n$ が共通因数 $p$ をもち、「既約」に矛盾する。

① 既約と仮定。 $\sqrt{p}$ が有理数なら、互いに素な正の整数 $m,n$ で $\sqrt{p}=\frac{m}{n}$ と書ける。$2$ 乗して $$m^2=p{n}^2.$$ ② $p\mid m$。 右辺は $p$ の倍数だから $p\mid m^2$。$p$ は素数なので $p\mid m$。$m=pk$ とおく。

③ 矛盾。 $m=pk$ を代入すると $p^2{k}^2=p{n}^2$、両辺 $p$ で割って $p{k}^2=n^2$。よって $p\mid n^2$、再び素数性で $p\mid n$。$m,n$ がともに $p$ で割れるのは「互いに素」に反する。よって仮定が誤りで、$\sqrt{p}$ は無理数。

まとめ $\sqrt{p}=\frac{m}{n}$(既約)から $m^2=p{n}^2$、$p$ が素数だから $p\mid m,p\mid n$ となり既約に矛盾。$\sqrt{p}$ は無理数。命題(背理法)と素数の融合。

発展。 補題「モニック整数係数方程式の有理数解は整数」を持っておくと、$\sqrt{n}$ が有理数 ⟺ $n$ が平方数($x^2-n=0$)、$\sqrt[3]{2}$ は無理数($x^3-2=0$ の整数解なし)、さらに $\sqrt{2}+\sqrt{3}$ の無理性($x^4-10x^2+1=0$ の整数解なし)まで、同じ3行で量産できる。1つの証明を「定理の形」に磨いておく価値の見本だ。

別解

「整数係数方程式の有理数解は整数」で撃つ(整数根定理)。 $\sqrt{p}$ は方程式 $x^2-p=0$ の解だ。次の小定理を使う。

補題: 最高次の係数が1の整数係数方程式 $x^2+bx+c=0$ の有理数解は、必ず整数である。(証明: $x=\frac{m}{n}$(既約)を代入して分母を払うと $m^2=-n(bm+cn)$。$n$ の素因数は $m^2$ を割るが、既約だから $n=1$。)

すると $\sqrt{p}$ が有理数なら整数のはず。だが $1^2=1<p<4\le k^2$($k\ge 2$ では $k^2\ge 4>p$ とは限らないので正しくは)… $p$ は素数だから平方数ではなく、$m^2=p$ を満たす整数 $m$ は存在しない。よって $\sqrt{p}$ は無理数。

既約分数の直接計算(本解)はこの補題の中身を1回展開したもの。補題として切り出しておくと、$\sqrt[3]{2}$ や $\sqrt{2}+\sqrt{3}$(整数係数の4次方程式の解)の無理性にも同じ議論が使え、何度も使い回せる。

方針

解答

⓪ 発想(どう考え始めるか) 「無限にある」は、「有限個しかない」と仮定する背理法に持ち込むのが古くからの方法だ。

素数が $p_1,\dots ,p_n$ で全部だと仮定して、全部の積に1を足した数 $N=p_1{p}_2\cdots p_n+1$ を作る。$N$ をどの $p_i$ で割っても余りは $1$ だ。つまり $N$ の素因数はリストのどれとも違う。だが $2$ 以上の整数は必ず素因数をもつ。「リスト外の素数」の存在が仮定を壊す。

① 有限と仮定。 素数が $p_1,p_2,\dots ,p_n$ の有限個しかないとする。

② $N$ を作る。 $N=p_1{p}_2\cdots p_n+1$ とおく($N\ge 2$)。どの $p_i$ で割っても、$p_1\cdots p_n$ は割り切れるので余りは $1$。よって $N$ はどの $p_i$ でも割り切れない。

③ 矛盾。 $N\ge 2$ は素因数を(少なくとも $1$ つ)もつが、それは $p_1,\dots ,p_n$ のどれでもない=リストにない素数。これは「素数は $p_1,\dots ,p_n$ で全部」という仮定に矛盾する。よって素数は無限に存在する。

まとめ素数が有限個なら、全部の積に $1$ を足した $N$ がどの素数でも割れず、新しい素因数をもって矛盾。素数は無限。命題(背理法)と整数の融合(ユークリッドの証明)。

発展。 $N=p_1\cdots p_n+1$ 型の数(ユークリッド数)は素数とは限らない: $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\times 509$。「$N$ が素数だから矛盾」と書くのは有名な誤りで、正しくは「$N$ の素因数がリスト外」。素数の無限性にはオイラーによる $\sum \frac{1}{p}$ の発散を使う証明など、まったく別の道もあり、証明の多様さ自体がこの定理の豊かさになっている。

別解

背理法を使わない直接版($n!+1$ の素因数)。 「どんな数よりも大きい素数がある」を直接構成で示すこともできる。任意の自然数 $n$ に対して、$N=n!+1$ を考える。$N\ge 2$ だから素因数 $q$ をもつ。

もし $q\le n$ なら、$q$ は $n!$ を割り切る($n!$ は $q$ を因数に含む)。すると $q$ は $N-n!=1$ も割り切ることになり不可能。よって $q>n$。

つまり「どんな $n$ に対しても、$n$ より大きい素数が存在する」。素数はいくらでも大きく、無限にある。仮定を置いて壊す(本解)か、大きい素数を実際に作って見せるか。同じ「積$+1$」の仕掛けを、2通りに説明したものだ。

方針

解答

⓪ 発想(どう考え始めるか) 「すべての $x$ で $>0$」という全称の条件は、グラフの言葉で言い換えると扱える: 放物線 $y=x^2+ax+1$ が $x$ 軸より完全に上にあること。

$x^2$ の係数は正(下に凸)だから、軸より上 ⟺ $x$ 軸と交わらない ⟺ 判別式 $<0$。$a^2-4<0$ を解いて $-2<a<2$。全称命題が判別式の1本の不等式に置き換わった。

① グラフで考える。 $y=x^2+ax+1$ は下に凸。「すべての $x$ で $>0$」は、グラフが $x$ 軸より上、すなわち $x$ 軸と共有点をもたないこと。

② 判別式 $<0$。 $$D=a^2-4\cdot 1\cdot 1=a^2-4<0.$$ ③ 解く。 $a^2<4$、すなわち $$-2<a<2.$$

まとめ全称命題「すべての $x$ で正」は、下に凸の放物線が $x$ 軸と交わらない($D<0$)条件。$-2<a<2$。命題(全称)と $2$ 次関数(判別式)の融合。$a=\pm 2$ は $x$ 軸に接し「$>0$」が崩れる($=0$ になる)ので含めない。

発展。 全称「すべての $x$ で $f(x)>0$」の否定は存在「ある $x$ で $f(x)\le 0$」だ。答えの範囲 $-2<a<2$ の補集合 $|a|\ge 2$ が、ちょうど否定命題の成立範囲になっている。「全称 ⟺ 最小値」「存在 ⟺ 最大値(または1点)」という言い換えは、パラメータつき不等式の問題すべてで使い、2次関数の章では「定義域つき」の形でまた出てくる。

別解

平方完成で最小値を直接見る(判別式を経由しない)。 全称命題は「最小値が正」と同じことだ。平方完成すると

$$x^2+ax+1={\left(x+\frac{a}{2}\right)}^2+1-\frac{a^2}{4}$$

第1項は $0$ 以上(最小は $x=-\frac{a}{2}$ のとき $0$)だから、全体の最小値は $1-\frac{a^2}{4}$。「すべての $x$ で正」⟺「最小値 $>0$」⟺ $1-\frac{a^2}{4}>0$ ⟺ $-2<a<2$。

判別式(本解)は「グラフが軸と交わらない」を式にしたもので、平方完成は「一番低い所でも正」を式にしたものだ。同じ内容だが、平方完成はなぜその範囲か(最小値の式)まで手元に残る。境界 $a=\pm 2$ では最小値がちょうど $0$(グラフが軸に接する)ことも即座に読める。

方針

解答

⓪ 発想(どう考え始めるか) 「$n^2$ が3の倍数 ⟹ $n$ が3の倍数」を直接示そうとすると、$n^2$ の情報から $n$ を復元する向きで進みにくい。

そこで対偶「$n$ が3の倍数でない ⟹ $n^2$ も3の倍数でない」に切り替える。仮定が「$n=3k\pm 1$ と書ける」という使いやすい形になるのが対偶の御利益だ。

あとは2乗して、3で割った余りを計算するだけ。どちらの場合も余り $1$ で、3の倍数にならない。

① 対偶をとる。 示すべき対偶は「$n$ が $3$ の倍数でないならば $n^2$ も $3$ の倍数でない」。

② 余りで場合分け。 $n$ が $3$ の倍数でないとき、$n=3k+1$ または $n=3k+2$($=3(k+1)-1$)、まとめて $n=3k\pm 1$。 $$n^2=(3k\pm 1{)}^2=9k^2\pm 6k+1=3(3k^2\pm 2k)+1.$$ ③ 余り $1$。 $n^2$ は $3$ で割ると余り $1$ で、$3$ の倍数でない。よって対偶が成り立ち、元の命題「$n^2$ が $3$ の倍数 $\Rightarrow$ $n$ が $3$ の倍数」も真。

まとめ対偶「$n$ が $3$ の倍数でない $\Rightarrow$ $n^2$ も $3$ の倍数でない」を、$n=3k\pm 1$ の $2$ 乗が余り $1$ になることで示す。命題(対偶)と整数の融合。$\sqrt{3}$ が無理数の証明にも使う。

発展。 この命題($3\mid n^2\Rightarrow 3\mid n$)は、$\sqrt{3}$ の無理性の証明で中心になる部品だ(前問の $p=3$ の場合で使った性質)。また対偶の技は「余りで分類すると仮定が使いやすくなる」場面全般で有効で、たとえば「$n^2+1$ が3の倍数になる $n$ は存在しない」($n^2$ の余りは $0,1$ のみ)も同じ表から即答できる。

別解

素数の性質で直接(対偶を経由しない1行)。 $3$ は素数だから、次の性質が使える:

素数 $p$ が積 $ab$ を割り切るなら、$p$ は $a$ か $b$ の少なくとも一方を割り切る。$n^2=n\times n$ に適用すると、$3\mid n^2$ から $3\mid n$ または $3\mid n$、すなわち $3\mid n$。1行で終わる。

対偶+余りの場合分け(本解)はこの素数の性質を「余りの計算」で手作りしていることに当たる(余り $1,2$ の2乗が $1$ になる、という表がその中身)。素数の性質を既知として使ってよい場面なら直接1行で、性質そのものの根拠から書く場面なら対偶で書く。答案の文脈で使い分けたい。ちなみにこの命題は $\sqrt{3}$ の無理性証明(前問の $p=3$)の中で部品として使われる。

方針

解答

⓪ 発想(どう考え始めるか) $x=n(A\cap B)$ とおいて、$x$ が満たすべき制約を全部並べる。

上からは「共通部分は小さい方の集合を超えられない」: $x\le 25$。下からは、和集合の公式 $n(A\cup B)=30+25-x$ が全体 $40$ を超えられないこと: $55-x\le 40$、つまり $x\ge 15$。あとは両端が実際に実現できる配置(図)を示して、最大 $25$・最小 $15$ が確定する。

① 最大。 $A\cap B\subset B$ だから $n(A\cap B)\le n(B)=25$。等号は $B\subset A$(このとき $A\cap B=B$)。$n(A)=30\ge 25$ だから $B\subset A$ は可能。よって最大 $25$。

② 最小。 包除より $n(A\cap B)=n(A)+n(B)-n(A\cup B)=55-n(A\cup B)$。$n(A\cup B)\le n(U)=40$ だから $$n(A\cap B)\ge 55-40=15.$$ 等号は $A\cup B=U$(全体を覆う)とき。$n(A)+n(B)=55>40=n(U)$ なので必ず重なりがあり、$A\cup B=U$ は可能。よって最小 $15$。

③ 結論。 最大 $25$、最小 $15$。

まとめ $n(A\cap B)$ は $B\subset A$ で最大 $25$、$A\cup B=U$ で最小 $55-40=15$。集合(包除)と最大最小の融合。

発展。 一般式は $\max (0,n(A)+n(B)-n(U))\le n(A\cap B)\le \min (n(A),n(B))$。下限に $\max$ がつくのは、合計が全体に収まるとき($n(A)+n(B)\le n(U)$)は交わりゼロが可能だから。この評価は確率版($P(A\cap B)\ge P(A)+P(B)-1$、ボンフェローニの不等式)として統計でも働く、実用の不等式だ。

別解

「どちらでもない人数」で読む(制約の意味が見える)。 $x=n(A\cap B)$ とおいて、ベン図の4部屋を $x$ で表す:

• $A$ のみ: $30-x$、$B$ のみ: $25-x$、両方: $x$、どちらでもない: $40-(55-x)=x-15$

4部屋とも人数だから $0$ 以上。$30-x\ge 0,25-x\ge 0$ から $x\le 25$、そして

$$x-15\ge 0⟺x\ge 15$$

つまり下限 $15$ は「どちらでもない人が負の人数になれない」ことから来ていた。$x=25$ は $B$ のみ $=0$($B\subset A$)、$x=15$ は どちらでもない $=0$($A\cup B=U$)で、どちらも実現できる。

不等式を機械的に並べる(本解)のに対し、4部屋の人数で表すと、各不等式が「誰が0人になる配置か」という絵として読める。最大・最小の実現例もこの絵から自動で出てくる。