棋题 from WXC

constant · 发表于 2006-4-18 20:11:48

难度：++.5www.ddhw.com

有2000个方格排成一排，两个玩家轮流在方格里写S或O，谁先在连续的三个方格里写出SOS，谁就获胜；如果都写不出来就算平局。www.ddhw.com

请证明：后写的人有胜算。

好好活着 · 发表于 2006-4-19 10:29:57

如题，如果是就好说列：

第一个人要写个S，第二个人就不敢写O,因为一写O人家就赢了，于是只好也写S,同理第一个人还是写S,写到第1999个S的时候，轮到第二个人了，他填个O就连上了--SOS！

第一个人想平局，于是写个O,第二个人照样写个S,第一个人也只好跟着写S,然后S到第1999个，轮到第二个人写了，他再加个S,还是--SOS！

结论：1.如果方格是首尾相连的，那就没什么说的，肯定第二个人赢。100个还是20000个方格都一样。

2.如果方格不是首尾相连，那第二个人不可能保证一定有胜算。如第一种情况所言，两人写满2000个S,就平局了。

P.S. 本人数学一项不及格，所以用笨办法来推结果，各位高手不要笑话哈。

constant · 发表于 2006-4-19 19:09:09

不是首尾相连。但是写的时候不要求挨着写。

好好活着 · 发表于 2006-4-20 06:39:27

我说嘛，这才是数学题啊，等我再想想

sean9991 · 发表于 2006-4-21 01:06:37

There are 4000 opportunities (2000 spots, each with 2 ways to fill the spot) to fill the spaces. To fill a spot with a letter, the player reduce the opportunity by 2 for the spot, and adjust the opportunities at the netghbor spots. For example, the first player put an 'S' at somewhere in the middle, he reduces the opportunity by 6. If he put an 'S' at the corner, the opportunity is reduced by 4. The strategy of the second player is such that the opportunity is 4000 - 8K (K integer) after his move. There are many scenarios to examine with this approach though.

勇敢的辛 · 发表于 2006-4-21 18:03:57

不管A第一个填哪里，B总可以在某一端的第4格填一个S。如果A接下来在1-3里填，B在第7格填S；如果A在第5格以后填，B在第1格填S。这样，B总可以做出两个S中间留两个空格的陷阱，A在中间怎么填都会输。而无论A怎么填其它，最后其它格全满了时，按奇偶关系A不得不掉进陷阱。

sean9991 · 发表于 2006-4-21 18:41:40

What if A plays in such a way that it's B who has to fall into the trap? Can you prove that this will not happen?

constant · 发表于 2006-4-21 19:28:13

基本上对，要证明没有其他形式的陷阱

一般来说，N是大于14的偶数时后走必胜，N是大于5的奇数时先走必胜，其他情况没人能保证必胜。

勇敢的辛 · 发表于 2006-4-23 15:56:36

显然陷阱只能是两个S夹两个空格。如果中间是3个空格，则可以在最中间填O破解。

如果A也设置同样陷阱，B不理会。无论有多少个陷阱，留下的都是偶数个空格，在其它格填完后还是A先掉进去。

hfdf · 发表于 2008-8-25 09:06:21

1筐橘子连筐重20.05千克,买出1半后,连筐还重11.37千克,原来橘子重多少千克

hfdf · 发表于 2008-8-25 09:18:21

1筐橘子连筐重20.05千克,买出1半后,连筐还重11.37千克,原来橘子重多少千克

		自动登录	找回密码
密码			立即注册

动态微博

棋题 from WXC

排成一排是不是最后首尾相连啊？

不是首尾相连。但是写的时候不要求挨着写。

我说嘛，这才是数学题啊，等我再想想[:-K]

回复：棋题 from WXC

回复：棋题 from WXC

回复：回复：棋题 from WXC

回复：回复：棋题 from WXC

回复：回复：回复：棋题 from WXC

回复：我说嘛，这才是数学题啊，等我再想想[:-K]

回复：我说嘛，这才是数学题啊，等我再想想[:-K]