「オイラーグラフ\(\Longleftrightarrow\)すべての頂点が偶点」の証明

頂点と辺(直線でなくともOK)を結んだ図形をグラフと呼びます.

ここで,

・すべての辺を1回だけ通り,
・出発点に戻る
道が存在する(すなわち一筆書きができる)グラフ

つまり一筆書きして出発点に戻ってこられるグラフをオイラーグラフと呼びます.

このオイラーグラフに関して,次の定理があります(頂点に集まる辺の本数を次数とよび,次数が偶数であるような頂点を偶点,次数が奇数であるような頂点を奇点と呼びます).

\[\text{オイラーグラフ}\Longleftrightarrow{頂点がすべて偶点}\]

この定理より,例えば上の三つのグラフの頂点はどれも偶点だけなのでいずれもオイラーグラフであることがわかります.つまり一筆書きできます!下の証明は,一筆書きを見つけるための一般論にもなっています.

証明

(\(\Longrightarrow\)の証明)
グラフがオイラーグラフであるとする.オイラーグラフとはいわば「一筆書きして出発点に戻ってこられる」ようなグラフであるから,各頂点において,その頂点で袋小路になることなく通過できることになる.これはその頂点に「入る」辺があれば必ず「出ていく」辺もセットで存在することを意味する(2本がセットとなる).したがって各頂点における次数は2の倍数となる.ゆえに,すべての頂点は偶点であるといえる.

(\(\Longleftarrow\)の証明)
すべての頂点が偶点となるグラフを考える.辺の数が1のとき,すべての頂点は奇点となるから考える必要はない.したがって辺の本数を\(n\)として\(n\geq2\)で考える.

\(n\)に関する帰納法で証明する.

\(n<k\)のとき,与えらえた命題が正しいと仮定,すなわち\[\text{\(k-1\)個以下の頂点すべてが偶点\(~\Longrightarrow~\)オイラーグラフ}\]であると仮定する.この仮定のもとで,
\[\text{\(k\)個の頂点すべてが偶点\(~\Longrightarrow~\)オイラーグラフ}\]が示せればよい.

まとめると,今手元にある仮定は,

\[
\begin{cases}
\text{\(k-1\)個以下の頂点すべてが偶点\(~\Longrightarrow~\)オイラーグラフ}\quad \cdots (1)\\
\text{\(k\)個の頂点すべてが偶点}\quad \cdots (2)
\end{cases}
\]

であり,この下で,\(k\)個の頂点をもつグラフがオイラーグラフであることが示せればよい.

今,仮定(2)よりグラフの\(k\)個の頂点はすべて偶点である.このグラフ(\(G\)とおく)は閉路\(C\)をもつ.この閉路\(C\)を抜き出す(下図参照).グラフ\(C\)を抜き出したあとのグラフを\(G\backslash C\)とおく.

閉路\(C\)を抜き出しても,各頂点は偶点のままであることに注意する(なぜなら\(C\)を抜き出したあと,頂点から次数が\(2\)の倍数だけ減ることになるが,もともと偶点なので,\(\text{偶数}-2\text{の倍数}=\text{偶数}\)より,残った頂点もやっぱり偶点となるから.下図参照).

残ったグラフ\(G\backslash C\)の頂点はすべて偶点であるから,仮定(1)より,\(G\backslash C\)はすべてオイラーグラフといえる.

グラフ\(C\)を辿る過程で,残ったグラフ\(G\backslash C\)(オイラーグラフ)を寄り道しながらたどれば一筆書きができる(下図参照).すなわち\(G\)はオイラーグラフである.

\(n=2\)で各頂点が偶点であるようなグラフがオイラーグラフであることは明らか.(証明終)

この証明から分かるように,「一筆書きの見つけ方」は以下のようになります:
① まず何でもいいから閉路(ア)をみつけ,その閉路(ア)を取り除く.
② 取り除いたあとのグラフから,一筆書きの経路(イ)(ウ)を見つける.
③ あとは(ア)を進む途中で(イ)(ウ)に寄り道して出発点に戻る.

②の段階で一筆書き(イ)(ウ)が見つけづらい場合は,そのグラフのもとで再び①②の操作を行えばOK.

これで理論上はどんなオイラーグラフも一筆書きの経路が見つかります.

完全順列

問題
5人がそれぞれプレゼントを持ち寄り,それらを無作為に1つずつ再分配してプレゼント交換するとき,5人すべてが自分のプレゼントと異なるプレゼントを受け取る場合は何通りあるか.

一般に,\(1\)~\(n\)の数字を1列に並べるとき,数字\(i~(1\leq i \leq n)\)が左から\(i\)番目に来ないような並べ方を完全順列といいます.今回はこの完全順列の総数の求め方について触れてみたいと思います.

まず,5人にそれぞれ番号をふりましょう.1,2,3,4,5.

このとき,次のように書くことに決めます.

例えば「1が2へ渡し,2が1へ渡し,3が4へ渡し,4が5へ渡し,5が3へ渡す」なら

\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 1 & 4 & 5 & 3
\end{array}
\right)\quad \cdots (1)
\]

例えば「1が2へ渡し,2が3へ渡し,3が4へ渡し,4が5へ渡し,5が1へ渡す」なら

\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 4 & 5 & 1
\end{array}
\right)\quad \cdots (2)
\]

例えば「全員,自分のプレゼントを自分に渡す」なら

\[
\left(
\begin{array}{ccc}
1 & 2 & 3 & 4 & 5\\
1 & 2 & 3 & 4 & 5
\end{array}
\right)
\]

といった具合です(この場合は題意に沿いませんね).このようにして考えると,この「プレゼント交換会」にはある特徴が見えてきます.

まず\((1)\).1に着目すると\[1~\rightarrow~2~\rightarrow~1~\rightarrow~\cdots\]と2つの数字がループしていることが分かります.
3に着目するとこちらは\[3~\rightarrow~4~\rightarrow~5~\rightarrow~3~\rightarrow~\cdots\]と3つの数字がループしています.

\((2)\)はどうでしょう.1に着目すると
\[1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~5~\rightarrow~1\cdots\]と5つの文字がループしています.

このようにみると,「プレゼント交換会」にはループ構造が潜んでいることがわかります.

では,この二つの例に登場しなかった1つの文字のループ,4つの文字のループはあるでしょうか?これは明らかにダメですね.例えば\(1~\rightarrow~1~\rightarrow~\cdots\)は1が自分のプレゼントを受け取ることになり題意に反します.\(1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~1~\cdots\)はよさそうですが残りの5が\(5~\rightarrow~5~\rightarrow~\cdots\)となり自分がプレゼントを受け取ることになりますのでこれもやはり題意に反します.

ここでひとつ言葉を定義しましょう.2つの数字のループ構造互換3つ以上の数字のループ構造巡回置換,ループしないとき(自分が自分のプレゼントを受け取るとき)恒等置換と呼ぶことにします.\((1)\)の例だと互換が1個で巡回置換が1個,\((2)\)の例だと互換が0個で巡回置換が1個,\((3)\)の例だと恒等置換が5個ですね.

ここまでくるとふと思います.結局,完全順列の総数は「互換の数で場合分けして求めればよいのでは?」と.やってみましょう.

    1. 互換が0個のとき
      5つの数字の巡回置換(5つの数のループ)になりますから,
      \[1~\rightarrow~2~\rightarrow~3~\rightarrow~4~\rightarrow~5~\rightarrow~1\cdots\]
      この場合のループの種類は,真ん中の2,3,4,5の順列の数だけ存在するので,\(4!=24\)通り.
    2. 互換が1個のとき
      どの2数を互換とするかで\({}_5\mathrm{C}_2=10\)通り.そのそれぞれに対し,3つの数字の巡回置換(3つの数のループ)を考える.例えば3,4,5のループなら,\[3~\rightarrow~4~\rightarrow~5~\rightarrow~3~\rightarrow~\cdots\]であるから(ⅰ)と同様に考えて真ん中の4,5の順列より\(2!=2\)通り.したがって\(10\times2=20\)通り
    3. 互換が2個のとき
      残りの1つの数字が恒等置換になるので,題意に適さない.

以上より,\(24+20=44\)通り ・・・(答)

さて,ここで問題.今回の問題はたった5人の小規模なプレゼント交換会でしたが,これがもし「10人」「20人」・・・と人数が増えていったらどのように完全順列の総数を求めればいいのでしょうか(また「互換の数で場合分け」はしたくないですよね^^;).また,人数を「\(n\)人」としたとき,完全順列の総数は求まるのでしょうか?

次回はこの話題について書いてみたいと思います.

\(\exists x \forall y\)と\(\forall y \exists x\)の違い

並びが違うだけのように見えますが意味は全く異なります.\(p(x,~y)\)を条件とします.

\(\exists x \forall y~p(x,~y)\)は「\(x\)が存在して,任意の\(y\)に対して\(p(x,~y)\)が成り立つ」となります.最初に「存在して」と言っているあたりが慣れないと気持ち悪いと思います.なので言い換えると,「任意の\(y\)に対して\(p(x,~y)\)が成り立つような\(x\)が,\(y\)とは無関係に存在する」となります.

ポイントは,\(x\)は\(y\)に依存していないということです.

他方,\(\forall y \exists x ~p(x,~y)\)は「どんな\(y\)に対しても,それに対応して\(x\)が存在して,\(p(x,~y)\)が成り立つ」ということです.やはり「存在して」が先に来ると違和感がある人は「\(p(x,~y)\)が成り立つような\(x\)が,\(y\)に応じて存在する」と言い換えればよいと思います.

こちらは\(x\)は\(y\)に依存しているということがポイントです.

【具体例】

条件\(p(x,~y)\)を「\(x\)は\(y\)の親である」という条件とします(\(x,y\in \text{人類}\)).このとき,

\(\exists x \forall y~p(x,~y)\)は,
\[\exists x \forall y~[~\text{\(x\)は\(y\)の親である}~]\]
となります.これを翻訳すると「人間\(x\)が存在して,その人間\(x\)はすべての人間\(y\)の親である」,あるいは「どんな人間\(y\)にとっても親となる人間\(x\)が(その人間\(y\)が誰であるかとは無関係に)存在する」となります.

・・・この命題は常識的に考えれば真とは言いづらいですね^^;宗教のようなある種の信仰を持っている人にとってはこの命題も真と言えるのかもしれませんが.

