1

So I have been trying to solve the following problem:

Suppose you are given n blocks, each of which weighs an integral number of pounds, but less than n pounds. Suppose also that the total weight of the n blocks is less than 2n pounds. Prove that the blocks can be divided into two groups, one of which weighs exactly n pounds.

What I've tried so far is defining the sequence $a_1,a_2,...,a_n$ to be the weight of each of the blocks, with $a_i<n$ for all $i=1,2,...,n$.We can express the above information as: $$\sum_1^n a_i <2n$$ I also said that there exists another sequence $b_1,b_2,...,b_j$ for some integer $j$, such that $\sum_1^j b_i = n$.

However, I have not been able to find anything insightful which could help. I found that one of the terms of the sequence $\{a_i\}$ must be equal to one, but that doesn't seem very useful.

I have also been told that either the pigeonhole principle or induction could help. I've ruled out induction since it doesn't appear to be true based on the previous value of n. I have no idea what to do with regard to the pigeonhole principle, nothing seems to be appearing to me.

Does anyone have any thoughts on how to solve the question?

Cataline
  • 2,018
  • As far as problem solving goes, sometimes it helps to consider smaller cases or definite cases. Try setting n = 3, and seeing if you can find something. Then, work on larger cases and then the general case. – Race Bannon Jul 15 '15 at 17:30
  • I've tried that, without success really. For small values of n I can only really solve by cycling through values of the sequence a. – Cataline Jul 15 '15 at 17:43

1 Answers1

2

Consider the $n$ numbers $$a_1,\quad a_1+a_2,\quad a_1+a_2+a_3,\quad\dots,\quad a_1+a_2+a_3+\cdots +a_n.\tag{1}$$ If some difference between a smaller and a larger number is divisible by $n$, we are finished, since that difference is less than $2n$, so must be exactly $n$.

If no difference of numbers in List 1 is divisible by $n$, then the $n$ numbers in the list must have different remainders on division by $n$. So all remainders occur, in particular remainder $0$. And if $a_1+\cdots+a_k$ has remainder $0$ on division by $n$, it must be $n$.

Another way: Instead of using List 1, use the list $$0,\quad a_1,\quad a_1+a_2,\quad a_1+a_2+a_3,\quad\dots\dots,\quad a_1+a_2+a_3+\cdots +a_n.\tag{2}$$ These $n+1$ numbers cannot all have different remainders on division by $n$. So two of them have the same remainder, and therefore their difference has $0$ remainder. But that difference must be positive and less than $2n$, so it must be $n$.

André Nicolas
  • 507,029