画家作画的证明题 [:)]

野菜花 · 发表于 2006-11-24 07:14:13

有个画家

9月份整整工作了一个月，一天也没休息，共作了45张画。他画画都是一气呵成，也就是不可能一张画画了一半留到第二天的，每天至少画了一张。证明这画家在这一个月中必有连续N天正好画了14张。

本贴由[野菜花]最后编辑于：2006-11-24 8:26:29

constant · 发表于 2006-11-26 00:32:39

记得有一个这类问题的一般解

野菜花 · 发表于 2006-11-26 17:25:57

如果你的一般方法写起来不复杂，是否能和我们分享一下

这个问题有一个简单有趣的方法

constant · 发表于 2006-11-27 00:42:59

设有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天必须做完。

野菜花 · 发表于 2006-11-27 03:24:43

你记忆力真好，佩服！

这个一般结论的证明难吗？

constant · 发表于 2006-11-27 05:48:17

先是假设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个。

野菜花 · 发表于 2006-11-27 07:29:14

COOL, Thank you

野菜花 · 发表于 2006-11-27 20:10:55

用抽屉原理

xlxk · 发表于 2006-11-27 21:14:45

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

野菜花 · 发表于 2006-11-27 22:14:04

Smart!

献小红花一朵

野菜花 · 发表于 2006-11-28 20:41:18

其实constant and xlxk 的证明已经 cover了，我只是想用中文和抽屉原理把它写得更简明易懂：

设 a(i) 为前 i 天共作的画，因为每天至少画一张，所以 www.ddhw.com

a(1), a(2),...,a(30)=45 , 严格递增.

www.ddhw.com

再考虑，a(1)+14, a(2)+14,...,a(30)+14=59 , 也严格递增。

www.ddhw.com

这60个数最多有59个不同的值，由抽屉原理，至少有i >j

a(i)=a(j)+14

a(i)-a(j)=14

		自动登录	找回密码
密码			立即注册

动态微博

画家作画的证明题 [:)]

记得有一个这类问题的一般解

如果你的一般方法写起来不复杂，是否能和我们分享一下[@};-] 这个问题有一个简单有趣的方法

我现想看能不能想起来[:D)]

你记忆力真好，佩服！[:-Q] 这个一般结论的证明难吗？

不难，但是有点啰嗦

COOL, Thank you [@};-] [@};-][@};-]

这个问题有一个简单有趣的证明，提示：

回复：画家作画的证明题 [:)]

Smart![:-Q][@};-][@};-] 献小红花一朵[:)]

用简单的抽屉原理证明