他方,\(\forall y \exists x ~p(x,~y)\)は,

\[\forall y \exists x ~[~\text{\(x\)は\(y\)の親である}~]\]

これを翻訳すると「どんな人間\(y\)に対しても,その人間\(y\)に対応して\(x\)という人間が存在し,\(x\)と\(y\)との間に親子関係が成り立つ」あるいは「どんな人間\(y\)に対しても,その人間に応じて親\(x\)が存在する」となります.

・・・この命題は明らかに真でしょう.(クローン人間など特殊な例を考えない限り)物理的に人間から生まれなかった人間はいませんから.

以上,\(\exists x \forall y\)と\(\forall y \exists x\)の違い,それは\(x\)と\(y\)の間に関係(対応)があるかないか,ということです!

部分分数分解

数学Bで学びますが,この話題が教科書の例題や練習題に登場する際は,部分分数分解済の式が問題文中で天下りに与えれるのみで,肝心の「どう部分分数分解」するのかには全く触れていません.しかし,実戦では部分分数分解済の式が与えられることなどまずなく,自分で部分分数分解しなければなりません.そこで,ここでは「部分分数分解の仕方」について書いていきたいと思います.

・・・ところで,そもそもなぜ部分分数分解をするのでしょうか?というか,なぜ部分分数分解をしようと思うのでしょうか?方法論の前に,まずこの点にから見ていこうと思います.

少し話が飛びますが,\(\Sigma k^2\)や\(\Sigma k^3\)の公式を導出する際にどんなアイデアを使ったかを思い出しましょう.前者は\((k+1)^3-k^3=3k^2+2k+1\)という恒等式を,後者は\((k+1)^4-k^4=4k^3+6k^2+4k+1\)という恒等式を考え,\(k\)を\(1\)から\(n\)まで変えて辺々足し加えた,つまり

\[
\begin{align*}
&\sum^n_{k=1}\{ (k+1)^3-k^3\}=\sum^n_{k=1}(3k^2+2k+1)\\
&\sum^n_{k=1}\{ (k+1)^4-k^4\}=\sum^n_{k=1}(4k^3+6k^2+4k+1)
\end{align*}
\]

を計算することで例の公式\(\Sigma k^2=\frac{1}{6}n(n+1)(2n+1)\)や\(\Sigma k^3=\left\{\frac{1}{2}n(n+1)\right\}^2\)が得られたのでした.

なぜうまく計算ができて,このような公式をつくることができたのしょうか?

左辺の\(\Sigma\)のうしろ\((k+1)^3-k^3\)を見てみましょう.\(f(k)=k^3\)とおくと,\(f(k+1)=(k+1)^3\)となりますから\((k+1)^3-k^3\)は\(f(k+1)-f(k)\)と表せます.

\((k+1)^4-k^4\)についても同様に\(f(k)=k^4\)とおくと,\(f(k+1)=(k+1)^4\)となりますからやはり\((k+1)^4-k^4\)も\(f(k+1)-f(k)\)と表せます.

どうやら,「\(\Sigma\)の後ろを\(f(k+1)-f(k)\)という形にする」というところに秘密がありそうです.実際,\(\sum (f(k+1)-f(k))\)を計算してみると

\[
\begin{align*}
&\sum^n_{k=1}(f(k+1)-f(k))\\
=&(f(2)-f(1))+(f(3)-f(2))+(f(4)-f(3))+\cdots+(f(n+1)-f(n))\\
=&f(n+1)-f(1)
\end{align*}
\]

となって途中項同士が打ち消しあい,いわば「中抜け」現象がおきて生き残りが\(f(n+1)\)と\(f(1)\)だけになってくれるという,とても嬉しいことが起きます.

このように,\(\Sigma k^2\)や\(\Sigma k^3\)の公式を教科書で導出する際は\((k+1)^3-k^3=3k^2+2k+1\)や\((k+1)^4-k^4=4k^3+6k^2+4k+1\)という恒等式が天下りに与えらえていましたが,どちらも実は「\(f(k+1)-f(k)\)という形を作りたい」という積極的な動機のもとに用意する式だった,と言えます.

\(\Sigma\)計算はその背景に「\(f(k+1)-f(k)\)という形を作りたい」という気持ちがある,ということが分かりました.この点を踏まえた上で,改めて部分分数分解を眺めてみましょう.

例えば\(\sum^n_{k=1}\frac{1}{k(k+2)}\).これもやはり\(f(k+1)-f(k)\)という形を作りたいわけですから,「\(\frac{1}{k}-\frac{1}{k+2}\)と部分分数分解できたら嬉しいなあ・・・」と予想(というか願望?)します.なぜなら\(f(k)=\frac{1}{k}\)とおけば\(\frac{1}{k+2}\)は\(f(k+2)\)と表せることになり,\(f(k)-f(k+2)\)が現れるからです(\(f(k+1)-f(k)\)でなく\(f(k)-f(k+2)\)でいいの?と思った人.大丈夫,これらに本質的な違いはありません,どちらも「中抜け現象」がおきますから).

しかしあくまでこれは「予想」なので,確かめてみる必要があるわけです.予想した\(\frac{1}{k}-\frac{1}{k+2}\)を計算して\(\frac{1}{k(k+2)}\)になるか確かめてみましょう.

