[問題] 不玩四人行的潔牙竹籤

[yjd (origin of love)]

(硬是要掰...)
                                                       ┌─┬─┬─┬─┐
有40根牙籤排成如右圖的方格型                           │  │  │  │  │
                                                       ├─┼─┼─┼─┤
請問要拿掉多少根牙籤 才能確保不會有任何正方形形成      │  │  │  │  │
                                                       ├─┼─┼─┼─┤
拿掉的牙籤數也是能越少越好                             │  │  │  │  │
                                                       ├─┼─┼─┼─┤
請注意 此圖含16個1x1 9個2x2 4個3x3 及 1個4x4 的正方形  │  │  │  │  │
                                                       └─┴─┴─┴─┘
如果上題覺得還不過癮

可以試著想想看 如果是個5x5的方格型呢 (共60根牙籤)

猜猜看吧~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 125.225.85.39
推 pphhxx:只想的到拿掉10根= =
推 puzzlez:這個好經典，不容易回答呢^^我也來想想（答案忘了）.....
推 isnoneval:┌┐┌┬┐  九根啦，不能再少了，很好證
→ isnoneval:│├┤││
→ isnoneval:├┤│├┤
→ isnoneval:│├┴┤│
→ isnoneval:└┴─┴┘
推 puzzlez:樓上是高手0.0
推 isnoneval:偶數的通解是 n^2/2 + 1，構造用上一個偶數的解去包一圈
→ isnoneval:證法是一樣的，奇數有點難搞，我懷疑要 (n^2+5)/2，
→ isnoneval:構造用上一個偶數的解去多包半圈