場合の数・確率系 実践演習

確率漸化式【除去型:隣り合う領域を異なる色で塗る塗り方】【1996年度 麻布大学ほか】

問題はこちら(画像をクリックするとPDFファイルで開きます。)

 

\(n\) 角地図という独特な言い回しが目につく問題です。

 

4色定理

境界線で囲まれるいくつかの領域からなる平面図形があり、境界線を共有する隣り合った領域は異なった色で塗らなければならない。

このとき、この平面図形を塗り分けるには4色あれば十分である。

という主張があり、長年未解決問題で、4色問題と呼ばれていました。

現在は解決し、4色定理と呼ばれています。

証明はコンピューターを利用したかなり強引な力業による証明で、エレガントな証明とは言えず、皮肉を込められ「エレファントな証明」と言われているようです。

まぁ、本問のような単純な図形であれば、4色で十分ということぐらいは分かると思いますが。

さて、本問の話題に移ります。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

隣り合う領域を異なる色で塗る塗り方を考えるということで、(1) で具体例、(2)で一般論というステップアップ方式の構成です。

とは言え、

3角地図の塗り方から4角地図の塗り方へ

4角地図の塗り方から5角地図の塗り方へ

という繋がりを(1) の段階から見出しておくことが大切です。

つまり、漸化式を意識するということになります。

この漸化式の立式なのですが、普段の漸化式とは違う頭の動かし方をします。

そのあたりが、考えどころであり脳みそをフル回転してほしいところです。

解答はコチラ

頻出というわけでもないため、演習経験も少ないと思いますので、もう一題類題をつけておきますから、確認用にぜひご利用ください。

類題はこちら(クリックするとPDFファイルで開きます)

\(n\)角地図の問題に比べて、ひと手間思考要素が入ると思います。

立体の面の塗り分け問題と言うのは、割とよくある問題なので、皆さんも経験があると思います。
(よくあるのは立方体の面の塗り分け)

その手の問題の多くは「漸化式を用いずに、円順列やじゅず順列などを用いて数え上げる」という方針が多いわけです。

そういった意味で色々な問題に紛れてこの問題がポ~ンと置いてあった場合、漸化式の問題と判断しないかもしれません。

ただ、本問は漸化式を持ち出さずとも解くことはできます。

しかし力ずくでまさに「エレファントな解法」です。

試験場ではエレファントな解法もやむを得ませんが、勉強の段階ではせっかくなのでエレガントに漸化式で倒す方針も考えてみてください。

類題の解答はコチラ

-場合の数・確率系, 実践演習
-

© 2022 MathClinic