There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy, take turns to remove pumpkins away. Each time they can take 1 or 2 consecutive pumpkins (pumpkins considered to be consecutive only if they are consecutive on the original circle). Whoever picks up the last pumpkin wins. Ghosty makes the first move. Who is going to win with best possible moves: Ghosty or Slimy?
这个算是线性吧 【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】 : There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy, : take turns to remove pumpkins away. Each time they can take 1 or 2 : consecutive pumpkins (pumpkins considered to be consecutive only if they are : consecutive on the original circle). Whoever picks up the last pumpkin wins : . Ghosty makes the first move. Who is going to win with best possible moves: : Ghosty or Slimy?
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】 : There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy, : take turns to remove pumpkins away. Each time they can take 1 or 2 : consecutive pumpkins (pumpkins considered to be consecutive only if they are : consecutive on the original circle). Whoever picks up the last pumpkin wins : . Ghosty makes the first move. Who is going to win with best possible moves: : Ghosty or Slimy?
There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy, take turns to remove pumpkins away. Each time they can take 1 or 2
consecutive pumpkins (pumpkins considered to be consecutive only if they are consecutive on the original circle). Whoever picks up the last pumpkin wins. Ghosty makes the first move. Who is going to win with best possible moves: Ghosty or Slimy?
比码工的题好玩多了，花了周末大半天
发给我儿子了。He is in grade 3，LoL
Please post the answer later, or he will keep asking.
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 比码工的题好玩多了，花了周末大半天
目前还没有数学solution
【 在 chebyshev (......) 的大作中提到: 】
: 发给我儿子了。He is in grade 3，LoL
: Please post the answer later, or he will keep asking.
multiples of 3
是不是先拿的赢？
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 目前还没有数学solution
1,2: 先拿的人赢
>2: 后拿的人应该赢
我的程序可以找到几十，再大就算不动了。cache也加了。主要是没有线性或者以下复
杂度的算法，如果找到了，也就证明了
主要问题是目前dynamic programming的states不高效。
【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: 是不是先拿的赢？
南瓜数量是3的倍数的时候第二个赢，因为第二个只需要每次根据第一个人拿的数量，
拿1或2凑成3的倍数，这样第二个就肯定赢。
其他时候都是第一个赢，策略就是南瓜数目是3k+m的时候先拿m，然后用上面的策略就
可以了。
这个算是线性吧
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy,
: take turns to remove pumpkins away. Each time they can take 1 or 2
: consecutive pumpkins (pumpkins considered to be consecutive only if they
are
: consecutive on the original circle). Whoever picks up the last pumpkin
wins
: . Ghosty makes the first move. Who is going to win with best possible
moves:
: Ghosty or Slimy?
这个题有order限制，如果两个不相邻就拿不了
【 在 longtian (有人的地方,就有江湖) 的大作中提到: 】
: 南瓜数量是3的倍数的时候第二个赢，因为第二个只需要每次根据第一个人拿的数量，
: 拿1或2凑成3的倍数，这样第二个就肯定赢。
: 其他时候都是第一个赢，策略就是南瓜数目是3k+m的时候先拿m，然后用上面的策略就
: 可以了。
: 这个算是线性吧
: ,
: are
: wins
: moves:
这个想法好，结论不对，3个及以上，第二个人都可以赢。
如果有2n个，n>=2
第一个人拿1,2，那么第二个人拿n+1,n+2
第一个人拿1，那么第二个人拿n+1
如果有2n+1个，n>=1
第一个人拿1,2，那么第二个人拿n+2
第一个人拿1，那么第二个人拿n+1,n+2
这样剩下的两部分按直径轴对称，往下第二个mirror play就好。
【 在 Caravel (克拉维尔) 的大作中提到: 】
: 跟3没关系，是奇偶性的问题，后发的那个人可以mirror play，如果是偶数个他必必赢
: 。 如果是奇数，第一个人可以先拿一个，反转。
这题要用上对称性，
如果是偶数个，180度两两对称，所以第二个人只要mirror play，肯定是他收官。
如果是奇数个，第一个人可以先拿走一个，反转成后手。
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 这个题有order限制，如果两个不相邻就拿不了
这个是take turn拿。每个人都用自己预见的最佳策略。除了dp穷举。
这题都不一定是严格的。
Who is going to win with best possible moves
这个best possible moves should be defined with some measures/length/steps
in advance.
【 在 pptwo (pp) 的大作中提到: 】
: 这个想法好，结论不对，3个及以上，第二个人都可以赢。
: 如果有2n个，n>=2
: 第一个人拿1,2，那么第二个人拿n+1,n+2
: 第一个人拿1，那么第二个人拿n+1
: 如果有2n+1个，n>=1
: 第一个人拿1,2，那么第二个人拿n+2
: 第一个人拿1，那么第二个人拿n+1,n+2
: 这样剩下的两部分按直径轴对称，往下第二个mirror play就好。
楼上几位牛，谢谢。对，他们在讲even odd。对称！！！
当轴线确定后，一方是可以拿跨轴线的两个相邻的的
【 在 Caravel (克拉维尔) 的大作中提到: 】
: 这题要用上对称性，
: 如果是偶数个，180度两两对称，所以第二个人只要mirror play，肯定是他收官。
: 如果是奇数个，第一个人可以先拿走一个，反转成后手。
best possible moves怎么解释的？
应该就是有一个人不管对方干什么都能赢吧。
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 楼上几位牛，谢谢。对，他们在讲even odd。对称！！！
老顾你去网上搜搜nim game，变种策略证明多的很。
【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: best possible moves怎么解释的？
: 应该就是有一个人不管对方干什么都能赢吧。
3k+1 or 3k+2 sure win
3k sure lose, if the counterparty makes right moves
怎么看都像码工的game theory类题。LC上有个stone game系列。
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: 比码工的题好玩多了，花了周末大半天
对。这种镜像policy, 应该只是一种必赢策略。我的DP还有非镜像的，当然有可能可以map到镜像的方案
【 在 guvest (我爱你老婆Anna) 的大作中提到: 】
: best possible moves怎么解释的？
: 应该就是有一个人不管对方干什么都能赢吧。
西方数学教育比较注重归纳，递归教育。在这种教育下，比较聪明的的确不用怎么刷题，因为太自然就想到了。
【 在 fantasist (一) 的大作中提到: 】
: 怎么看都像码工的game theory类题。LC上有个stone game系列。
偶数个的分析是对的，后拿的人稳赢。
奇数个的情况，第二个人在对称的地方拿2个，让剩下的情况重新偶数对称，就稳赢了。
所以只要多余2个，就是后拿的那人稳赢。
【 在 Caravel (克拉维尔) 的大作中提到: 】
: 这题要用上对称性，
: 如果是偶数个，180度两两对称，所以第二个人只要mirror play，肯定是他收官。
: 如果是奇数个，第一个人可以先拿走一个，反转成后手。
【 在 pptwo (pp) 的大作中提到: 】
: 这个想法好，结论不对，3个及以上，第二个人都可以赢。
: 如果有2n个，n>=2
: 第一个人拿1,2，那么第二个人拿n+1,n+2
: 第一个人拿1，那么第二个人拿n+1
: 如果有2n+1个，n>=1
: 第一个人拿1,2，那么第二个人拿n+2
: 第一个人拿1，那么第二个人拿n+1,n+2
: 这样剩下的两部分按直径轴对称，往下第二个mirror play就好。
正解，这题是小学三年级数奥里的圆桌上拿硬币那个题目的变种，是一道好题。
这个问题我小时候做过！不过好像是苹果或者桔子。
【 在 lightroom (吃一条鱼，思考一个问题，法号三丰) 的大作中提到: 】
: There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy,
: take turns to remove pumpkins away. Each time they can take 1 or 2
: consecutive pumpkins (pumpkins considered to be consecutive only if they
are
: consecutive on the original circle). Whoever picks up the last pumpkin
wins
: . Ghosty makes the first move. Who is going to win with best possible
moves:
: Ghosty or Slimy?
你老不会是奥赛X牌吧……
【 在 digua(姚之FAN) 的大作中提到: 】
: 这个问题我小时候做过！不过好像是苹果或者桔子。
: ,
: are
: wins
: moves:
这题的难度是不需要连续的拿
你可以在一圈里面的任意地方开始拿