§２．証明のマジック背理法（配線問題）
数学の証明は背理法と数学的帰納法なくしては成り立たない。
ここでは，背理法のすばらしさとその有用性について，「配線問題」と呼ばれる問題を通して，味わってもらうことにしよう。
| 背理法の論法とは？ |
| 「事柄Ｐが正しい」ことの証明 ① 「事柄Ｐが正しくない」と仮定する。 ② ①の仮定のもとに議論をすすめていく。 ③ 議論の途中で矛盾が生じる。 ④ 矛盾が生じた原因は，①の仮定にあると判断できる。したがって，①の仮定は誤りである。 ⑤ 「事柄Ｐは正しい」と間接的に断定できる。 |
| 配線問題 |
| 電気製品の内部は多くの配線が複雑に絡み合っている。最近では，製品の製造のオ－トメ－ション化が進み，多くの 端子が配置してある絶縁基盤上に複雑な回路が伝導物質でプリントされている場合が多い。この場合，伝導物質から なる線分が交差すると，当然のことながらショ－トしてしまう。そこで，どの２本の線分も交差しないように回路を設計し なければない。 今，絶縁基盤上の勝手な位置に＋の端子と－の端子がそれぞれ10個ずつ配置されているものとする。これら20個の 端子のどの３個も一直線上にはないものとするとき，これら20個の端子がどのように配置されていようとも，＋と－の端 子を結ぶ10本の線分をショ－トしないように（交差しないように）プリントすることが可能であることを証明しなさい。 |
| この配線問題を，より明確にかつ数学的に書き直すと次のようになる。 |
| 配線問題 |
| 平面上に赤点と青点がそれぞれ10個づつ存在する。ただし，どの３点も一直線上には存在しないものとする。 今，赤点と青点１つずつを線分で結び，10本の線分を引く。このとき，どの２本の線分も交差することのない結び方が 必ず存在することを証明しなさい。 |
| ［証明］ |
| 赤点と青点を結ぶ線分が交差していてもよいとすると，その結び方は全部で 10！＝10×9×8×7×6×5×4×3×2×1＝3628800 通り 存在する。 これら全ての結び方の中には，その線分の長さの総和が最小の結び方が必ず存在する。その結び方をＭとよぶこと にする。結び方Ｍが，その10本の線分のどの２本も交差していないことを背理法を使って以下に証明する。 |
 |
| 今，逆に，結び方Ｍの中のある２本の線分Ｂ1Ｗ2，Ｂ2Ｗ1が点Oで 図１ Ａ のように交差しているものと仮定する。 このとき，これら２本の線分を図１ Ｂ のように，Ｂ1Ｗ1，Ｂ2Ｗ2となるように結び直し，残り８本の線分は元のままとする結び方Ｍ’に着目してみましょう。 ここ で，明らかな定理，「三角形の２辺の長さの和は残り１辺の長さよりも大きい」 を思いだしてみよう。この定理を使うと， Ｂ1Ｗ2＋Ｂ2Ｗ1＝Ｂ1Ｏ＋ＯＷ2＋Ｂ2Ｏ＋ＯＷ1 ＝Ｂ1Ｏ＋ＯＷ1＋Ｂ2Ｏ＋ＯＷ2 ＞Ｂ1Ｗ1＋Ｂ2Ｗ2 となる。 したがって，(結び方Ｍの線分の長さの総和) ＞ (結び方Ｍ’の線分の長さの総和) が成り立つ。しかし，これは，「結び方Ｍが，全ての結び方の中で，その線分の長さの総和が最小になる結び方である」という仮定に矛盾する。よって，その線分の長さの総和が最小になる結び方においては，どの２本の線分も交差していないことが示された。 QED. |