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 hawk at 2005-03-31 23:28:01 on Problem 1405
命题是:按照题目的要求
取
a(1)=2
a(2)=3
...
a(n)=a(1)*a(2)*..*a(n-1)+1
的时候,剩下最少,为1/(a1*a2*...*an),令r(n)=a1*a2*...an
然后归纳的时候
利用下面这个性质
k+1时候,前k个取完后剩下越少,取完第k+1个之后,剩下也越少
这个可以用函数单调性比较简单证明
假设取完前k个剩余1/c (由于前k的取法随意,c不一定是整数)
取第k+1个的时候,取1/([c]+1)使得剩余最少,而这个值是f(c)=1/c-1/([c]+1)
容易证明f单调减,而由归纳假设,c的最大值是r(k),所以当c取r(k)的时候
k+1步取完剩余最少
计算一下a[k+1]和剩余,容易发现得证
完善一下就比较严格了。

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