作者id010406 (no id)
看板Math
標題Re: [其他] 看起來簡單卻不知怎麼證的著色問題
時間Sat Jun 23 12:26:27 2012
※ 引述《LimSinE (r=e^theta)》之銘言：
: 設m = ad+r, 0<=r<d
: 則用此方法塗的格字數為 N=a^2d + 2ar = ma + ra
: 但是事實上我們可以在棋盤上放入不重疊的N個長條
: 放法就是先橫放ma個長條，剩下的rxm 再放直的ra個長條
: 因此至少要塗N格
是的 有一個證明法的確是這樣做 不過L大你的式子有點錯
用 m=5 d=3 代入 得 N=8
正確的式子是當 m= r或-r (mod d)時 (r<=d/2)
N= (m^2-r^2)/d
m=r (mod d)時的排法就是 L大所說的
但 m=-r(mod d)時 要像 "風車" 一樣排
但是這個證明很不直接 難道一定要這麼做嗎?
會不會有其他更直接的證明?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.104.7
※ 編輯: id010406 來自: 180.177.104.7 (06/23 12:28)
推 XII :你也可以把方格塗成風車狀 06/23 22:53
→ XII :這兩種好像不好合併一起看.. 06/23 22:57
是的 分兩種情形討論 兩種排法又不一樣
好像沒辦法簡化成一種
可是這個著色法直覺上就是對的 想法就是用最有效率的方式著色這麼簡單
甚至對任意 m*n m,n>=d 也應該是對的 但是 m n不同時要討論的情況又變多了
推 LimSinE :怎麼叫人家證明錯誤的結論 06/24 01:04
推 LimSinE :喔不是::: 06/24 01:08
→ LimSinE :可是你都已經會了 06/24 01:08
※ 編輯: id010406 來自: 180.177.104.7 (06/24 12:06)