・擬似4色問題                           GAI 氏

 どんな地図でも4色あれば塗り分けられることはよく知られている。しかし、何通りの塗り方
があるかはあまり知られていない。

 そこで、今異なる4色があり、地図の代表として同じ矩形が6つ一列に並んだ図形GLと正
6角形の中心と各頂点を結び正三角形が円状になっている図形GSを4色以内で塗り分け
る方法が何通り可能かを考える。

 同じ色を何度でも使ってもよいものとし、4色すべてを用いる必要はないが、隣り合った二
つの領域は別々の色を塗るとする。

 ただし、GSの図形は回転してできる塗り方は同じ塗り方とする。さて、GL、GSそれぞれ何
通り可能か?

 なるだけ論理的に導けるかに挑戦して下さい。もし壁が突破できないなら、コンピュータの
実験からでも結果を教えて下さい。


 らすかるさんからのコメントです。(平成28年1月12日付け)

図形GL

 1個目は4色のどれでもよく、2個目以降は一つ前と異なる3色のどれかであればよいので、
4×3^5=972通り

図形GS

 2色:塗り方は1通り、色の選び方が4C2=6通りなので6通り

 3色:(2,2,2)か(3,2,1)

 (2,2,2)の場合、塗り方はABACBC形とABCABC形の2通り
  ABACBC形は色の選び方が、4×3C2=12通り
  ABCABC形は色の選び方が、4C3×2=8通り

 (3,2,1)の場合、塗り方はABABAC形のみ
  色の選び方が4P3=24通り

 よって、3色は全部で12+8+24=44通り

 4色:(2,2,1,1)か(3,1,1,1)

 (2,2,1,1)の場合、塗り方はABABCD形、ABACBD形、ACABDB形、ABCABD形の3通り
  ABABCD形は色の選び方が4!=24通り
  ABACBD形も、4!=24通り
  ACABDB形は、4!/2=12通り
  ABCABD形も、4!/2=12通り

 (3,1,1,1)の場合、塗り方はABACAD形のみで
  色の選び方は、4×2=8通り

 よって、4色は全部で24+24+12+12+8=80通りなので、全部の合計は6+44+80=130通り

追記:図形GSの別解

 一般に、円をn個の扇形に分けて回転したものを同一視しない場合を考える。

 1個目とn-1個目の色が異なる場合は、n個目を削除すれば、n-1個の扇形のパターンに
なる。

 このとき、n個目に選べる色は、2通り

 1個目とn-1個目の色が同一の場合は、n個目とn-1個目を削除すれば、n-2個の扇形の
パターンになる。

 このとき、n-1個目の色は1個目と同じ固定色、n個目の色は3通り

 よって、n個の扇形に分けた場合のパターン数をa[n]とすれば、

  a[n]=2a[n-1]+3a[n-2] 、a[2]=12、 a[3]=24

 これより、 a[6]=732

 このうち、180度回転対称形は、a[3]通り、120度回転対称形は、a[2]通りだから、求める
場合の数は、 (a[6]-a[3]-a[2])/6+a[3]/3+a[2]/2=130(通り)


 GAI さんからのコメントです。(平成28年1月13日付け)

 *この漸化式の発見に驚きです。
(これって一列に並べたとき始めと終わりの色が異なるものの並び方ですよね。)

*a[6]=732の値をコンピューターの活用で探していました。後はこの732パターンのそれぞれ
 をずらす4通り(回転させる様子)の中で最小になるものを代表にしていった。

 180度回転対称形・・・、120度回転対称形・・・から、求める場合の数は・・・

*こんな計算方法があるんだ!上記の732個の代表を目でチェックして重複分を除く手作業
 をやっていったら130個が残っていた。

 いや〜この別解のやり方は華麗そのものですね。同じ結果を得るのにこんなにも洗練され
た方法が採れることに、まさに頭は使いようの格言が身に沁みます。

 この華麗な方法を他のGS図形について応用するにはと思い挑戦してみました。

 a[n]=2a[n-1]+3a[n-2] の漸化式から、

 a[2]=12 、a[3]=24 、a[4]=84 、a[5]=240 、a[6]=732 、a[7]=2184 、a[8]=6564 、
 a[9]=19680 、a[10]=59052 、a[11]=177144 、a[12]=531444

が算出でき、例のGS(n)の図形に対する4色彩色方法は

 GS(2)=a[2]/2=6 、GS(3)=a[3]/3=8 、GS(4)=(a[4]-a[2])/4+a[2]/2=(84-12)/4+12/2=24
 GS(5)=a[5]/5=48
 GS(6)=(a[6]-a[3]-a[2])/6+a[3]/3+a[2]/2=(732-24-12)/6+24/3+12/2=130
  (らすかるさんの別解の方法)
 GS(7)=a[7]/7=312
 GS(8)=(a[8]-a[2]+a[4]-a[2])/8+a[2]/2=(6564-12+84-12)/8+12/2=834
 GS(9)=(a[9]-a[3])/9+a[3]/3=(19680-24)/9+24/3=2192
 GS(10)=(a[10]-a[5]-a[2])/10+a[5]/5+a[2]/2=(59052-240-12)/12+24/3+12/2=5934
 GS(11)=a[11]/11=16104
 GS(12)=?

 このGS(12)の構成の方法がわかりませんでした。GS(8)もこじつけの感もあります。どんな
