2016年7月13日 星期三

訓練數學感 106 ─ 變色龍

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

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

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

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

23 則留言:

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

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

    回覆刪除
    回覆
    1. 兩位的分析非常正確。

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

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

      刪除
    4. 後來想到應該加一個限制條件,如果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. 關於這部分,因明日有重要會議要準備,等想清楚後再答覆。

      刪除
    6. 我舉個例子,來看看你所說的情形,因為總數為奇數,所以剩一隻不配對
      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. 沒錯,我想通了,我的限制條件是畫蛇添足。
      如果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. 剛剛又想了一下,應該還是要加一個限制條件,考慮下列狀況:
      (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. 嗯,你說的沒錯,總數三的倍數,這樣的條件不足以保證全變一色。

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

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

      刪除
    12. 加分題二

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

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

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

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

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

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

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

    回覆刪除
  4. 我猜還是不能,
    第一步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. 嗯,這是不能的,不過想知道,現在變色條件不更動下,甚麼樣的變色龍數量可以有機會都變同一色?

      刪除
    2. 假設最後全部變成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. tora 真不簡單,短短一小時左右就立即想出這個通解,你的內容,我是細細品味許久才明白想法,正解無誤。

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

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

      刪除