Re: [理工] [離散] 鴿籠 四角落同色
※ 引述《mqazz1 (無法顯示)》之銘言:
: a 3*7 rectangle is divided into 21 squares each of which is colored red or
: black
: prove that the board contains a nontrivial rectangle(not 1*k or k*1)
: whose four corner squares are all black or all red
: 謝謝
首先 因為每行都有3格 而我們只有紅黑兩色
所以必然每行都會出現兩個相同顏色 (假設是黑色 且出現在j,k列 j,k: 1~3 )
再來我們要找到另外一行 在j,k列也是黑色的
這樣這四個角落就會出現相同顏色
(i) 如果有兩行一樣 就結束了
(ii) 如果七行皆相異
假設另外一行不存在
則 其他6行的 j,k項都不可同時為黑 這樣只會有 2*2*1 = 4種可能
4 < 6 --> <--
所以必然有另外一行的j,k項也是黑
ps.解答放在學校 沒辦法驗証, 有錯請指正~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.184.30
→
12/29 02:55, , 1F
12/29 02:55, 1F
→
12/29 02:56, , 2F
12/29 02:56, 2F