用抽屉原理 
有个画家
9月份整整工作了一个月，一天也没休息，共作了45张画。他画画都是一气呵成，也就是不可能一张画画了一半留到第二天的，每天至少画了一张。证明这画家在这一个月中必有连续N天正好画了14张。
这个问题有一个简单有趣的方法设有n件事，不能有连续的几天加起来得k（1 n=k+1,...,2k-1时，k-1天要做完。 n=2k,...,3k-1时，n-k天要做完。 n=3k,...,4k-1时，2k-1天要做完。 n=4k,...,5k-1时，n-2k天要做完。 即[n/k]为偶数时，n-k*[n/k]/2天要做完，[n/k]为奇数时，k*([n/k]+1)/2-1天要做完。对这个题，n=45，k=14，[n/k]=3，27天必须做完。 |
这个一般结论的证明难吗？先是假设n天做完，每天一个，然后逐渐缩短。把这n天按模k的余数分为k组。设[n/k]=m，n mod k = r，第一组是0，k，...，mk，其中有[k/2]天做完不能睡觉，要接着做下一个，即要缩短[k/2]天。对每一组都这样考虑，其中有r+1组要缩短[k/2]天，k-r-1组要缩短[(k-1)/2]天。加起来就得到这个公式。而且同时还得到一个做法，例如27天做45个，得到的做法是前13天和后13天每天做一个，第14天做19个。 |
用抽屉原理 |
Suppose n(i) (i=1,2,...30) is the number of finished paints for the first i days. Then there exist three days with the same value of mod(n(i),14). i.e., there exist aIt's easy to demstrate that either n(b)-n(a) or n(c)-n(b) or both are 14. done. This problem will be more chanllenging if you change September to Feburary. Namely, the painter finished all the 45 paints in 28 days. The problem can be solved by the following way (deduced from 'constant'): All the 45 paints can be divided into following subgroups: 1 15 29 43 2 16 30 44 3 17 31 45 4 18 32 5 19 33 6 20 34 7 21 35 8 22 36 9 23 37 10 24 38 11 25 39 12 26 40 13 27 41 14 28 42 Now, we have to choose 28 numbers from the 14 subgroups. Obviously, if you choose 3 numbers from any of the subgroups, you will end up with at lease two of the numbers have a difference of 14. If you choose two from every subgroup, two numbers from the last (14th) subgroup will give a difference of 14 (attention: 14-0=14). 本贴由[xlxk]最后编辑于：2006-11-27 13:57:2 |
献小红花一朵 
其实constant and xlxk 的证明已经 cover了，我只是想用中文和抽屉原理把它写得更简明易懂：
设 a(i) 为前 i 天共作的画，因为每天至少画一张，所以 a(1), a(2),...,a(30)=45 , 严格递增.
再考虑，a(1)+14, a(2)+14,...,a(30)+14=59 , 也严格递增。
这60个数最多有59个不同的值，由抽屉原理，至少有i >j a(i)=a(j)+14 a(i)-a(j)=14 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |