How many pebbles end up in hole 0?
Source: South African MO 2009 Q5
May 26, 2012
invariantabsolute valuecombinatorics unsolvedcombinatorics
Problem Statement
A game is played on a board with an infinite row of holes labelled . Initially, pebbles are put into hole ; the other holes are left empty. Now steps are performed according to the following scheme:(i) At each step, two pebbles are removed from one of the holes (if possible), and one pebble is put into each of the neighbouring holes.(ii) No pebbles are ever removed from hole .(iii) The game ends if there is no hole with a positive label that contains at least two pebbles.Show that the game always terminates, and that the number of pebbles in hole at the end of the game is independent of the specific sequence of steps. Determine this number.