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 bbbbbbbbba at 2011-07-11 19:38:19 on Problem 1740
In Reply To:Re:其实很简单,看似N复杂 Posted by:gdczcpy at 2010-06-03 01:37:17
> 这规律怎么观察出来的?
观察的确很难,但是证明相当简单。
对任意状态,把所有的堆从大到小排序,设为a[1],a[2],a[3]……,a[n]>0。
首先确定操作最大的一堆a[1]。把a[2]-a[3]个石子放到第3堆,a[4]-a[5]个石子放到第5堆,等等。
如果n是奇数,直接把剩下的石子扔掉。如果n是偶数,最后第一堆留an个石子,其余扔掉。
当n是奇数,扔掉的石子数为a[1]-(a[2]-a[3])-(a[4]-a[5])-……-(a[n-1]-a[n])=a[1]-a[2]+a[3]-a[4]+……+a[n-2]-a[n-1]+a[n]>=a[n]>0,操作必定成功。
当n是偶数,扔掉的石子数为a[1]-(a[2]-a[3])-(a[4]-a[5])-……-a[n]=a[1]-a[2]+a[3]-a[4]+……+a[n-1]-a[n]。操作不成功<=>扔掉的石子数为0<=>a[1]-a[2]=a[3]-a[4]=……=a[n-1]-a[n]=0,即当前已经为必败态。
显然操作成功时能够得到必败态,必败态无法转化为必败态。证毕。

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