13 12
發新話題
打印

排列組合題目,圓被半徑分成n個區域,相鄰塗異色

推到噗浪
推到臉書

排列組合題目,圓被半徑分成n個區域,相鄰塗異色

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

TOP

引用:
原帖由 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 老師有寫了,
討論串:http://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

TOP

經由您的解釋我比較容易看得懂!
感謝您肯花時間來解這一題唷!

TOP

討論數學的感覺很好,

謝謝。

TOP

不好意思關於此句[因為第 n 區可能跟第 1 區同色或是異色]我是覺得應該是第 n-1 區可能跟第 1 區同色或是異色

TOP

為什麼你會這樣覺得呢?

TOP

因為第n區與第1區不就有可能同色
這樣子不符合題意[相鄰異色]!
若有觀念錯誤麻煩指正

TOP

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 還要多!

TOP

感謝你的解惑,讓我更清楚囉!

TOP

補充資料
http://forum.nta.org.tw/examservice/showthread.php?t=21240
使用\( a_{n-1}+a_n=k \cdot (k-1)^{n-1} \)解題
中一中 賴老師工作室
http://jflai.blogspot.com/2007/12/blog-post_7984.html

使用\( a_{n+1}=(k-2)a_n+(k-1)a_{n-1} \)解題
排列組合之塗色問題 台北縣立三民高中 楊建泰老師
101.4.10補充
連結已失效,請下載附加檔案
h ttp://blog.cshs.ntct.edu.tw/math/%e5%b0%88%e9%a1%8c%e7%a0%94%e7%a9%b6/

2011.6.11補充
用紅、黑、黃3種顏色塗下列9個不同的區域如下圖,規定每區需塗一色,顏色可以重複使用,但相鄰部分不得塗同色,則共有幾種不同的塗法?
(100玉井工商,https://math.pro/db/thread-1131-1-1.html)

100.9.29補充
以O為圓心的圓上有n個相異點,依序為\( A_1 \)、\( A_2 \)、\( A_3 \)、…、\( A_n \),此n個點將圓分割為\( A_1 O A_2 \)、\( A_2 O A_3 \)、\( A_3 O A_4 \)、…、\( A_n O A_1 \)等n個扇形區域。在m種不同顏色的色筆中任選一種顏色塗其中任一扇形區域,每區域一色,相鄰區域不同色,全部的方法數有\( S(n,m) \),若\( S(n+2,m)=p S(n+1,m)+k S(n,m) \),求\( p-k= \)?
(98彰化女中,https://math.pro/db/viewthread.php?tid=741&page=1#pid1296)

101.4.30補充
阿花參加著色比賽,主辦單位提供八種色筆,圖形為五格的圓形轉盤(如右圖,可以旋轉但不可以翻轉),若規定顏色可以重複使用但是同色不可以相鄰,則阿花有種著色方式?
(RA628.swf)

投擲一顆公正六面骰子n次(各面為1,2,3,4,5,6點),依序紀錄點數為\( x_1,x_2,x_3,…,x_n \),設滿足\( (x_1-x_2)(x_2-x_3)(x_3-x_4)…(x_{n-1}-x_n)(x_n-x_1)\ne 0 \)的機率為\( P_n \)。求\( P_n+6 \cdot P_{n+1} \)之值(以n表之)
(101台中一中,感謝Ellipse提供同色不相鄰的解法)
https://math.pro/db/viewthread.php?tid=1334&page=1#pid5252

101.8.2補充
A-BCD為空間中的一正四面體,O為其中心,質點P可以在A、B、C、D、O中自由移動,而且規定從其中一點移動至另外一點稱為一步,若定義質點P從O點出發,最後又回到O點共走了n步的方法數為\( a_n \),\( n \ge 2 \)(例如\( a_2=4 \) ),則\( a_{10}= \)
(101文華高中代理,https://math.pro/db/thread-1462-1-1.html)
weiye提供的另解,https://math.pro/db/viewthread.php?tid=1462&page=2#pid7008

[ 本帖最後由 bugmens 於 2012-8-2 11:54 AM 編輯 ]

附件

2010.2.21.rar (943.39 KB)

2010-2-21 12:37, 下載次數: 3052

TOP

 13 12
發新話題