0

Question: There is a heap of 1001 stones on a table. You are allowed to perform the following operation: you choose one of the heaps containing more than one stone, throw away a stone from the heap, then divide it into two smaller (not necessarily equal) heaps. Is it possible to reach a situation in which all the heaps on the table contain exactly $3$ stones by performing the operation finitely many times?

The solution is as follows: Let I be the sum of the number of stones and heaps. An easy check shows that the operation leaves I invariant. The initial value is 1002. But a configuration with k heaps, each containing $3$ stones, has $I = k + 3k = 4k$. This number cannot equal $1002$, since $1002$ is not divisible by $4$.

What I don't understand is the reasoning behind letting I = the sum of stones and heaps. This just seems somewhat arbitrary. Why wouldn't I equal the sum of all stones. Any help is appreciated.

Adeyemi Lawal
  • 37
  • 2
  • 6
    The author is looking for an invariant. The number of remaining stones is not invariant. At each move, you lose one stone, but gain one heap, so that makes sum "stones + heaps" an invariant. – quasi Jun 19 '18 at 00:59

1 Answers1

1

One way to find this invariant is to realize that in each operation you "pay" a stone to start an additional heap.

So morally, you want to use the number of stones as invariant, but since we exchange stones for additional heaps, we need to add the number of heaps to account for the spent stones.

Phira
  • 20,860