0

There are $n$ piles of marbles and that every pile has a different number of marbles. We want to prove that the sum of the number of marbles in all the piles is greater than or equal to $\frac{n(n + 1)}{2}$, without knowing anything beyond the fact that each pile has a different number of marbles. Use induction to prove this fact for any positive integer $n$.

I'm having trouble writing the initial equation to solve and getting started. $\sum_{i=1}^{n}$ $\geq \frac{n(n + 1)}{2}$ is what I have so far where the base case is n = 1, but should I say have a variable for the number of piles so that it's written like $\sum_{i=1}^{p}~$ p $~\geq \frac{n(n + 1)}{2}$ where p is the sum of the piles and then the base case would be p = 1?

Lauren Zio
  • 31
  • 1
    Note that the sum you looking for is greater then or equal to $1 + 2 + \cdots + n$: let $p_1,p_2,...,p_n$ your piles and assume that $p_1$ has $k$ numbers of marbles. Then, WLOG, $p_1 < p_2 < \cdots < p_n$. Thus, the smallest number is when $k = 1$ and $p_i$ has $i$ marbles. Thus, if you show that $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$, your problem is solved. – Lucas Feb 22 '21 at 06:22

1 Answers1

4

Base case : (Assuming that each pile has non zero number of marbles) Clearly the claim is true for $ 1 $ pile .
Induction Hypothesis : Suppose that the sum of number of marbles in each pile is greater than $ \frac{n(n+1)}{2} $ for some arbitrary $n$ piles.
Induction step : Now suppose that there are $n + 1$ piles. Obviously the last pile has to contain at least $ n + 1 $ marbles as the number of marbles in each pile is distinct. Let the number of marbles in last pile be $p$. We have that $ p \geq n+1$ . Hence $$ \frac{n(n+1)}{2} + p \geq \frac{n(n+1)}{2} + n + 1$$ As there are at least $\frac{n(n+1)}{2}$ marbles when there are $n$ piles from our hypothesis, we are done.

Strange
  • 737