PUZZLEUP 2015

newkid

lugionline 发表于 2015-11-13 16:39
本来就是14么，但是你人脑能确定这个就是正确解吗？万一是13呢

能不能证明N递增时至少要多画两个？或者是N+2时至少要多画四个。

newkid

lugionline 发表于 2015-11-13 15:24
还是用M，求204个变量的0-1规划，及其缓慢，基本到机器的极限了，但是好歹能出来

用圆圈表示正方形位置 ...

你这个答案不如我的优美。

lugionline

newkid 发表于 2015-11-14 07:56
你这个答案不如我的优美。

是啊，要能证明就好了，能找到现在这个问题和下面这个问题的联系没有

https://en.wikipedia.org/wiki/Thinking_outside_the_box


K = 5的时候用你的方法是怎么画的？

〇〇

手机解锁图案?有时候不对称人类更难想

〇〇

392楼是左下右上对角线对称

newkid

奇数的要从外层往里“削”，每削掉一圈（N-2）用掉四个正方形, 直到中心点为止：

1111*
1111*
1111*
1111*
*****

*2222
*2222
*2222
*2222
*****

*****
3333*
3333*
3333*
3333*

*****
*4444
*4444
*4444
*4444

555**
555**
555**
*****
*****

**666
**666
**666
*****
*****

*****
*****
777**
777**
777**

*****
*****
**888
**888
**888

lugionline

newkid 发表于 2015-11-14 23:08
奇数的要从外层往里“削”，每削掉一圈（N-2）用掉四个正方形, 直到中心点为止：

1111*

哦哟，itpub出错了，输了N遍密码都不行，itpub的账号又不值钱

下面就来尝试证明最小数不小于 2 * n - 2 时

事实：
        1：一个 n * n 格点在四边共有 4 个角和 4 * (n - 1) 个T形 (T形只看那个 | 线)
        2：每个正方形最多可以覆盖 4 个角或者 1 个角和 2 个T形

要覆盖这些 n * n 格点形状，至少也要覆盖这四个角和所有T形，分两种情况：

1：没有一个方块覆盖了4个角，这时
        2 * k >= 4 * (n - 1)  并且 k >= 4(至少要有4个正方形覆盖那4个角)
得出        k >= 2 * n - 2，并且 k >= 4

2：或者有一个方块覆盖了4个角，剩下的正方形覆盖 4 * (n - 1) 个T形
        2 * (k - 1) >= 4 * (n - 1)
得出        k >= 2 * n - 1

命题得证

剩下的就交给你了，来证明你的方法可以覆盖所有线段吧，这个更难点

newkid

lugionline 发表于 2015-11-15 08:36
哦哟，itpub出错了，输了N遍密码都不行，itpub的账号又不值钱

下面就来尝试证明最小数不小于 2 * n ...

实在太经典了，没想到从外围突破，我必须得送你一个章！
至于我那个方法，覆盖所有线段不是很直观的吗？因为逐层推进，就没有遗漏的。如果花点时间是很容易写出证明的。

lugionline

那就来个玉兔吧，我要会动的

〇〇

lugionline 发表于 2015-11-15 12:45
那就来个玉兔吧，我要会动的

m能解决n*m长方形的问题吗