2016年7月13日 星期三

訓練數學感 106 ─ 變色龍

https://4rdp.blogspot.com/2016/07/106.html

圖片來自 維基百科
某人養了一群同種變色龍，能產生黃、綠、紅三種顏色，當兩隻不同色變色龍相遇在一起，就會變成第三色，如果同色在一起，則不會產生變化，例如，黃色跟綠色在一起兩隻都會變成紅色，黃色和黃色在一起，仍保持黃色。

現在有變色龍黃色 12 隻、綠色 13 隻、紅色 14 隻，請問有可能所有變色龍都變成同一色嗎？

我覺得這題很有趣，有興趣的朋友也可以寫個電腦程式遊戲模擬。

標籤：

23 則留言:

  1. flyingdusts2016年7月14日 下午4:16

    不能。
    如果全換成黃色，則紅色剩下1隻；
    如果全換成綠色，則紅色剩下2隻；
    如果全換成紅色，則綠色剩下1隻。
    1黃1綠1紅 可以換成 3黃 或 3綠 或 3紅，
    如果除了目標顔色外，只剩下3隻或3的倍數隻同色的變色龍，就能全變成同色，否則不行。

    回覆刪除
  2. tora2016年7月14日 晚上10:06

    我也覺得不能，要能全部變成同一顏色的話，必定要經過某兩種顏色的數量相同這個階段。
    但是照題意所說，當某兩個顏色隻數各為a和b時，a和b只能同時減1，或者其中一個減1另外一個加2。
    即是flyingdusts所說的任兩顏色的隻數最小變化為正負3。
    所以12,13,14這個組合沒有差3或3的倍數的組合，所以無法全部轉換成同一顏色。

    回覆刪除
    回覆
    1. Bridan2016年7月14日 晚上11:08

      兩位的分析非常正確。

      刪除
    2. flyingdusts2016年7月15日 中午12:13

      第一題的程式我運行了一上午，還沒運行到同色，看來讓這些特種變色龍變成同色的概率極低。

      刪除
    3. Bridan2016年7月15日 晚上10:55

      先把問題簡化，三色變色龍各兩隻，然後程式每輪將6隻變色龍，任意兩兩配對，看需平均幾輪才能發生全變成一色？簡單的說，計算需要幾輪才變成同色變色龍的期望值。

      刪除
    4. tora2016年7月19日 上午10:42

      後來想到應該加一個限制條件，如果A,B,C三色的變色龍隻數各為a,b,c，
      若要最後能夠全部變成C色的話，|a-b|=3(n-1),且c>=(n-1),n為正整數。例如若a與b差了9隻，但c只有2隻的話，
      還是無法將A與B色變色龍數量調整成一樣，所以無法全部變成C色。

      刪除
    5. Bridan2016年7月19日 晚上7:10

      關於這部分，因明日有重要會議要準備，等想清楚後再答覆。

      刪除
    6. Bridan2016年7月20日 晚上10:45

      我舉個例子，來看看你所說的情形，因為總數為奇數，所以剩一隻不配對
      A,B,C 三色分別為
      11,2,2
      7,4,4 A2+B2 A2+C2 其它 A+A
      3,12,0 A4+C4 其它 B+B
      0,9,6 A3+B3 其它 B+B
      6,6,3 B3+C3 其它 B+B
      0,0,15 A6+B6 其它 C+C
      因此 A+B+C 總數是三的倍數即可

      刪除
    7. tora2016年7月21日 凌晨12:00

      沒錯，我想通了，我的限制條件是畫蛇添足。
      如果C的數量不夠的話，可以A和B變成C去增加C的數量即可。
      所以原本(11,2,2)->(10,1,4)->(7,7,1)->(0,0,15)就好了。
      另外站長說的A+B+C總數是三的倍數即可似乎有點錯誤。
      因為原本的題目(12,13,14)加起來也是3的倍數但卻無法變成一色。
      應該還是要某2個顏色的差異數為3的倍數才可以。
      像(11,2,2)這個例子任2個顏色差都是3的倍數，所以最後可變成(15,0,0)或(0,15,0)或(0,0,15)。
      另外舉個例子(10,1,2)加起來不是3的倍數，但最後可以變成(0,0,13)，只是無法變成(13,0,0)或(0,13,0)。

      刪除
    8. tora2016年7月21日 凌晨12:28

      剛剛又想了一下，應該還是要加一個限制條件，考慮下列狀況：
      (A,B,C)=(20,2,1)，雖然A和B差了18是3的倍數，但是由於B和C的數量太少，所以
      (20,2,1)->(18,0,5)之後就無法繼續下去了。
      所以限制條件應該要改寫成如下：
      如果A,B,C三色的變色龍隻數各為a,b,c，
      若要最後能夠全部變成C色的話，|a-b|=3(n-1),且c+2*min(a,b)>=(n-1),n為正整數。
      一直推翻自己，可見思慮還是很不周密，哈哈。

      刪除
    9. Bridan2016年7月21日 晚上9:01

      嗯，你說的沒錯，總數三的倍數，這樣的條件不足以保證全變一色。

      不過你提的例子 (20,2,1) 是有機會全變為 (0,0,23)，方法如下
      (20,2,1) > (18,0,5) > (14,8,1) > (12,6,5) > (10,10,3) > (0,0,23)

      看來全變一色的條件應是，任兩色的差值為三的倍數，就可以轉換成第三色
      因此(a,b,c)，若 abc 之間沒有三的倍數差，則都無法全部轉換成一色，若 ab 間有三的倍數差，則可全變成 c，
      若 c 與 a 有三倍數差關係，那 c 與 b 也會有三倍數差關係，那麼 abc 三者都有機會變成一色。

      刪除
    10. Bridan2016年7月21日 晚上9:13

      我覺得推翻自己是一種進步的表現，通常我們會自己假想某種理論來描述事物，當用這方法論述不成立時，就表示需要改進，蠻像古代從 天動學說 變到 地動學說 一樣，逐步進化找出正確的方法，很高興我們可以這樣討論把一些問題想法釐清。

      刪除
    11. tora2016年7月21日 晚上10:38

      原來如此，其實可以透過C變成B再變成C這個方法來縮小差距的。
      所以只要有任兩色隻數差距是3的倍數，就可以變成第三色了。
      讚！

      刪除
    12. Bridan2016年7月21日 晚上11:35

      加分題二

      如果從三色得到的新結論，想想看能運用到四色嗎？例如 (12,13,14,16) AD 之間為四的倍數，就能變成單一某色嗎？還是 (12,13,16,14) 才行?

      刪除
    13. tora2016年7月21日 晚上11:50

      但4色的時候變化規則是甚麼呢？是要三隻不同色才會變成第四色嗎？

      刪除
    14. Bridan2016年7月22日 上午8:42

      首先，依原變色條件，知道2c+4n可以全變為d，想進一步思考，遇到總數為奇數情形，有無機會全變一色？

      第二，除了2c+4n這樣情況外，有無類似三色那樣，以過渡轉換再變成一色？我舉個例子 (3,3,0,0)，它看似不符你之前分析情況，個人覺得應該有機會全變成一色。

      第三，如果變色規則改成，只有三隻在一起才變色，三隻不同色時，全變第四色，當三隻有兩隻同色，第三隻就變跟兩隻同色。其餘情形不變色。

      第四，如果兩隻變色又加三隻變色規則，算了，情況變得太複雜，我想這樣搞下去，可以寫個論文專題研究。

      刪除
  3. Bridan2016年7月14日 晚上11:06

    老師厲害，一次完整答覆這題的解答。
    加分題，假設變色龍可變四色，用ABCD編號，A+B=C，B+D=A，C+D=B，A+C=D，其它情形顏色不變。
    請問 A 有12隻，B 有13隻，C 有14隻，D 有15隻，最後會變成同色嗎？

    回覆刪除
  4. tora2016年7月14日 晚上11:40

    我猜還是不能，
    第一步C和D變成B->A、B、C、D的隻數變成12、15、13、14；
    第二步B和D變成A->A、B、C、D的隻數變成14、14、14、14；
    但是不管是A+B=C配上C+D=B；或是A+C=D配上B+D=A，
    剩下來的B和C或是A和D都沒辦法再變到另一色了。
    不知這樣答案是否正確？還是其實有其他解法？

    回覆刪除
    回覆
    1. Bridan2016年7月15日 晚上10:46

      嗯，這是不能的，不過想知道，現在變色條件不更動下，甚麼樣的變色龍數量可以有機會都變同一色？

      刪除
    2. tora2016年7月16日 凌晨12:11

      假設最後全部變成A色的話，前一階段首先需要B和D達到相同數量，那B是由C和D變化而來；D則是由A和C變化而來，
      所以最簡單的數量是A1B0C2D1->B2D2->A4，
      一般解則是當B為b隻時，D為b+n隻，A為n隻，C為2n隻，最後會變成A有2b+4n隻，b為0或正整數，n為正整數。
      依此類推
      若最後要全部變成B色，
      一般解是當D為d隻時，C為d+n隻，A為2n隻，B為n隻，最後會變成B有2d+4n隻，d為0或正整數，n為正整數。
      若最後要全部變成C色，
      一般解是當A為a隻時，B為a+n隻，D為2n隻，C為n隻，最後會變成C有2a+4n隻，a為0或正整數，n為正整數。
      若最後要全部變成D色，
      一般解是當C為c隻時，A為c+n隻，B為2n隻，D為n隻，最後會變成D有2c+4n隻，c為0或正整數，n為正整數。

      刪除
    3. Bridan2016年7月16日 上午8:52

      tora 真不簡單，短短一小時左右就立即想出這個通解，你的內容，我是細細品味許久才明白想法，正解無誤。

      刪除
    4. tora2016年7月18日 下午1:27

      站長過獎了，其實7/14站長第一次提問加分題時就有大概想了一下，7/15問的時候也是有點運氣好才能想出一般解。
      說來慚愧，站長的數學難題有好幾題我到現在都還是想不出來，哈，再繼續努力。

      刪除
    5. Bridan2016年7月18日 下午6:38

      研發人員每天都會遭遇各種奇奇怪怪的工程問題，能不能解，會不會解另一回事，不過也練就一身假想狀況的能力，因此通常出完基本題後，若有想到一些有趣的狀況，就會適時再加入。
      你客氣了，很多題目，我也是要想很久很久，不管會不會解，有在思考總是比較好，還好現在的身分不是學生，沒有限時考試，有充裕的時間解題，大家一起努力。

      刪除

訂閱： 張貼留言 (Atom)