z*****n
发帖数: 165 | 1 1，一个N*N的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、
右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
2，2*N？
3，一般M*N? |
S****h
发帖数: 558 | 2 Not clear about your question. What if the coins are absent in upper, right
or upper-right? Can you choose that one? |
g***s
发帖数: 3811 | 3 1. win
2. win for N<>3, lose for N=3
3. thinking...
走它上面、
【在 z*****n 的大作中提到】
: 1，一个N*N的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、
: 右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
: 2，2*N？
: 3，一般M*N?
|
z*****n
发帖数: 165 | 4 可以，你选了一枚硬币后，所有右上方的有多少都要拿走
right
【在 S****h 的大作中提到】
: Not clear about your question. What if the coins are absent in upper, right
: or upper-right? Can you choose that one?
|
z*****n
发帖数: 165 | 5 2，N=3再想想？
【在 g***s 的大作中提到】
: 1. win
: 2. win for N<>3, lose for N=3
: 3. thinking...
:
: 走它上面、
|
f*******3
发帖数: 577 | 6 只要不是1*1的方正（很难定义）
第一个走的人永远都有必胜的策略，不伦是N*N, 2*N, M*N
走它上方、
【在 z*****n 的大作中提到】
: 1，一个N*N的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、
: 右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
: 2，2*N？
: 3，一般M*N?
|
z*****n
发帖数: 165 | 7 是的
【在 f*******3 的大作中提到】
: 只要不是1*1的方正（很难定义）
: 第一个走的人永远都有必胜的策略，不伦是N*N, 2*N, M*N
:
: 走它上方、
|
a********e
发帖数: 508 | 8 第三问好难啊，哪位高手说说怎么做？
走它上方、
【在 z*****n 的大作中提到】
: 1，一个N*N的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、
: 右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
: 2，2*N？
: 3，一般M*N?
|
z*****n
发帖数: 165 | 9 只能证明先手胜，简单的策略暂时不知道；当然可以用Dynamic Programming编程算。
【在 a********e 的大作中提到】
: 第三问好难啊，哪位高手说说怎么做？
:
: 走它上方、
|
a********e
发帖数: 508 | 10 能证明应该策略也差不多吧。话说怎么证明呢？
【在 z*****n 的大作中提到】
: 只能证明先手胜，简单的策略暂时不知道；当然可以用Dynamic Programming编程算。
|
|
|
l******n
发帖数: 9344 | 11 只要第一个人取对角线上的方块（不是最左下角的那个，非1X1 case)，那么剩下的图
形是y=x对称的，无论第二个人怎么选方块，第一个人就选关于y=x对称的那个方块就可
以了。最后剩下的就是最左下角那个，第二个人不得不选。
【在 f*******3 的大作中提到】
: 只要不是1*1的方正（很难定义）
: 第一个走的人永远都有必胜的策略，不伦是N*N, 2*N, M*N
:
: 走它上方、
|
z*****n
发帖数: 165 | 12 您的方法只适用于N*N吧，而且你取(N,N)的话，我可以取其他对角元——它们是没有对
称方块的。所以
N*N的必胜策略是先取(2,2)
【在 l******n 的大作中提到】
: 只要第一个人取对角线上的方块（不是最左下角的那个，非1X1 case)，那么剩下的图
: 形是y=x对称的，无论第二个人怎么选方块，第一个人就选关于y=x对称的那个方块就可
: 以了。最后剩下的就是最左下角那个，第二个人不得不选。
|
z*****n
发帖数: 165 | 13 假设后手有必胜策略。
先手取(M,N)，如果后手的必胜策略是取(i,j)，那么先手开局不取(M,N)而取(i,j)，则
先手必胜——
矛盾。
所以先手必胜。
【在 l******n 的大作中提到】
: 只要第一个人取对角线上的方块（不是最左下角的那个，非1X1 case)，那么剩下的图
: 形是y=x对称的，无论第二个人怎么选方块，第一个人就选关于y=x对称的那个方块就可
: 以了。最后剩下的就是最左下角那个，第二个人不得不选。
|
a********e
发帖数: 508 | 14 这个好像有点问题吧
先取(i,j)跟先取(M,N),(i,j)剩下的局是不一样的
【在 z*****n 的大作中提到】
: 假设后手有必胜策略。
: 先手取(M,N)，如果后手的必胜策略是取(i,j)，那么先手开局不取(M,N)而取(i,j)，则
: 先手必胜——
: 矛盾。
: 所以先手必胜。
|
z*****n
发帖数: 165 | 15 一样的啊，取了(i,j)就把它右上角所有的都取了，和先取(M,N)后取(i,j)结果一样。 |
l******n
发帖数: 9344 | 16 恩,是这样的
【在 z*****n 的大作中提到】
: 您的方法只适用于N*N吧，而且你取(N,N)的话，我可以取其他对角元——它们是没有对
: 称方块的。所以
: N*N的必胜策略是先取(2,2)
|
a********e
发帖数: 508 | 17 为啥(M,N)一定在(i,j)的右上角？
【在 z*****n 的大作中提到】
: 一样的啊，取了(i,j)就把它右上角所有的都取了，和先取(M,N)后取(i,j)结果一样。
|
z*****n
发帖数: 165 | 18 因为方阵是M*N的，所以(M,N)是最右上角那个。 |
a********e
发帖数: 508 | 19 晕，没看清楚。这个证明很妙！
【在 z*****n 的大作中提到】
: 因为方阵是M*N的，所以(M,N)是最右上角那个。
|
z*****n
发帖数: 165 | 20 恩，这就是数学之美所在啊，存在性往往不依赖于实例。
【在 a********e 的大作中提到】
: 晕，没看清楚。这个证明很妙！
|
|
|
p******e
发帖数: 756 | 21 但这里面的前提是先手和后手必有一个人有必胜策略。通常情况不一定吧
【在 a********e 的大作中提到】
: 晕，没看清楚。这个证明很妙！
|
g***s
发帖数: 3811 | 22 一定。因为状态数目是有限的。【 在 philosze (人生有很多不如意) 的大作中提到: 】 |
p******e
发帖数: 756 | 23 不一定吧，那五子棋，围棋都有必胜侧率？可能这个策略很复杂，但必然存在？
我觉得通常的情况可能是A走到了某部之后可能B有必胜侧率。但同时B如果走到了某部，
A就有必胜策略。
【在 g***s 的大作中提到】
: 一定。因为状态数目是有限的。【 在 philosze (人生有很多不如意) 的大作中提到: 】
|
g***s
发帖数: 3811 | 24 是的。只是计算不过来而已。
部，
【在 p******e 的大作中提到】
: 不一定吧，那五子棋，围棋都有必胜侧率？可能这个策略很复杂，但必然存在？
: 我觉得通常的情况可能是A走到了某部之后可能B有必胜侧率。但同时B如果走到了某部，
: A就有必胜策略。
|
a********e
发帖数: 508 | 25 10几年前不是有个国际象棋的冠军跟当时最牛的计算机下国际象棋的比赛么
据说那个运算量非常之大，当时世界上还没其他计算机能做到
要是围棋，计算量就更不能同日而语了
这也侧面说明可能这个问题要列出明确的必胜策略是挺困难的
部，
【在 p******e 的大作中提到】
: 不一定吧，那五子棋，围棋都有必胜侧率？可能这个策略很复杂，但必然存在？
: 我觉得通常的情况可能是A走到了某部之后可能B有必胜侧率。但同时B如果走到了某部，
: A就有必胜策略。
|
G********d
发帖数: 10250 | 26 同意 不错
【在 l******n 的大作中提到】
: 只要第一个人取对角线上的方块（不是最左下角的那个，非1X1 case)，那么剩下的图
: 形是y=x对称的，无论第二个人怎么选方块，第一个人就选关于y=x对称的那个方块就可
: 以了。最后剩下的就是最左下角那个，第二个人不得不选。
|
z*****n
发帖数: 165 | 27 有的游戏（如五子棋）可能出现平局，所以是“必有一方有必不败策略”。有限步、下
步选择有限的游戏
肯定是对的。
部，
【在 p******e 的大作中提到】
: 不一定吧，那五子棋，围棋都有必胜侧率？可能这个策略很复杂，但必然存在？
: 我觉得通常的情况可能是A走到了某部之后可能B有必胜侧率。但同时B如果走到了某部，
: A就有必胜策略。
|
G********d
发帖数: 10250 | 28 我觉得这个证明是有问题的
如果后手有必胜策略
先手取(M,N)，后首有必胜策略取(i,j)
那么先手取(i,j)
但是如果先手取(i,j)后的局面不一定就是取完(M,N)和(i,j)的局面（这种情况下棋子
可能更加少）
的图
就可
【在 z*****n 的大作中提到】
: 假设后手有必胜策略。
: 先手取(M,N)，如果后手的必胜策略是取(i,j)，那么先手开局不取(M,N)而取(i,j)，则
: 先手必胜——
: 矛盾。
: 所以先手必胜。
|
z*****n
发帖数: 165 | 29 先取(M,N)再取(i,j)后的局面就是(i,j)右上方的都没了；和直接取(i,j)的是一样的。
【在 G********d 的大作中提到】
: 我觉得这个证明是有问题的
: 如果后手有必胜策略
: 先手取(M,N)，后首有必胜策略取(i,j)
: 那么先手取(i,j)
: 但是如果先手取(i,j)后的局面不一定就是取完(M,N)和(i,j)的局面（这种情况下棋子
: 可能更加少）
:
: 的图
: 就可
|
G********d
发帖数: 10250 | 30 明白了 原来你在说MxN的情况。。。
great！
谢谢！
【在 z*****n 的大作中提到】
: 先取(M,N)再取(i,j)后的局面就是(i,j)右上方的都没了；和直接取(i,j)的是一样的。
|
|
|
p******e
发帖数: 756 | 31 这个必胜策略的存在性能简单的证明么？我总觉得可能不是那么简单。为什么不可能出
现对于对手的某一部，都不能必胜，但同时对手走那一部也不能保证他必胜呢？
thx
【在 z*****n 的大作中提到】
: 有的游戏（如五子棋）可能出现平局，所以是“必有一方有必不败策略”。有限步、下
: 步选择有限的游戏
: 肯定是对的。
:
: 部，
|
G********d
发帖数: 10250 | 32 假设A没有必胜策略 那么B就有必胜策略
【在 p******e 的大作中提到】
: 这个必胜策略的存在性能简单的证明么？我总觉得可能不是那么简单。为什么不可能出
: 现对于对手的某一部，都不能必胜，但同时对手走那一部也不能保证他必胜呢？
: thx
|
g***e
发帖数: 577 | 33 精辟：我补充下细节：对游戏的步数做数学归纳法。
【在 G********d 的大作中提到】
: 假设A没有必胜策略 那么B就有必胜策略
|
s***e
发帖数: 267 | 34 很有意思。1和2的答案相对简单，3比较有意思。如果先走必胜，如何构造这个解。下
面是一个尝试：
假设 M
下面是一个猜想：是因为不对称（和1不同），为了不拿到(1,1), 我们也必须不拿到(2
,2)....(M,M).
如果先暂时把M*M盖起来，剩下的就是一个 M*M1的长方形，现在问题变成了不要拿到这
个新的长方形的（1,1）位置。然后依照同样的方法对这个进行分解（考虑M1=M和M1<>M
的情况）。。。。。
走它上方、
【在 z*****n 的大作中提到】
: 1，一个N*N的方阵，每个格子里放一个硬币。甲乙轮流取：选定一枚硬币后，必须取走它上方、
: 右方和右上方的所有硬币（如果有的话）。拿走最左下角那个输。问谁有必胜策略？
: 2，2*N？
: 3，一般M*N?
|
p*****k
发帖数: 318 | 35 the game is known as chomp, which is a classical example of the so-called
"strategy-stealing" argument as given by OP. there is also an algebraic
formulation of the game by using divisors of a given integer.
it was popularized by one of Gardner's column article. the winning
positions for 2*n is known to be (x,x-1), i.e., the top row # is exactly one
less than the bottom row, but the winning positions for 3*n have
surprisingly complicated structures (see a paper by Zeilberger and the
extension by his student). it is also known the winning moves are not
always unique.
the multi-dimensional extension is also interesting, e.g. 2*2*N is easy, but
i'm not aware if anyone has solved the cube version: N*N*N? |
z*****n
发帖数: 165 | 36 That's so cool, thanks a lot!
called
one
but
【在 p*****k 的大作中提到】
: the game is known as chomp, which is a classical example of the so-called
: "strategy-stealing" argument as given by OP. there is also an algebraic
: formulation of the game by using divisors of a given integer.
: it was popularized by one of Gardner's column article. the winning
: positions for 2*n is known to be (x,x-1), i.e., the top row # is exactly one
: less than the bottom row, but the winning positions for 3*n have
: surprisingly complicated structures (see a paper by Zeilberger and the
: extension by his student). it is also known the winning moves are not
: always unique.
: the multi-dimensional extension is also interesting, e.g. 2*2*N is easy, but
|
s***e
发帖数: 267 | 37 pcasnik,
Thanks for the information! Are you saying that there is no simple strategy
which makes the first player always winning? Note that the solution has a
complicated structure is not equivalent to the existance of a simple
strategy, since as the first player, you may not care all possible winning
positions. All you care is how to proceed based on your strategy.
one
but
【在 p*****k 的大作中提到】
: the game is known as chomp, which is a classical example of the so-called
: "strategy-stealing" argument as given by OP. there is also an algebraic
: formulation of the game by using divisors of a given integer.
: it was popularized by one of Gardner's column article. the winning
: positions for 2*n is known to be (x,x-1), i.e., the top row # is exactly one
: less than the bottom row, but the winning positions for 3*n have
: surprisingly complicated structures (see a paper by Zeilberger and the
: extension by his student). it is also known the winning moves are not
: always unique.
: the multi-dimensional extension is also interesting, e.g. 2*2*N is easy, but
|
f*k
发帖数: 95 | |
x********9
发帖数: 31 | 39 都是先手赢。
3.设左下那个硬币坐标是（1，1）。那么用和2类似策略可以保证所有 （k,k）都是后
手拿到。（除非这个硬币被作为其他硬币的“附属品”拿掉） |
g***s
发帖数: 3811 | 40
how?
【在 x********9 的大作中提到】
: 都是先手赢。
: 3.设左下那个硬币坐标是（1，1）。那么用和2类似策略可以保证所有 （k,k）都是后
: 手拿到。（除非这个硬币被作为其他硬币的“附属品”拿掉）
|
|
|
l**********e
发帖数: 6 | 41 这个证明的问题是：先手为什么必须取最右上角那个(M,N)，这样一来你可以假定i>=M
and j>=N。但是对于i
philosze有同样的疑问。五子棋，象棋，围棋存在必胜策略吗？这是一个大大的问号。
而且，棋类的规则与本题的chomp大不相同，所以很多结论是不能简单类比和类推的。
grass说如果状态数目有限，那么先手和后手一定必有一个人有必胜策略。请问为什么？
GlennGould和geome，请问如何证明：“假设A没有必胜策略 那么B就有必胜策略”？
则先手必胜——矛盾。
【在 z*****n 的大作中提到】
: 假设后手有必胜策略。
: 先手取(M,N)，如果后手的必胜策略是取(i,j)，那么先手开局不取(M,N)而取(i,j)，则
: 先手必胜——
: 矛盾。
: 所以先手必胜。
|
