【分享】想要和朋友們一樣

[曾阿牛 10]

談到分享數學　在下最想推薦的就是這樣的一個題目　請大家一起玩玩

印象中　深藍還沒出現過這樣的題目.. :P

某一年秋天　　有12 名小矮人搬到妙妙島上住 ( 妙妙島上本來是沒有小矮人的 )

他們各自選了地點　蓋起自己的房子　並將房子的門 漆成紅色或藍色

隔年一月　1號小矮人去拜訪他所有住在妙妙島上的小矮人朋友 並在當月回到家

二月　2號小矮人去拜訪他所有住在妙妙島上的小矮人朋友 並在當月回到家

三月　3號小矮人去拜訪他所有住在妙妙島上的小矮人朋友 並在當月回到家

幾月　就由幾號小矮人去拜訪他所有住在妙妙島上的小矮人朋友 並在當月回到家

這樣的拜訪行為 一直不斷的一年又一年地持續下去

當每個小矮人拜訪完朋友 且回到家後

小矮人會回想他所有的朋友的家門上 哪種顏色比較多 就會將自己的門 漆成那種顏色

當然 如果家門本來就是那種顏色　就不用漆

如果 所有朋友的家門上的顏色 紅與藍各佔一半的比例的話 也不用漆

問題來了：請說明　經過一段時間後 所有的小矮人 都將不用改漆自家門的顏色

( ps. 朋友關係是相互的 譬如說 如果1號是3號的朋友 那3號也會是1號的朋友 )

[arthurduh1 10]

定義「志同道合數」：

對於任一個矮人，

他門上所漆的顏色 若恰與他好友中的n個一樣，

則稱此矮人的「志同道合數」為n。

我們現在考慮「志同道合總數」，

也就是把所有矮人的志同道合數加總。

每個月某位矮人回家、把自己門上的漆的顏色決定完以後，

只有兩種可能：

(i)志同道合總數不變，

也就是這位矮人門上漆的顏色不變，

每位矮人的志同道合數也都不會改變。

(ii)志同道合總數變大。

當這位矮人把門上漆的顏色換掉時，

自己的志同道合數必定增加。(知道為什麼吧？！)

而這位矮人的所有朋友的志同道合數也會有所增減。 (因為朋友關係是相互的)

假設門上漆色由A換成B，

那麼門上漆色為A的朋友志同道合數會減一，

而門上漆色為B的朋友志同道合數則會加一。

從題目所述得知 門上漆色為A的朋友較少，故志同道合總數仍然會增加！

注意志同道合總數不可能減少，

又志同道合總數最高只可能為12*11/2=66

且志同道合總數一定是整數，

故在一段時間後志同道合總數必定會停止增加，

維持不變。

這就代表矮人們都不會換漆的顏色了！(因為換漆色=>志同道合總數增加)

我覺得這個題目挺有趣的！

花了好些時間才想到這個證明。

[howt 10]

將12名小矮人的房子視為12個點，各自著色

朋友關係則視為點與點之間的連線(沒有朋友的小矮人也不會改變顏色)

若兩點同色則連黑線，兩點異色則連白線

那麼根據題目的要求可知

若某一點對外連線數量滿足黑≥白，則此點的黑白線不變色

若某一點對外連線數量滿足黑<白，則此點的黑白兩線變色(結果造成黑>白)

而一開始給定的點顏色，可決定所有線一開始的顏色

根據以上可知白線數量總是在減少或不變(不變表示不需改點顏色)

但白線不可能無止盡減少，證畢(這跟arthurduh1 大大的證法其實是一樣的)

同理可證，若有N個小矮人，K種顏色，結果也是一樣的

(也就是說，如果一群沒有主見而只聽從較多部份朋友意見的人生活在一起，

最後會變成一種穩定狀態囉!? XD )

[曾阿牛 10]

arthurduh1 和 howt 大大真的很棒呀　

在解決這個問題的過程中　arthurduh1 引進了「志同道合數」這樣的輔助工具

有了這工具　問題就變得清晰了　

howt 大大　將這題換成圖形　再去考慮邊(edge)的顏色　這與「志同道合數」的觀點是契合的

最後再考慮到　有限的自然數的子集有界　這是解題的第二個關鍵

(第一個關鍵就是引進輔助工具　或是將問題轉化成圖形介面)

個人很喜歡這題目　　只可惜自己當初沒解出來:E

[arthurduh1 10]

我覺得howt大的解法省事多了！

我的還要個別討論關係兩邊的朋友，

換成討論關係本身就可以少很多敘述了！