文章阅读 北大未名站 精华区 

--------------------------------------------------------------------------------
 发信人: 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]

 

--------------------------------------------------------------------------------
本层目录 
 分类讨论区 
 全部讨论区 
 

• 谢谢，这兄弟数理推理好强 (1508) sunmoonstar_love 2005-07-22 20:53:08
• Re:我贴过来 (12) ldxf2006 2008-09-18 12:01:45
• Re:我贴过来 (292) nrg1984 2008-09-28 09:33:35
• 拜一个 Orz ,踩着别人的石头才勉强过河~~ (1508) passgod 2008-10-10 19:54:17
• Re:我贴过来 (1514) Mandolin23 2010-04-06 20:49:39
• Re:按这个思路 0 5 0 0 4 0 过不了，证明里面哪有问题？ (0) Mandolin23 2010-04-07 16:21:41
  • Re:按这个思路 0 5 0 0 4 0 过不了，证明里面哪有问题？ (141) bbbbbbbbba 2010-06-28 20:41:27
• Re:我贴过来 (1508) zhepeng123 2016-11-22 17:21:53