引用:

原帖由 chu1976 於 2008-4-13 01:32 PM 發表
一個圓被半徑分割成n等份用k種顏色來塗,每一區域塗一色,相鄰異色,顏色可以重複,不一定k種顏色全用,求證塗法為(k-1)(-1)^n+(k-1)^n
[解]設用k種顏色塗n個區域,相鄰異色塗法有a_n,則a_n+a_n-1=k(k-1)^n-1
紅色部分是如何來的呢?麻煩知道老師能分享一下,謝謝!

由第 1 區開始圖顏色，有 k 種顏色可以用，

第 2 區必須跟第 1 區異色，所以有 k-1 種顏色可以用，

第 3 區必須跟第 2 區異色，所以有 k-1 種顏色可以用，
‧
‧
‧
第 n-1 區必須跟第 n-2 區異色，所以有 k-1 種顏色可以用，

第 n 區必須跟第 n-1 區異色，所以有 k-1 種顏色可以用。

所以以上共有 k(k-1)^{n-1} 種塗色法。

可是這個數據並不是 a_n ，因為第 n 區可能跟第 1 區同色或是異色，

所以這個數據包含有 n 個區域相鄰塗異色，以及 n-1 個區域相鄰塗異色(第 n 區與第 1 區同色)的情況，

所以這個數據是 a_n + a_{n-1}，故 a_n + a_{n-1} = k(k-1)^{n-1} 　for all n>=3，

再加上遞迴關係式的初始條件 a_2 = k(k-1) 與 a_3=k(k-1)(k-2) ，可以求出 a_n (以 n 及 k 表示)。

註：a_1 + a_2 並不會滿足上面的遞迴關係式，但是 a_2 + a_3, a_3 + a_4, .... 之後才會滿足上面的遞迴條件。

　　感謝 ptt 的 moun9 網友提醒。2011/04/10





額外的補充：這個題目也可以改成 k 個球員要互相傳籃球的問題，教練隨便選一球員，由該球員開始傳球給其他人，此 k 位球員互傳了 n+1 次之後，又回到剛開始第一個傳出去的球員的手上，求方法數。做法跟上面一模一樣。


解題的其它部分，在全教會的 thepiano 老師有寫了，
討論串：h ttp://forum.nta.org.tw/examservice/showthread.php?t=42668　連結已失效












另外，其它相關資料，

　　1. https://math.pro/db/viewthread.php?tid=741&;extra=#pid1296

　　2. 陽明高中數學科　羅驥韡老師的《舊的圖色文題，新的計算方法》

　　　http://www.scribd.com/full/14174890?access_key=key-sqcrk2qz34pt63qgyvr

討論數學的感覺很好，

謝謝。

為什麼你會這樣覺得呢?

k(k-1)^{n-1}  並不是 a_n 喔～

你可以先想看看 k(k-1)^{n-1} 是怎麼來的～

就會發現，

因為在塗第 n 塊的時候，並沒有特別避開說要與第 1 塊不同，

而 a_n 的定義有要求第 n 塊跟第一塊要異色，

也因此 k(k-1)^{n-1} 比 a_n 多，

而多多少呢？多出來的數目就是 a_{n-1}

原因就是～當初在算 k(k-1)^{n-1} 時，

有可能會遇到第 n 塊跟第一塊相同的情況，

如果第 n 塊跟第 1 塊相同，就變成 n-1 格相鄰都途異色的區域囉！




題意[相鄰異色]，是限制在 a_n 上面，所以 k(k-1)^{n-1}  並不是 a_n，

k(k-1)^{n-1} 比 a_n 還要多！