s****i
发帖数: 197 | 1 Given a n×n checkerboard with checkers on it, one can put a new checker in
an empty square if at least two of it's neighbor are occupied by checker(
here only horizontal and vertical).
注:也就是说只有这样的才可以放一个新的checker上去:
* *
_ => *
* *
或者
* *
_* => **
这里*代表已经有的checker, _代表空格
Apply this rule until no more checker can be placed. If we start with n-1
checkers (注如果是start with n个的话 都放对角线上就可以了都occupy了) is it
possible all of n^2 square be occupied in the end? If not prove your result.
想了半天毫无头绪啊 而且据说最简单的答案只需要一句话就可以了 头痛啊啊 |
e********5
发帖数: 422 | 2 新放入的棋子一定和原来存在的要么在一行要么在一列 如果某一格的同一行和同一列
初始时候一个棋子都没有 那么不管怎么放都无法把这一格填满 |
H*****1
发帖数: 4815 | 3 这个解释是不对的
*_*
___
*_*
第二行和第二列空的，但可以被填满
【在 e********5 的大作中提到】
: 新放入的棋子一定和原来存在的要么在一行要么在一列 如果某一格的同一行和同一列
: 初始时候一个棋子都没有 那么不管怎么放都无法把这一格填满
|
H*****1
发帖数: 4815 | 4 如果空的列或者行在边界处，是不可能被填满的
如果在中间，则问题被分割成四个单独的小问题，只有四块都能独立填满，中间空的行
和列才能被填满，但接下去怎么证明就不知道了
【在 H*****1 的大作中提到】
: 这个解释是不对的
: *_*
: ___
: *_*
: 第二行和第二列空的，但可以被填满
|
d****o
发帖数: 1055 | 5 这个最开始的n-1个checker，是不是可以自己随便放？
还是任意的n-1个checker?
in
【在 s****i 的大作中提到】
: Given a n×n checkerboard with checkers on it, one can put a new checker in
: an empty square if at least two of it's neighbor are occupied by checker(
: here only horizontal and vertical).
: 注:也就是说只有这样的才可以放一个新的checker上去:
: * *
: _ => *
: * *
: 或者
: * *
: _* => **
|
d****o
发帖数: 1055 | 6 显然不能。
当n=2的时候， 如果start with 1个checker,肯定不行。
当n=3的时候，你画画就知道了~~
in
【在 s****i 的大作中提到】
: Given a n×n checkerboard with checkers on it, one can put a new checker in
: an empty square if at least two of it's neighbor are occupied by checker(
: here only horizontal and vertical).
: 注:也就是说只有这样的才可以放一个新的checker上去:
: * *
: _ => *
: * *
: 或者
: * *
: _* => **
|
c****p
发帖数: 6474 | 7 如果n-1个可以填满n*n的话，
那么初始只放一个checker就可以填满任意大的平面。
这与n=1和n=2时的情况相悖。
所以原命题是假的
in
【在 s****i 的大作中提到】
: Given a n×n checkerboard with checkers on it, one can put a new checker in
: an empty square if at least two of it's neighbor are occupied by checker(
: here only horizontal and vertical).
: 注:也就是说只有这样的才可以放一个新的checker上去:
: * *
: _ => *
: * *
: 或者
: * *
: _* => **
|
e********5
发帖数: 422 | 8 不懂 能再解释一下么
【在 c****p 的大作中提到】
: 如果n-1个可以填满n*n的话，
: 那么初始只放一个checker就可以填满任意大的平面。
: 这与n=1和n=2时的情况相悖。
: 所以原命题是假的
:
: in
|
e********5
发帖数: 422 | 9 肯定不行的 但可他要的是证明 总不能跟面试管说你画画就知道吧
【在 d****o 的大作中提到】
: 显然不能。
: 当n=2的时候， 如果start with 1个checker,肯定不行。
: 当n=3的时候，你画画就知道了~~
:
: in
|
s******s
发帖数: 31 | 10 每放一个checker,checker和empty space的总的接触的edge数都是不变的。n-1个
checker，最多有4(n-1)的edge接触empty space，最大的总面积是(n-1)^2，所以不可
能覆盖n^2的checkerboard。 |
|
|
e********5
发帖数: 422 | 11 这个解释也不对 因为填空不止一轮 与初始棋子都不相邻的空 也可能被填上的
【在 s******s 的大作中提到】
: 每放一个checker,checker和empty space的总的接触的edge数都是不变的。n-1个
: checker，最多有4(n-1)的edge接触empty space，最大的总面积是(n-1)^2，所以不可
: 能覆盖n^2的checkerboard。
|
g*********e
发帖数: 14401 | 12 我来证明
用递归
N=2,3的时候不能
假设N=n的时候不能，则当N=n+1时
1...n, n+1
.
.
n...n, n+1
n+1,n+1,...
已知左上n*n个不能用n-1个初始checker完成全部填满，ketuide
若第n个check仍然放在n*n里面，则右边和下边都无法填满
若第n个放在右边或下边任意一条边上（不包括(n+1,n+1)这个点） 则另外一条边
任何一个空格都无法填上
若第n个放在(n+1,n+1)上，可以证明只有当第n行 第n列（1.。。n)都已经填满的
情况下才能把n+1行、列填满。（这个有点拗口，但仔细想想是可以证的） 而若第n行
第n列都已经满了，则左上n*n也可填满，与假设不符。
综上，得证。 |
g*********e
发帖数: 14401 | 13
不对,please disregard
【在 g*********e 的大作中提到】
: 我来证明
: 用递归
: N=2,3的时候不能
: 假设N=n的时候不能，则当N=n+1时
: 1...n, n+1
: .
: .
: n...n, n+1
: n+1,n+1,...
: 已知左上n*n个不能用n-1个初始checker完成全部填满，ketuide
|
s******s
发帖数: 31 | 14 我应该再严密些，n个checker和empty space最多有4n个edge接触。每加1个checker与
empty space接触的edge数不会增加。至于有几轮没有关系。你自己用好好想一下。
【在 e********5 的大作中提到】
: 这个解释也不对 因为填空不止一轮 与初始棋子都不相邻的空 也可能被填上的
|
g*********e
发帖数: 14401 | 15
仔细想想 应该是可以的
【在 g*********e 的大作中提到】
: 我来证明
: 用递归
: N=2,3的时候不能
: 假设N=n的时候不能，则当N=n+1时
: 1...n, n+1
: .
: .
: n...n, n+1
: n+1,n+1,...
: 已知左上n*n个不能用n-1个初始checker完成全部填满，ketuide
|
d****o
发帖数: 1055 | 16 当证明一个问题不行的时候，一个反例就可以了。
证明行的时候，才需要证明全部情况。
【在 e********5 的大作中提到】
: 肯定不行的 但可他要的是证明 总不能跟面试管说你画画就知道吧
|
k*****y
发帖数: 744 | 17 用归纳法证明填满一个m x n的矩形至少需要 (m+n)/2 个checker?
in
【在 s****i 的大作中提到】
: Given a n×n checkerboard with checkers on it, one can put a new checker in
: an empty square if at least two of it's neighbor are occupied by checker(
: here only horizontal and vertical).
: 注:也就是说只有这样的才可以放一个新的checker上去:
: * *
: _ => *
: * *
: 或者
: * *
: _* => **
|
e********5
发帖数: 422 | 18 大哥 你这逻辑刚好反了啊
要证明可以 你只要给出一个初始的棋子分布就行了
证明不行 你把所有分布都安排遍？他可以是要证明对所有nxn的棋盘用n-1个棋子无论
如何排列都不能填满
【在 d****o 的大作中提到】
: 当证明一个问题不行的时候，一个反例就可以了。
: 证明行的时候，才需要证明全部情况。
|
e********5
发帖数: 422 | 19 sorry 还是无法理解这个empty space的接触的edge有啥关系 还是等待高人给解释解释
【在 s******s 的大作中提到】
: 我应该再严密些，n个checker和empty space最多有4n个edge接触。每加1个checker与
: empty space接触的edge数不会增加。至于有几轮没有关系。你自己用好好想一下。
|
g*********e
发帖数: 14401 | 20 大家看看我的递归吧，我觉得可以的，不过google应该不出智力题了吧？都是coding |
|
|
i**********e
发帖数: 1145 | 21 赞！这个思路很赞啊，怎么没人顶？
我也是一开始往你这个 induction 的思路跑，不过我往反方向跑，想要得到一个
proof by contradiction，不果。
你这个思路是对的:
》若第n个放在(n+1,n+1)上，可以证明只有当第n行 第n列（1.。。n)都已经填满的情
况下才能把n+1行、列填满。（这个有点拗口，但仔细想想是可以证的）
这个不难证明，只要有右下角那个支撑的棋子，就能不断往上建立，因为旁边的棋子都
是填满的。这个也能用类似 induction 的思路来证明。
【在 g*********e 的大作中提到】
: 我来证明
: 用递归
: N=2,3的时候不能
: 假设N=n的时候不能，则当N=n+1时
: 1...n, n+1
: .
: .
: n...n, n+1
: n+1,n+1,...
: 已知左上n*n个不能用n-1个初始checker完成全部填满，ketuide
|
i**********e
发帖数: 1145 | 22 另外一方面，当一个n x n棋盘一开始只有 n-1 个棋子的时候，觉得最后最多也就只能
覆盖 (n-1)^2 个位子。不知道这个能不能很容易得到证明。如果能证明这点的话，也
能得到这个结论。 |
k*****y
发帖数: 744 | 23 n-2个放左上的对角线上，剩一个放在(n，1)的位置能填满前n-1列
【在 i**********e 的大作中提到】
: 另外一方面，当一个n x n棋盘一开始只有 n-1 个棋子的时候，觉得最后最多也就只能
: 覆盖 (n-1)^2 个位子。不知道这个能不能很容易得到证明。如果能证明这点的话，也
: 能得到这个结论。
|
d****o
发帖数: 1055 | 24 你再想想？
你的题是：
If we start with n-1checkers， is it possible all of n^2 square be occupied
in the end? If not prove your result.
我的答案：
it is not possible. when n=2, it is not ok. Proven.
【在 e********5 的大作中提到】
: 大哥 你这逻辑刚好反了啊
: 要证明可以 你只要给出一个初始的棋子分布就行了
: 证明不行 你把所有分布都安排遍？他可以是要证明对所有nxn的棋盘用n-1个棋子无论
: 如何排列都不能填满
|
H*****1
发帖数: 4815 | 25
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这个不成立
【在 s******s 的大作中提到】
: 每放一个checker,checker和empty space的总的接触的edge数都是不变的。n-1个
: checker，最多有4(n-1)的edge接触empty space，最大的总面积是(n-1)^2，所以不可
: 能覆盖n^2的checkerboard。
|
H*****1
发帖数: 4815 | 26
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 这个推演不出来
【在 c****p 的大作中提到】
: 如果n-1个可以填满n*n的话，
: 那么初始只放一个checker就可以填满任意大的平面。
: 这与n=1和n=2时的情况相悖。
: 所以原命题是假的
:
: in
|
H*****1
发帖数: 4815 | 27 这个归纳法也不行啊
因为当你要cover n+1*n+1的时候，没说一定要前n个放在左上角的n*n里啊
【在 g*********e 的大作中提到】
: 我来证明
: 用递归
: N=2,3的时候不能
: 假设N=n的时候不能，则当N=n+1时
: 1...n, n+1
: .
: .
: n...n, n+1
: n+1,n+1,...
: 已知左上n*n个不能用n-1个初始checker完成全部填满，ketuide
|
H*****1
发帖数: 4815 | 28 赞！
不会增加
problem solved. thanks~
【在 s******s 的大作中提到】
: 我应该再严密些，n个checker和empty space最多有4n个edge接触。每加1个checker与
: empty space接触的edge数不会增加。至于有几轮没有关系。你自己用好好想一下。
|
H*****1
发帖数: 4815 | 29 老大，这个是错的
【在 i**********e 的大作中提到】
: 赞！这个思路很赞啊，怎么没人顶？
: 我也是一开始往你这个 induction 的思路跑，不过我往反方向跑，想要得到一个
: proof by contradiction，不果。
: 你这个思路是对的:
: 》若第n个放在(n+1,n+1)上，可以证明只有当第n行 第n列（1.。。n)都已经填满的情
: 况下才能把n+1行、列填满。（这个有点拗口，但仔细想想是可以证的）
: 这个不难证明，只要有右下角那个支撑的棋子，就能不断往上建立，因为旁边的棋子都
: 是填满的。这个也能用类似 induction 的思路来证明。
|
c****p
发帖数: 6474 | 30 里面是有点问题
【在 H*****1 的大作中提到】
: 老大，这个是错的
|
|
|
i**********e
发帖数: 1145 | 31 是先假设 ：
“已经放了 n-1 个棋子在 n*n 个格子里，而这个不能填满”
然后扩展与 n+1*n+1 个格子，就把之前这结果引申过来，这时候只能选择左上/下角，右上/下角都不重要，不影响最后结论。
然后这时候你只能选一个格子放一个棋子作为 n+1*n+1 棋盘的起点，他的证明就是不管你怎么放，最后都是不可能填满棋盘。
【在 H*****1 的大作中提到】
: 这个归纳法也不行啊
: 因为当你要cover n+1*n+1的时候，没说一定要前n个放在左上角的n*n里啊
|
s****i
发帖数: 197 | 32 赞高手 应该是这样证明的 为神马我就没有想到呢 唉～
多谢各位大虾 果然人民的智慧是无穷的～～
【在 s******s 的大作中提到】
: 我应该再严密些，n个checker和empty space最多有4n个edge接触。每加1个checker与
: empty space接触的edge数不会增加。至于有几轮没有关系。你自己用好好想一下。
|
