Blog Entries: 8
Recognitions:
Gold Member
Staff Emeritus

## Stone pile puzzle

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:
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!!

 PhysOrg.com science news on PhysOrg.com >> Heat-related deaths in Manhattan projected to rise>> Dire outlook despite global warming 'pause': study>> Sea level influenced tropical climate during the last ice age
 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....
 Recognitions: Science Advisor 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)

Blog Entries: 8
Recognitions:
Gold Member
Staff Emeritus

## Stone pile puzzle

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!

 Recognitions: Science Advisor 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
 Blog Entries: 8 Recognitions: Gold Member Science Advisor Staff Emeritus Nice! It's definitely not what I had in mind, but me like
 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 .