0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Lucas
    Feb 22, 2021 at 6:22

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.