Re: [其他] 看起來簡單卻不知怎麼證的著色問題
設m = ad+r, 0<=r<d
則用此方法塗的格字數為 N=a^2d + 2ar = ma + ra
但是事實上我們可以在棋盤上放入不重疊的N個長條
放法就是先橫放ma個長條，剩下的rxm 再放直的ra個長條
因此至少要塗N格
※ 引述《id010406 (no id)》之銘言：
: 給定一個 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)....
: .......
: 也就是以斜對角方式著色
: "這種著色法所著色的格子數是所有著色法中最少的"
: 請問這要怎麼證明?
--
r=e^theta
即使有改變，我始終如一。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.2.140
討論串 (同標題文章)