Suppose you begin with a pile of n stones and split this pile into n piles of on

Question

Suppose you begin with a pile of n stones and split this pile into n piles of one stone each by repeatedly splitting a pile of stones (of size two or more) into two piles. Each time you split a pile, you multiply the number of stones in each of the resulting piles -- for example, if I split a pile of 10 stones into a pile of size 3 and a pile of size 7, then I compute 21. During this process, you keep track of the sum of all of these products. We claim that no matter how you split the piles, the sum of the products computed is n(n-1)/2 (a) show this is true for n=5 by brute force: enumerate all possible ways in which the 5 stones can be partitioned and evaluate each sum of products. (b) Prove that the claim is true for all n1. What kind of induction did you use?

Explanation / Answer

please rate :)

suppose you have 5 stones

split it it as (1,4), (2,3)

1 x 4 = 4

2 x 3 = 6

6 + 4 = 10

5(5-1)/2 = 10

hence we proved for n = 5

I already posted the solution for n = n :)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.