Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

对称博弈

Posted by tzkq at 2010-11-18 01:04:00 on Problem 2484
写点感想吧, 记得刚进高中的时候, 物理老师就举了一个例子,大概是这样的:

有个棋盘,两个棋手交错走棋,没有其他规则,就只是占领棋格,请问谁会赢(占的格子多)?
答案是先手赢。

如何证明?
先手一来就占领棋盘的正中, 然后不管后手如何走, 他都走与之呈点对称的位置,最后一定是先手多一个格。


直观来讲,也是先手赢,但并不严谨。通过对称这一思路,在这里就起作用了。


回到此题,说说大概的思路:当n>=3时,无论A如何选择,B选择一个特殊的位置(1个或者连续2个)正好把剩下的环路分成两个链路,大小相同。
接下来,无论A选择两个链路中哪一个,进行何种操作,B只需要选择另一个链路中,进行相同的操作。剩下的系统,仍是对称的。
直到最后,B肯定是最后一个进行操作的。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator