Stone pile puzzle

  • Thread starter micromass
  • Start date
  • #1
22,097
3,282

Main Question or Discussion Point

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

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
291
For n stones, you get
n(n-1)/2
There must be a way to show this that doesn't use algebra, but I can't see that yet....
 
  • #3
disregardthat
Science Advisor
1,854
33
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
{n \choose 2} = n(n-1)/2
(spoiler brackets doesn't seem to hide latex)
 
Last edited:
  • #4
22,097
3,282
Indeed, Jarl's solution is about the shortest you can get.

Here's a small rephrasing of the solution:

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!
 
  • #5
AlephZero
Science Advisor
Homework Helper
6,994
291
A proof by dissecting a geometric figure:

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
 
  • #6
22,097
3,282
Nice! It's definitely not what I had in mind, but me like :tongue2:
 
  • #7
disregardthat
Science Advisor
1,854
33
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 :biggrin:.
 

Related Threads on Stone pile puzzle

  • Last Post
2
Replies
27
Views
4K
  • Last Post
Replies
8
Views
2K
  • Last Post
2
Replies
29
Views
4K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
3
Views
2K
  • Last Post
2
Replies
31
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
16
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
14
Views
6K
Top