Re: [請益] 一些邏輯問題
※ 引述《sy20168 (Dennis)》之銘言：
: Q1: 有2009 片玻璃片, 每片塗有紅藍綠三色之一. 進行下面的操作:
: 每次取出兩片不同色的玻璃片, 擦淨其上塗色, 然後塗上第三種顏色.
: 試證明: 無論開始時紅藍綠玻璃片各有多少片, 都可以經過有限次的操作, 而使所有玻璃片
: 都變成同一顏色.
令三種顏色為r b g
先觀察如果給一個r 一個b可以合成兩個g 在用兩個b去合成四個r
所以總計b少了三個 g沒有多沒有少 r多了三個
也就是說經過這樣的設計對於所有的個數為3的倍數都可以完全的換掉成為另一個顏色
又因為 2009 = 2 mod 3
對於任意個數的三種不同顏色必然存在方法使得有一種顏色是3的倍數
(容我囉說一下 對於分成三類如果三類都不是三的倍數 那麼除以三的餘數可能為
(2,2,2),(2,2,1),(2,1,1),(1,1,1) 而其中唯一滿足總和mod 3為2的僅有(2,2,1)
所以我們只要把其中一個2和1各取出一個合併就會得到新的餘數組合為(1,1,0)
所以就出現了一個是三的倍數)
所以用上述的設計方式可以把三種顏色變成只有兩種顏色
若是這剩下的兩種顏色有一個顏色是三的倍數
那麼馬上就可以得知有一個有限的方式可以把這兩個顏色變成一種顏色
假若這兩種顏色都是3的倍數多1 那麼我們可以用以下的設計
這兩個顏色必定有一個比較多一個比較少(因為2009是奇數)假定這兩個顏色個數各為m n
且m > n
所以我們用一對一的方式取就可以得到第三種顏色直到原先的顏色中某一個顏色取為止
因此最後會只剩下兩種顏色 其中個數個別為 m-n 和 2*n
因為 m = 1 mod 3 和 n = 1 mod 3 => m - n = 0 mod 3
所以就會有一個顏色是三的倍數再用一開始的設計那麼就可以指得到一種顏色
因此對於任意個數總和是2009的三種顏色 存在一種有限的方法
將顏色變成同一種顏色 //
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.134.25.40
※ 編輯: simonjen 來自: 220.134.25.40 (06/10 08:34)
※ 編輯: simonjen 來自: 220.134.25.40 (06/10 08:40)
討論串 (同標題文章)