\[\frac{1}{k}-\frac{1}{k+2}=\frac{(k+2)-k}{k(k+2)}=\frac{2}{k(k+2)}\]

失敗しました.欲しいのは\(\frac{1}{k(k+2)}\)であって,\(\frac{2}{k(k+2)}\)ではありません.しかし,これは実りある失敗です.なぜなら,今得た式

\[\frac{1}{k}-\frac{1}{k+2}=\frac{2}{k(k+2)}\]

は,ちょっと細工すれば,すなわち両辺を2で割ってやれば

\[
\begin{align*}
&\frac{1}{k}-\frac{1}{k+2}\times\frac{1}{2}=\frac{2}{k(k+2)}\times\frac{1}{2}\\
&\frac{1}{k(k+2)}=\frac{1}{2}\left(\frac{1}{k}-\frac{1}{k+2}\right)
\end{align*}
\]

が得られます.\(\frac{1}{2}\)がついているものの,ちゃんと\(f(k)-f(k+2)\)という形になっています.これならうまくいきそうです.

このように,部分分数分解は,「\(f(k+1)-f(k)\)のような形を作りたい」という動機がまず最初にあり,その気持ちから然るべき予想をし,「予想を計算,その結果をあとで微調整」と考えるのが肝というわけです.

練習問題
\(S_n=\sum^{n}_{k=1}a_k\)とする.このとき,
\[\sum^n_{k=1}\frac{a_{k+1}+a_{k+2}}{S_kS_{k+1}S_{k+2}}\]を\(S_1,~S_2,~S_{n+1},~S_{n+2}\)で表せ.

\(\sum\)のうしろを\(f(k+1)-f(k)\)や\(f(k+2)-f(k)\)のような形にしたいという気持ちから,\(\frac{a_{k+1}+a_{k+2}}{S_kS_{k+1}S_{k+2}}=\frac{1}{S_{k+2}S_{k+1}}-\frac{1}{S_{k+1}S_{k}}\)ではないか?と予想します(\(f(k)=\frac{1}{S_{k+1}S_{k}}\)とおくと\(f(k+1)=\frac{1}{S_{k+2}S_{k+1}}\)となって\(f(k+1)-f(k)\)という形が現れますから).

この予想が正しいか,計算して確認してみます.

\[
\begin{align*}
&\frac{1}{S_{k+2}S_{k+1}}-\frac{1}{S_{k+1}S_{k}}=\frac{S_{k}-S_{k+2}}{S_kS_{k+1}S_{k+2}}\\
=&\frac{(a_1+a_2+\cdots+a_k)-(a_1+a_2+\cdots+a_k+a_{k+1}+a_{k+2})}{S_kS_{k+1}S_{k+2}}\\
=&-\frac{a_{k+2}+a_{k+1}}{S_kS_{k+1}S_{k+2}}
\end{align*}
\]

すなわち

\[\frac{1}{S_{k+2}S_{k+1}}-\frac{1}{S_{k+1}S_{k}}=-\frac{a_{k+2}+a_{k+1}}{S_kS_{k+1}S_{k+2}}\]

を得ます.\(-\)(マイナス)が邪魔ですね.両辺に\(-1\)を掛けて微調整しましょう.

\[\frac{a_{k+2}+a_{k+1}}{S_kS_{k+1}S_{k+2}}=\frac{1}{S_{k+1}S_{k}}-\frac{1}{S_{k+2}S_{k+1}}\]

よって,

\[\sum^{n}_{k=1}\frac{a_{k+2}+a_{k+1}}{S_kS_{k+1}S_{k+2}}=\sum^{n}_{k=1}\left(\frac{1}{S_{k+1}S_{k}}-\frac{1}{S_{k+2}S_{k+1}}\right)\]

「\(f(k)-f(k+1)\)」という形が作れたので,これでうまく「中抜け現象」を作り出せそうですね(以下解答は割愛).

基本ベクトルの外積

同じ基本ベクトル同士の外積は,\(\overrightarrow{0}\)になります.なぜなら,同じベクトルですからその2つのベクトルが作る平行四辺形の面積は0であるから,外積の大きさも0(外積の定義ⅲを参照),したがって\(\overrightarrow{0}\)です.

異なる基本ベクトル同士の外積ならどうでしょうか.たとえば,\(\overrightarrow{e_1}\times\overrightarrow{e_2}\)を考えてみます.

\(\overrightarrow{e_1}\times\overrightarrow{e_2}\)とは,外積の定義ⅰとⅱにより,図1に示す赤いベクトルであるといえます.さらに,\(\overrightarrow{e_1}\)と\(\overrightarrow{e_2}\)が作る平行四辺形は,正方形ですから,その面積は\(1\times1=1\)です.したがって,先ほどの赤いベクトル\(\overrightarrow{e_1}\times\overrightarrow{e_2}\)の大きさは\(1\)である,と言えます(図2参照).

以上により,\(\overrightarrow{e_1}\times\overrightarrow{e_2}\)は上の図の赤いベクトルで,しかもその大きさは\(1\)であることが分かります.このベクトルはほかならぬ\(\overrightarrow{e_3}\)ですね.同様に考え,\(\overrightarrow{e_1}\times\overrightarrow{e_3}\)や\(\overrightarrow{e_3}\times\overrightarrow{e_2}\)なども導出できます.

