推 LPH66 :用比例? 著色格子只佔全格子的 1/d 這樣... 06/22 02:13
→ LPH66 :(不過當 m 不是 d 的倍數時可能要討論一下) 06/22 02:13
→ id010406 :是的這題難的地方就是m不是d的倍數 會不會是什麼整數 06/22 10:21
→ id010406 :論的難題? 06/22 10:21
給定一個 m*m 的棋盤 和一條 d*1的長條 ( m >= d)
現在我們要在棋盤的某些格子上著色
使得這長條任意覆蓋盤上 d格時
都會蓋到至少一個著色格子
有個著色法是 假設棋盤左下角是 (1,1)
那麼著色 (d,1) (d-1,2) (d-2,3) .....
(2d,1) (2d-1,2) (2d-2,3) .....
(3d,1) (3d-1,2) (3d-2,3) .....
.......
到 ld>m時 開始著色
(m,ld-m+1) (m-1,ld-m+2) (m-2,ld-m+3)....
(m,ld+d-m+1) (m-1, ld+d-m+2) (m-2, ld+d-m+3)....
.......
也就是以斜對角方式著色
"這種著色法所著色的格子數是所有著色法中最少的"
請問這要怎麼證明?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.104.7
※ 編輯: id010406 來自: 180.177.104.7 (06/21 18:54)
※ 編輯: id010406 來自: 180.177.104.7 (06/21 21:15)