Distributing numbers over n buckets

[Akash47]

Homework Statement

The numbers {1,2,3,....2n-1,2n} are to be distributed over n buckets. Show that there will always be at least one bucket with its sum of numbers to be ≥ 2n+1.

Relevant Equations

Sum of the first 'n' natural numbers =n^2 +n/2 .

I've got the problem well. The sum of the given numbers is 2n(2n+1)/2 = n(2n+1). And there are n buckets, so the average sum of numbers of each bucket is 2n+1.I've come to this so far. But I'm not sure whether the numbers are to be distributed over all 'n' buckets or some of the buckets can remain empty (as it is not clear from the problem). In the first case, I think the problem gets harder. Now, what should I do?

 

[WWGD]

I think the Pigeonhole Principle should do it.

 

[sysprog]

I think that the problem is mis-stated -- the sum of the first $n$ natural numbers is $(n/2)*(n+1)$. You could also write it unambiguously as $(n^2+n)/2$. For the rest of the problem, please look up 'pigeonhole principle' and 'generalized pigeonhole principle' -- the latter is for ascending sequences of natural numbers from $n$ to $>n$ (not necessarily beginning with $1$).

 

[Akash47]

I think that the problem is misstated -- the sum of the first $n$ natural numbers is $(n/2)*(n+1)$. You could also write it unambiguously as $(n^2+n)/2$. For the rest of the problem, please look up 'pigeonhole principle' and 'generalized pigeonhole principle' -- the latter is for ascending sequences of natural numbers from $n$ to $>n$ (not necessarily beginning with $1$).

But how is it applied? It would be applicable if $2n+1$ numbers were to be distributed over $n$ buckets. But that would just give that 'at least one bucket contains more than 2 numbers'.But what about the sum of them? Pigeonhole principle deals with the numbers not with the sum of them. Then how can I use it in that case? Please in a bit more details.

 

[PeroK]

But how is it applied? It would be applicable if $2n+1$ numbers were to be distributed over $n$ buckets. But that would just give that 'at least one bucket contains more than 2 numbers'.But what about the sum of them? Pigeonhole principle deals with the numbers not with the sum of them. Then how can I use it in that case? Please in a bit more details.

Try with $n =5$, say, and see what happens.

 

[sysprog]

A little anecdote:

When Carl Gauss was a boy, a teacher betasked the students in the classroom with summation of the integers from 1 to 100 inclusive of 1 and 100. Gauss immediately realized that 1+100=101, that 2+99=101, et cetera, until one reaches 50+51=101, and that there were exactly 50 such pairs, so that the total must be 50*101=5050, so young Gauss wrote 5050 on his slate, and put the slate on his desk.

The teacher had done the exercise himself by a more time-consuming method, but had erred, and had a different sum as the to-himself putatively-correct result. Accordingly, he sent young Gauss to the office of the Principal/Headmaster, charged with defiance/impudence and failure to complete the exercise. There, young Gauss explained his reasoning, and after conference between the Principal/Headmaster and the teacher, it was decided that Gauss would be sent to higher education.

In the problem instanter, uptaking the suggestion of @PeroK to experimentally use n=5, please visualize a place with 5 accommodation locations, e.g. a bank with 5 teller stations, at which bank, persons are asked/directed to take a numbered slip, the slips being numbered with consecutive integers starting with 1. The first 5 persons occupy the 5 teller stations, one person per station. When a 6th person arrives, assuming that no-one has concluded business at any of the teller stations, the 6th person must either wait, or intrude himself, a 2nd person, at one of the teller stations.

That is an illustration of the pigeonhole principle.

 

[sysprog]

Homework Statement: The numbers {1,2,3,...2n-1,2n} are to be distributed over n buckets. Show that there will always be at least one bucket with its sum of numbers to be ≥ 2n+1.
Homework Equations: Sum of the first 'n' natural numbers =n^2 +n/2 .

I've got the problem well. The sum of the given numbers is 2n(2n+1)/2 = n(2n+1). And there are n buckets, so the average sum of numbers of each bucket is 2n+1.I've come to this so far. But I'm not sure whether the numbers are to be distributed over all 'n' buckets or some of the buckets can remain empty (as it is not clear from the problem). In the first case, I think the problem gets harder. Now, what should I do?

With $n=5$, as suggested by @PeroK, for example, given that the numbers have to include $2n$, which in this test instance equals $10$, the underlined statement requires that $10$ be added to a bucket which already contains an integer $>0$; after the $5$ buckets are occupied with the first $5$ integers, the procedure requires doubling up of the occupancy of each bucket, until $2n$ is reached, which in the case of $n=5$ means that eventually $10$, is placed in a bucket, and the least number of any bucket, prior to a second number being added, is $1$, so the bucket to which, in the case of $n=5$, $10$, i.e. $2n$, is added, will have to hold a number sum equal to or greater than $11$, i.e. $2n+1$.

 

[SammyS]

Homework Statement: The numbers {1,2,3,...2n-1,2n} are to be distributed over n buckets. Show that there will always be at least one bucket with its sum of numbers to be ≥ 2n+1.
Homework Equations: Sum of the first 'n' natural numbers =n^2 +n/2 .

You should write that last expression in any of the following ways. (Remember: Order of Operations)

(n^2 +n)/2 , { Looks better as (n² + n)/2 . )​

​

n(n+1)/2​

​

$\dfrac{n^2 +n}{2}$ , using LaTeX.​

I've got the problem well. The sum of the given numbers is 2n(2n+1)/2 = n(2n+1).
...

 

[ehild]

Homework Statement: The numbers {1,2,3,...2n-1,2n} are to be distributed over n buckets. Show that there will always be at least one bucket with its sum of numbers to be ≥ 2n+1.
Homework Equations: Sum of the first 'n' natural numbers =n^2 +n/2 .

I've got the problem well. The sum of the given numbers is 2n(2n+1)/2 = n(2n+1). And there are n buckets, so the average sum of numbers of each bucket is 2n+1.I've come to this so far. But I'm not sure whether the numbers are to be distributed over all 'n' buckets or some of the buckets can remain empty (as it is not clear from the problem). In the first case, I think the problem gets harder. Now, what should I do?

What you wrote concerning the average sum of numbers in the buckets means that in case when all buckets contain the same sum, this sum is 2n+1. If the sum in one bucket is less, there must be at last one bucket where the sum is more than 2n+1. And you have to prove that the sum is equal or more than 2n+1 at least in one bucket. Is it true?

 

[sysprog]

Hint: does the problem statement include that you can't put all the numbers in the first bucket?

Spoiler

A bigger hint -- please look up the pigeonhole principle -- it's an early precept in the 'advanced counting' sub-discipline of the topic of Discrete Mathematics.

 

[Akash47]

I've got the problem well. I want to close the thread. How can I do that?

 

[WWGD]

I've got the problem well. I want to close the thread. How can I do that?

Report it on lower left and tell the mods. Not sure if closing threads on demand is part of usual protocol but give it a try and see.

 

[sysprog]

Why would you not suppose that it's more than a little bit high-handed of you to even want to, let alone ask how to be enabled to be allowed to, bring about to become closed, a thread on this forum set, to which thread and forum set others have contributed, which forum thread you were yourself only by grace, allowed to open?