包除原理

数学Aで次の式を学びました.

\[
\begin{align*}
n(A_1 \cup A_2)=&n(A_1)+n(A_2)\\
&-n(A_1 \cap A_2)
\end{align*}
\]

\[
\begin{align*}
n(A_1 \cup A_2 \cup A_3)=&n(A_1)+n(A_2)+n(A_3)\\
&-n(A_1 \cap A_2)-n(A_1 \cap A_3)-n(A_2 \cap A_3)\\
&+n(A_1 \cap A_2 \cap A_3)
\end{align*}
\]

授業でベン図を用いて理解したことと思います.

この2つの式の流れ的に,

\[
\begin{align*}
&n(A_1 \cup A_2 \cup A_3 \cup A_4)\\
=&~n(A_1)+n(A_2)+n(A_3)+n(A_4)\\
&-n(A_1 \cap A_2)-n(A_1 \cap A_3)-n(A_1 \cap A_4)-n(A_2 \cap A_3)-n(A_2 \cap A_4)-n(A_3 \cap A_4)\\
&+n(A_1 \cap A_2 \cap A_3)+n(A_1 \cap A_2 \cap A_4)+n(A_1 \cap A_3 \cap A_4)+n(A_2 \cap A_3 \cap A_4)\\
&-n(A_1 \cap A_2 \cap A_3 \cap A_4)\\
\end{align*}
\]

などが,そしてさらに一般化して,

\[
n\left(\displaystyle\bigcup_{i}^{n} A_i\right)=\displaystyle\sum_{i}^{n} n(A_i)-\displaystyle\sum_{i<j}^{n}n(A_i \cap A_j)+\displaystyle\sum_{i<j<k}^{n}n(A_i \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{n}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )
\]

が成り立ちそうな気がします.

ここで,\(\displaystyle\bigcup_{i}^{n} A_i\)は\[A_1 \cup A_2 \cup ~\cdots~ \cup A_n\]を,\(\displaystyle\sum_{i<j}^{n}n(A_i \cap A_j)\)などは\(1\leq i<j\leq n~(i,j\in \mathbb{N})\)をみたす\(n(A_i \cap A_j)\)をすべて加えたものを意味するとします.

さて,この予想は正しいのでしょうか??もはやベン図では太刀打ちできません.数学的帰納法で証明してみます.

証明

\(n=l\)のとき予想が正しいとします.この仮定のもとで,\(n=l+1\)のときを考えます.

\[
\begin{align*}
n\left(\displaystyle\bigcup_{i}^{l+1} A_i\right)&=n\left(\left(\displaystyle\bigcup_{i}^{l}A_i\right)\bigcup A_{l+1}\right)\\
&=n\left(\displaystyle\bigcup_{i}^{l}A_i\right)+n\left(A_{l+1}\right)-n\left(\left(\displaystyle\bigcup_{i}^{l}A_i\right) \bigcap A_{l+1}\right)
\end{align*}
\]

ここで,第三項にある\(\left(\displaystyle\bigcup_{i}^{l}A_i\right) \bigcap A_{l+1}\)について考えてみると,

\[
\begin{align*}
&\left(\displaystyle\bigcup_{i}^{l}A_i\right) \bigcap A_{l+1}\\
=&(A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_l)\cap A_{l+1}\\
=&(A_1 \cap A_{l+1} ) \cup (A_2 \cap A_{l+1} ) \cup (A_3 \cap A_{l+1} ) \cup \cdots \cup(A_l \cap A_{l+1} )\\
=&\bigcup^{l}_i(A_i \cap A_{l+1})
\end{align*}
\]

ですから,

\[n\left(\displaystyle\bigcup_{i}^{l+1} A_i\right)=n\left(\displaystyle\bigcup_{i}^{l}A_i\right)+n\left(A_{l+1}\right)-n\left(\bigcup^{l}_i(A_i \cap A_{l+1})\right)\quad \cdots(\ast)\]

を得ます.ここで仮定より,

\[
n\left(\displaystyle\bigcup_{i}^{l} A_i\right)=\displaystyle\sum_{i}^{l} n(A_i)-\displaystyle\sum_{i<j}^{l}n(A_i \cap A_j)+\displaystyle\sum_{i<j<k}^{l}n(A_i \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{l}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )
\]

また,この式の\(A_i\)を\(A_i \cap A_{l+1}\)に変えることにより,