式で構成すればいいのですか?急に上手く算出できる式が分からなくなりました。


 らすかるさんからのコメントです。(平成28年1月13日付け)

 GS(8)は、a[4]の中にa[2]の個数が含まれていますので、

  (a[8]-a[4])/8+(a[4]-a[2])/4+a[2]/2=834

 GS(12)は、a[6]の中にa[3]とa[2]が含まれ、a[4]の中にa[2]が含まれていますので、

  (a[12]-a[6]-a[4]+a[2])/12+(a[6]-a[3]-a[2])/6+(a[4]-a[2])/4+a[3]/3+a[2]/2=44368

となりますね。

# GS(8)の先頭のa[8]-a[4]はa[8]-(a[4]-a[2])-a[2]をまとめたもの、GS(12)の先頭の
a[12]-a[6]-a[4]+a[2]は、a[12]-(a[6]-a[3]-a[2])-(a[4]-a[2])-a[3]-a[2]をまとめたものです。


 GAI さんからのコメントです。(平成28年1月13日付け)

 GS(12)=44368 となる理由は、

(a[12]-(a[6]-a[3]-a[2])-(a[4]-a[2])-a[3]-a[2])/12+(a[6]-a[3]-a[2])/6+(a[4]-a[2])/4+a[3]/3+a[2]/2

をまとめたものだったのですね。実験的に、(a[12]+a[6]+a[4]-a[2])/12+a[3]/3+a[2]/2 で計
算すると求められるとは長い試行錯誤で見つけてはいたんですが、何でこんな式となってし
まうのかまったく分からず途方に暮れていました。

 上記の式を整理してみたら、(a[4]=2a[3]+3a[2]を利用する。)実験的に探していた式が現
れ、これでやっとこの式の意味が掴めました。何となくどんなGS(n)の値でもコンピューター
無しで求められるような気がしてきました。


 らすかるさんからのコメントです。(平成28年1月13日付け)

 もう少し簡単に計算するには、便宜上a[1]=0とし、b[n]=(a[n]-Σ[kはnより小さいnの約数]b[k])/n
とすると、

 b[1]=0 、b[2]=12/2=6 、b[3]=24/3=8 、b[4]=(84-12)/4=18 、b[5]=240/5=48
 b[6]=(732-24-12)/6=116 、b[7]=2184/7=312 、b[8]=(6564-72-12)/8=810
 b[9]=(19680-24)/9=2184 、b[10]=(59052-240-12)/10=5880 、b[11]=177144/11=16104
 b[12]=(531444-696-72-24-12)/12=44220

のようになり、これを使えば、GS(n)=Σ[kはnの約数]b[k] と簡単に表せますね。


 GAI さんからのコメントです。(平成28年1月13日付け)

 b[n]=(a[n]-Σ[kはnより小さいnの約数]a[k])/n ですか?

 いずれにせよ、b[8]=(6564-72-12)/8=810 はおかしくないですか?
a[4]=2a[3]+3a[2]=2*24+3*12=84 のはずだから・・・


 らすかるさんからのコメントです。(平成28年1月13日付け)

 後で「/n」を追加したことで辻褄が合わなくなっていました。

 b[n]=(a[n]-Σ[kはnより小さいnの約数]b[k])/n は、

 b[n]=(a[n]-Σ[kはnより小さいnの約数]kb[k])/n

に訂正します。


 GAI さんからのコメントです。(平成28年1月13日付け)

 これからまさに、

b[1]=0 、b[2]=6 、b[3]=8 、b[4]=18 、b[5]=48 、b[6]=116 、・・・・・ 、b[12]=44220

が出現して行き、

 GS(1)=0 、GS(2)=b(1)+b(2)=6 、GS(3)=b(1)+b(3)=8 、GS(4)=b(1)+b(2)+b(4)=18
 GS(5)=b(1)+b(5)=48 、GS(6)=b(1)+b(2)+b(3)+b(6)=130 、・・・・・ 、
 GS(12)=b(1)+b(2)+b(3)+b(4)+b(6)+b(12)=44368

とピタリと一致しますね。

 らすかるさん、是非、{b[n]}の数列を整数列大辞典に登録して下さいよ。この列はとても利
用価値が大の意味を含んでいますよ。「A106366」、「A226493」にとても関連するので、この
リンクが含まれていたらすごく参考になります。こんな式で統一できるなんて意外でした。



                         投稿一覧に戻る