Archive

Posts Tagged ‘数学题’

NOIP2010提高组初赛问题求解第三题推广

October 27, 2010 Leave a comment

我们很自然地想求解下面的问题:

题目:记T为一队列,初始时为空,现有k个总和不超过n的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为m,那么k的最小值是___________。

显然当m<=0或n<=0或n<m时此题无解,否则:

类似地我们构建下面的图:

0—m—2m—…—m*[n/m]
1—m+1—2m+1—..—m*[n/m]+1
……
n%m—m+n%m—…—n

n%m+1—n%m+1+m—…—n-m+1

m-1—2m-1—…—n-n%m+1
第0行至第n%m行最多总共选([[n/m]/2]+1)(n%m+1)个
第n%m+1行至第m-1行最多总共选[([n/m]+1)/2](m-1-n%m)个
所以总共最多选([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)个
注意到,我们计算的时候包含了S0,所以k的最小值就是([[n/m]/2]+1)(n%m+1)+[([n/m]+1)/2](m-1-n%m)

以原题n=32, m=9代入,得

k=([32/9]/2+1)*(32%9+1)+[(32/9]+1)/2]*(9-1-32%9)=2*6+2*3=18

Advertisements
Categories: OI Tags: , , , , ,

A math problem concerned about monotonicity

October 10, 2010 Leave a comment

Given that f(x) is a monotonously increasing function and g(x)=f(x)-f(1-x). Now if for certain real numbers x_1, x_2, g(x_1)+g(x_2)>0, compare x_1+x_2 and 1.

Here we will prove that $latex  x_1+x_2>1$.

Obviously, when x_1>=1-x_1, x_2>=1-x_2 while the equalities don’t hold simultaneously, we can easily deduce the condition; at the same time we can get x_1+x_2>1.

While if x_1<=1-x_1 and x_2<=1-x_2, apparently we have

f(x_1)<=f(1-x_1), f(x_2)<=f(1-x_2), so f(x_1)+f(x_2)<=f(1-x_1)+f(1-x_2), so g(x_1)+g(x_2)<=0.

Now consider if x_1>=1-x_1 and x_2<=1-x_2. Thus we have x_1>=1/2 and x_2<=1/2. So at the same time we have
x_2<=x_1 and x_2<=1-x_2

Now if x_1+x_2<=1, then x_1<=1-x_2, then x_2<=1-x_1.

So we have x_2<=1-x_1<=x_1<=1-x_2

So f(x_2)<=f(1-x_1)<=f(x_1)<=f(1-x_2)

So f(x_2)+f(x_1)<=f(1-x_1)+f(1-x_2)

Which indicates that the condition holds only if x_1+x_2>1.

Symmetrically we can prove the same when x_1<=1-x_1 and x_2>=1-x_2.

数学趣题:铲雪机

October 6, 2010 Leave a comment

下雪了。雪花以恒定的速率落下。过了一会儿,一辆铲雪车开始铲雪。铲雪车在单位时间内所铲的雪的体积是固定的,也就是说,铲雪车前进的速度和雪的厚度成反比。已知这辆铲雪车在第一小时内行走的距离是第二小时内行走的距离的两倍,求铲雪车开始铲雪的时间距离开始下雪的时间有多久。

Read more…