\[
\begin{align*}
&n\left(\displaystyle\bigcup_{i}^{l} (A_i \cap A_{l+1})\right)\\
=&\displaystyle\sum_{i}^{l} n(A_i \cap A_{l+1})-\displaystyle\sum_{i<j}^{l}n(A_i \cap A_{l+1} \cap A_j)+\displaystyle\sum_{i<j<k}^{l}n(A_i \cap A_{l+1} \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{l}_{i<j<\cdots} n(A_i \cap A_{l+1} \cap A_j \cap \cdots )\\
=&\displaystyle\sum_{i}^{l} n(A_i \cap A_{l+1})-\displaystyle\sum_{i<j}^{l}n(A_i \cap A_j \cap A_{l+1})+\displaystyle\sum_{i<j<k}^{l}n(A_i  \cap A_j \cap A_k \cap A_{l+1})-\cdots+(-1)^{n-1}\displaystyle\sum^{l}_{i<j<\cdots} n(A_i  \cap A_j \cap \cdots \cap A_{l+1})
\end{align*}
\]

これら仮定を\((\ast)\)に代入すると,

\[
\begin{align*}
&n\left(\displaystyle\bigcup_{i}^{l+1} A_i\right)\\
=&\displaystyle\sum_{i}^{l} n(A_i)-\displaystyle\sum_{i<j}^{l}n(A_i \cap A_j)+\displaystyle\sum_{i<j<k}^{l}n(A_i \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{l}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )\\
&+n\left(A_{l+1}\right)\\
&-\left\{\displaystyle\sum_{i}^{l} n(A_i \cap A_{l+1})-\displaystyle\sum_{i<j}^{l}n(A_i \cap A_j \cap A_{l+1})+\displaystyle\sum_{i<j<k}^{l}n(A_i  \cap A_j \cap A_k \cap A_{l+1})-\cdots+(-1)^{n-1}\displaystyle\sum^{l}_{i<j<\cdots} n(A_i  \cap A_j \cap \cdots \cap A_{l+1})\right\}\\
=&\left\{\displaystyle\sum_{i}^{l} n(A_i)+n\left(A_{l+1}\right)\right\}-\left\{\displaystyle\sum_{i<j}^{l}n(A_i \cap A_j)+\displaystyle\sum_{i}^{l} n(A_i \cap A_{l+1})\right\}+\left\{\displaystyle\sum_{i<j<k}^{l}n(A_i \cap A_j \cap A_k)+\displaystyle\sum_{i<j}^{l}n(A_i \cap A_j \cap A_{l+1})\right\}\\
&-\cdots+(-1)^{n-1}\left\{\displaystyle\sum^{l}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )+\displaystyle\sum^{l}_{i<j<\cdots} n(A_i  \cap A_j \cap \cdots \cap A_{l+1})\right\}\\
=&\displaystyle\sum_{i}^{l+1} n(A_i)-\displaystyle\sum_{i<j}^{l+1}n(A_i \cap A_j)+\displaystyle\sum_{i<j<k}^{l+1}n(A_i \cap A_j \cap A_k)-\cdots+(-1)^{n-1}\displaystyle\sum^{l+1}_{i<j<\cdots} n(A_i \cap A_j \cap \cdots )
\end{align*}
\]

となって\(n=l+1\)のときも成り立つことが分かります.\(n=1\)のとき成り立つことは自明.(証明終)

見た目はいかついですが高校レベルでも理解できる内容(未習の知識としては\(\bigcup\)の記法と「または,かつ」の分配法則くらい)なので,ぜひ証明にチャレンジしてみてください.集合,場合の数,数学的帰納法,\(\Sigma\)記号の使い方などの総復習にもなりますから.

ちなみに今回証明した式を包除原理と呼びます.

いわゆる「場合分け」って

\(ax^2-2x-a=0\)を解け.ただし,\(a\)は定数とする.

「(ア)\(a=0\)のとき~(イ)\(a\neq0\)のとき~,」という,\(a\)が0かどうかで場合分けするお馴染みの問題です。これを論理式で記述すると

\[
\begin{align*}
&ax^2-2x-a=0 \land(a=0 \lor a \neq 0)\\
\Longleftrightarrow~ & (ax^2-2x-a=0 \land a=0) \lor (ax^2-2x-a=0 \land a \neq 0)\\
\Longleftrightarrow~ & (0-2x-0=0 \land a=0) \lor \left(x=\frac{1\pm\sqrt{1^2-a\cdot(-a)}}{a} \land a \neq 0 \right)\\
\Longleftrightarrow~ & (x = 0 \land a=0) \lor \left(x=\frac{1\pm\sqrt{1+a^2}}{a} \land a \neq 0 \right)
\end{align*}
\]

となります。

ベクトルの外積

外積を定義します.

外積

    1. \(\overrightarrow{a}\)と\(\overrightarrow{b}\)に対して垂直で,
    2. その向きが,\(\overrightarrow{a}\)から\(\overrightarrow{b}\)へねじを回したときにねじが進む向きと一致し,
    3. その大きさが,\(\overrightarrow{a}\)と\(\overrightarrow{b}\)が作る平行四辺形の面積と一致する

ようなベクトルを「外積(outer product)」と呼び,\[\overrightarrow{a}\times \overrightarrow{b}\]と表す.

ことにします.上図の赤いベクトルですね.定義しただけでは役に立たないので,実際にこの外積を求めてみましょう.\(\overrightarrow{a}=(a_1,~a_2,~a_3),~\overrightarrow{b}=(b_1,~b_2,~b_3)\)とおくことにします.

まず,\(\overrightarrow{a}\)は基本ベクトル\(\overrightarrow{e_1}=(1,~0,~0),~\overrightarrow{e_2}=(0,~1,~0),~\overrightarrow{e_3}=(0,~0,~1)\)を用いて,
\[
\begin{align*}
\overrightarrow{a}=
&\left(
\begin{array}{c}
a_1\\
a_2\\
a_3
\end{array}
\right)
=
\left(
\begin{array}{c}
a_1\\
0\\
0
\end{array}
\right)
+
\left(
\begin{array}{c}
0\\
a_2\\
0
\end{array}
\right)
+
\left(
\begin{array}{c}
0\\
0\\
a_3
\end{array}
\right)\\
&=a_1\left(
\begin{array}{c}
1\\
0\\
0
\end{array}
\right)
+
a_2\left(
\begin{array}{c}
0\\
1\\
0
\end{array}
\right)
+
a_3\left(
\begin{array}{c}
0\\
0\\
1
\end{array}
\right)\\
&=a_1\overrightarrow{e_1}+a_2\overrightarrow{e_2}+a_3\overrightarrow{e_3}
\end{align*}
\]

と\(e_1,~e_2,~e_3\)の1次結合で表すことができます.同様にして

\[\overrightarrow{b}=b_1\overrightarrow{e_1}+b_2\overrightarrow{e_2}+b_3\overrightarrow{e_3}\]

したがって外積\(\overrightarrow{a}\times\overrightarrow{b}\)は

\[\overrightarrow{a}\times\overrightarrow{b}=(a_1\overrightarrow{e_1}+a_2\overrightarrow{e_2}+a_3\overrightarrow{e_3})\times(b_1\overrightarrow{e_1}+b_2\overrightarrow{e_2}+b_3\overrightarrow{e_3})\]

と書けることになります.これを「計算」してみればよい.しかしここでひとつ問題があります.「\(\times\)」に関する計算法則を,まだ私たちはなにも知りません(普段使っている「掛ける」とは見た目が同じだけで別物です).したがって,まずこの「\(\times\)」がどのような計算法則を持つのか,調べなくてはなりません.

結論から先に述べますと,

\[
\begin{align*}
&\overrightarrow{a}\times\overrightarrow{b}=-\overrightarrow{b}\times\overrightarrow{a}\tag{A}\\
&k(\overrightarrow{a}\times \overrightarrow{b})=(k\overrightarrow{a})\times \overrightarrow{b}=\overrightarrow{a}\times (k\overrightarrow{b})\tag{B}\\
&\overrightarrow{a}\times(\overrightarrow{b}+\overrightarrow{c})=\overrightarrow{a}\times\overrightarrow{b}+\overrightarrow{a}\times\overrightarrow{c}\tag{C}
\end{align*}
\]

が成り立ちます(\(\mathrm{(A)}\)は定義より明らか.\(\mathrm{(B)}\),\(\mathrm{(C)}\)).注意したいのは,1つ目,「交換するとマイナスがつく」ということです.外積という新しい定義を導入したわけですから,当然,これまでの常識(交換法則)が通用するとは限らないわけです.

では,これらの計算法則に従って,計算してみましょう(実際に紙に書いて手を動かしてみることをおすすめします).

\[
\begin{align*}
&~\overrightarrow{a}\times\overrightarrow{b}\\
=&~(a_1\overrightarrow{e_1}+a_2\overrightarrow{e_2}+a_3\overrightarrow{e_3})\times(b_1\overrightarrow{e_1}+b_2\overrightarrow{e_2}+b_3\overrightarrow{e_3})\\
=&~a_1\overrightarrow{e_1}\times b_1\overrightarrow{e_1}+a_1\overrightarrow{e_1}\times b_2\overrightarrow{e_2}+a_1\overrightarrow{e_1}\times b_3\overrightarrow{e_3}\\
&+a_2\overrightarrow{e_2}\times b_1\overrightarrow{e_1}+a_2\overrightarrow{e_2}\times b_2\overrightarrow{e_2}+a_2\overrightarrow{e_2}\times b_3\overrightarrow{e_3}\\
&+a_3\overrightarrow{e_3}\times b_1\overrightarrow{e_1}+a_3\overrightarrow{e_3}\times b_2\overrightarrow{e_2}+a_3\overrightarrow{e_3}\times b_3\overrightarrow{e_3}\\
=&~a_1b_1(\overrightarrow{e_1}\times \overrightarrow{e_1})+a_1b_2(\overrightarrow{e_1}\times \overrightarrow{e_2})+a_1b_3(\overrightarrow{e_1}\times \overrightarrow{e_3})\\
&+a_2b_1(\overrightarrow{e_2}\times \overrightarrow{e_1})+a_2b_2(\overrightarrow{e_2}\times \overrightarrow{e_2})+a_2b_3(\overrightarrow{e_2}\times \overrightarrow{e_3})\\
&+a_3b_1(\overrightarrow{e_3}\times \overrightarrow{e_1})+a_3b_2(\overrightarrow{e_3}\times \overrightarrow{e_2})+a_3b_3(\overrightarrow{e_3}\times \overrightarrow{e_3})
\end{align*}
\]

ここで,

