[其他] 看起來簡單卻不知怎麼證的著色問題

看板Math作者id010406 (no id)時間13年前 (2012/06/21 18:43)推噓1(1推 0噓 3→)

留言4則, 2人參與討論串1/3 (看更多)

給定一個 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)

推

LPH66

06/22 02:13, , 1^F

06/22 02:13, 1^F

→

LPH66

06/22 02:13, , 2^F

06/22 02:13, 2^F

→

id010406

06/22 10:21, , 3^F

06/22 10:21, 3^F