Stone pile puzzle

micromass

You have a pile of N stones. You do the following: you take a pile and separate it into two smaller piles, multiply the numbers of stones in these two piles, and write this number on the blackboard. You do that until there is N piles with only one stone in each. Then you take a sum of all numbers written on the board. What result can you get?

Maybe an example will be instructive:
You start with a pile of 100 stones.
STEP 1: We divide it in two piles with 70 and 30 stones, thus we write 70*30=2100 on the board.
STEP 2: We divide the pile with 70 into two piles with 2 and 68, thus we write 2*68=136 on the board.
STEP 3: We divide the pile with 2 rocks into two pile with 1 rock each, thus we write 1*1=1 on the board
STEP 4: We divide the pile with 30 rocks into two piles with 15 rocks each, thus we write 15*15=225 on the board.
STEP 5: ......

As you can see, it doesn't matter which pile you divide into two piles and it doesn't matter into what numbers you divide the pile. Still the eventual sum of all the numbers on the board will be equal!!

AlephZero

For n stones, you get

Spoiler

n(n-1)/2

There must be a way to show this that doesn't use algebra, but I can't see that yet....

disregardthat

This is really interesting micromass! I think I have a combinatorial argument to show that Aleph-zero's formula is correct. This is really just a way of finding the number of ways to pair two stones.

You initially have N stones. You split them in two, and multiply the number of stones in each piles. This gives you the number of ways to pair each stone in one pile with a stone in the other pile. The reason is that for each stone in one pile, there is as many pairings with this as there are stones in the other pile. This exhausts the pairings between stones in the different piles.

To find the other ways to pair stones, all you have to do is to find the ways to pair the stones in each separate pile. The process is the same, you split each of your piles in two to get the number of pairings of stones between the piles.

Eventually reaching piles of size 1, you have exhausted the ways to pair each stone with another, yielding the answer

Spoiler

{n \choose 2} = n(n-1)/2

(spoiler brackets doesn't seem to hide latex)

micromass

Indeed, Jarl's solution is about the shortest you can get.

Here's a small rephrasing of the solution:

Spoiler

Between ever two stones, you tie a string. If you separate the stones into two piles with x and y elements, then you have to cut some strings. How many string do you have to cut? Well, exactly x*y.
The final answer is the sum of all the multiplications, thus it is the number of string we need to cut between all the stones. This is exactly n(n-1)/2!

Congratulations to both of you!

AlephZero

A proof by dissecting a geometric figure:

Spoiler

Draw a triangle with n-1 rows corresponding to the pile of n stones. Splitting the pile into two is equivalent to splitting the figure into a rectangle and two triangles.
x
x x
x x x
o o o o
o o o o x
o o o o x x

micromass

Nice! It's definitely not what I had in mind, but me like

disregardthat

I must say I really like your solution Aleph-zero. 3 different solutions to 1 puzzle is not bad. What's missing is a number-theoretic solution

.

Similar Threads for: Stone pile puzzle
Thread	Forum	Replies
Voltaic Pile of confusion	General Physics	0
Simulating a radioactive pile	General Math	4
50K Ft/Lbs explosive pile driver	Classical Physics	12
load under sand pile.	General Engineering	11
Pile Driver	Classical Physics	5

AlephZero $Math 2012$ Recognitions: Science Advisor	For n stones, you get Spoiler n(n-1)/2 There must be a way to show this that doesn't use algebra, but I can't see that yet....

micromass Blog Entries: 8 Recognitions: Gold Member Science Advisor Staff Emeritus	Nice! It's definitely not what I had in mind, but me like

disregardthat Recognitions: Science Advisor	I must say I really like your solution Aleph-zero. 3 different solutions to 1 puzzle is not bad. What's missing is a number-theoretic solution .