\[
\begin{align*}
&\overrightarrow{e_1}\times\overrightarrow{e_1}=\overrightarrow{e_2}\times\overrightarrow{e_2}=\overrightarrow{e_3}\times\overrightarrow{e_3}=\overrightarrow{0} \\
&\overrightarrow{e_1}\times\overrightarrow{e_2}=\overrightarrow{e_3},\quad\overrightarrow{e_1}\times\overrightarrow{e_3}=-\overrightarrow{e_2}\\
&\overrightarrow{e_2}\times\overrightarrow{e_1}=-\overrightarrow{e_3},\quad\overrightarrow{e_2}\times\overrightarrow{e_3}=\overrightarrow{e_1}\\
&\overrightarrow{e_3}\times\overrightarrow{e_1}=\overrightarrow{e_2},\quad\overrightarrow{e_3}\times\overrightarrow{e_2}=-\overrightarrow{e_1}
\end{align*}
\]

ですから(なぜ?),結局外積\(\overrightarrow{a}\times\overrightarrow{b}\)は
\[
\begin{align*}
\overrightarrow{a}\times\overrightarrow{b}
=&~a_1b_1\cdot \overrightarrow{0}+a_1b_2\overrightarrow{e_3} -a_1b_3\overrightarrow{e_2}\\
&-a_2b_1\overrightarrow{e_3}+a_2b_2\cdot \overrightarrow{0}+a_2b_3\overrightarrow{e_1}\\
&+a_3b_1\overrightarrow{e_2}-a_3b_2\overrightarrow{e_1}+a_3b_3\cdot \overrightarrow{0}\\
=&~(a_2b_3-a_3b_2)\overrightarrow{e_1}+(a_3b_1-a_1b_3)\overrightarrow{e_2}+(a_1b_2-a_2b_1)\overrightarrow{e_3}\\
=&~(a_2b_3-a_3b_2)\left(
\begin{array}{c}
1\\
0\\
0
\end{array}
\right)
+
(a_3b_1-a_1b_3)\left(
\begin{array}{c}
0\\
1\\
0
\end{array}
\right)
+
(a_1b_2-a_2b_1)\left(
\begin{array}{c}
0\\
0\\
1
\end{array}
\right)\\
=&~\left(
\begin{array}{c}
a_2b_3-a_3b_2\\
a_3b_1-a_1b_3\\
a_1b_2-a_2b_1\\
\end{array}
\right)
\end{align*}
\]

を得ます.この結果は覚えておくとよいでしょう.以下のように覚えるのがおすすめです.

\[\overrightarrow{a}\times\overrightarrow{b}=\left(
\begin{array}{c}
a_2b_3-a_3b_2\\
a_3b_1-a_1b_3\\
a_1b_2-a_2b_1\\
\end{array}
\right)\]

内積(inner product)と言葉自体は似ているのですが,内積はスカラー量であるのに対して,外積はベクトル量であることに注意してください.

注意
高校数学においても垂直なベクトルを求めるシーンは多いのですが,高校範囲外なので,テストや模試等では検算にとどめておくのが無難かも知れません.

「かつ」「または」の分配法則

\(p,~q,~r,~s\)を命題とする.このとき,
\[p\land (q \lor r) \Longleftrightarrow (p\land q) \lor (p\land r)\]
が成り立ちます.高校数学的にはベン図で証明(というか説明?)しますが,論理学的には真理値表で証明します.

他にも,\[p\lor (q \land r) \Longleftrightarrow (p\lor q) \land (p\lor r)\]や\[(p\lor q) \land (r \lor s) \Longleftrightarrow (p\land r) \lor (q\land r) \lor (p \land s) \lor (q \land s)\]や
\[(p\land q) \lor (r \land s) \Longleftrightarrow (p\lor r) \land (q\lor r) \land (p \lor s) \land (q \lor s)\]なども同様に成り立ちます.数や文字の分配法則にそっくりですね.証明はこちら

センター試験お疲れ様でした

受験生の皆さんセンター試験お疲れ様でした.
うまくいった人,失敗した人,様々だと思います.

うまくいった人へ.おめでとうございます.引き続き2次試験に向けて頑張ってください.油断せずにね.

失敗した人へ.

相当落ち込んでいると思います.自責の念にも駆られて苦しいと思います.もしかしたら出願校の変更も考えているかもしれません.

センター試験はアプローチすべき解法が出題者によって予め定められており,それをなぞる形で解答していく.しかもかなりシビアな時間設定.これは,出題者の意図が読み取れない場合はかなりの苦戦を強いられることを意味します.こういった形式が得意な人がいる一方で,人に指示されるのが嫌いなタイプの人や,自分で考え自分の解法でじっくり思考し自由に解きたいタイプの人にとっては相当ストレスフルな出題形式でしょう.なので,こういうスタイルでうまく得点できずともそれは単に適性・相性の問題なだけかも知れません.実際,センター試験でうまく得点できずとも数学力の高い人間は存在します.今回準備を重ねてきたにも関わらず得点できなかった人,あなたはきっとこのタイプです.大丈夫,ちゃんと実力はあります.自信をもって2次試験,併願校受験に向けて粛々と勉強を続けましょう.

失敗も大事な経験です.

これは慰めのための綺麗事ではありません.こんな言葉があります.

An expert is a person who has found out by his own painful experience all the mistakes that one can make in a very narrow field.

Niels Bohr – wikiquote


「非常に狭い範囲において,経験しうるすべての間違いを経験した者を『専門家』と呼ぶ.」

ノーベル賞物理学者ボーアの言葉です.ほんとうにいい言葉ですね.

幸運を祈ります.

© 2022 佐々木数学塾, All rights reserved.