Question

Suppose you have to distribute the numbers {1; 2; 3; ... ; 2n-1;2n} over n buckets. Show that there will always be at least one bucket with its sum of numbers to be >=2n+1.

Answer 1

Let us assume that the sum of numbers in each bucket is less than 2n +1.

Where n is the number of buckets into which numbers ranging from 1 to 2n are distributed.

Let the sum of numbers in first bucket is s1.

Similarly there are s2,s3,s4,...,sn sums.

$s1+s2+...+sn = 1+2+...+(2n-1)+(2n)$

$s1 +s2+...+sn = (2×n)×(2×n+1)/2$

$s1 + s2 +...+sn = n×(2×n+1)$ ------(i)

According to our assumption

$s1<(2×n+1)$

$s2<(2×n+1)$

Similarly, $sn<(2×n+1)$

Adding up the above equations,we get ;

$s1 +s2+...+sn <(2×n+1)×n$

But this is a contradiction to the equation --(i)

So our assumption is wrong.

Thus,there will always be at least one bucket

with its sum of numbers to be >=2n+1.

(Proved)