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

拜一个 Orz ,踩着别人的石头才勉强过河~~

Posted by passgod at 2008-10-10 19:54:17 on Problem 1014
In Reply To:我贴过来 Posted by:frkstyc at 2005-07-22 20:41:44
> 文章阅读 北大未名站 精华区 
> 
> --------------------------------------------------------------------------------
>  发信人: wuminghui (lagrima), 信区: ACM_ICPC
> 标  题: 关于dividing问题中如何将20000改写为1000问题的严格证明:
> 发信站: 北大未名站 (2003年03月13日21:49:11 星期四) , 站内信件
> 
> 
> 对于任意一组数,6的个数为n(n>=8)
> 
> 一。如果可以分成两堆,我们可以分成两种情况:
> 1.两堆里都有6,那么我们可知:把n改为n-2,仍然可分。(两堆各减一个6)
> 2.只有一堆里有6,设为左边,那么左边的总和不小于6*8=48。
>   我们观察,5*6=6*5  ,4*3=6*2  , 3*2=6  , 2*3=6 , 1*6=6
>   而 5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 25 + 8 + 3 + 4 + 5 = 45 < 48
>   由抽屉原理右边必然存在(多于5个的5 或者 多于2个的4 或者 多于1个的3
>                          或者 多于2个的2 或者 多于5个的1)
>   即右边至少存在一组数的和等于若干个6,比如右边有3个4
>   这样把左边的2个6与右边的3个4交换,则又出现左右都有6的情况。
>   根据1,我们还是可以把n改为n-2且可分的状态不变。
> 综合1,2。我们可以看出只要原来n的个数>=8,我们就可以把它改为n-2,
> 这样操作一直进行到n<8。我们可以得出结论,对于大于等于8的偶数,可以换成6
> 对于大于8的奇数,可以换成7。换完之后仍然可分。
> 
> 二。如果不能分成两堆:
>   显然改为n-2时同样也不能分,那么对于大于等于8的偶数,可以换成6
> 对于大于8的奇数,可以换成7。换完之后仍然不可分。
> 
> 综合一,二。我们得出结论把不小于8的偶数改为8,大于8的奇数改为7,
> 原来可分与否的性质不会改变。
> 
> 以上是对6的讨论,同样的方法可以推出
> 5的个数 6*4 + 4*4 + 3*4 + 2*4 + 1*4 = 64 < 5*13
>     即5的个数多于12时,偶数换为12,奇数换为11
> 4的个数 6*1 + 5*3 + 3*3 + 2*1 + 1*3 = 35 < 4*9
>     即4的个数多于8时,偶数换为8,奇数换为7
> 3的个数 5*2 + 4*2 + 2*2 + 1*2 = 24 < 3*9
>     即3的个数多于8时,偶数换为8,奇数换为7
> 2的个数 5*1 + 3*1 + 1*1 = 9 < 2*5
>     即2的个数多于4时,偶数换为4,奇数换为3
> 1的个数 多于5则必然可分(在总数是偶数的前提下)
>   
> 
> --
> 
> ※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.108.234]
> 
>  
> 
> --------------------------------------------------------------------------------
> 本层目录 
>  分类讨论区 
>  全部讨论区 
>  

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