ZA-SAMO 2009 Problem 5

A game is played on a board with an infinite row of holes labelled $0, 1, 2, \dots$ . Initially, $2009$ pebbles are put into hole $1$ ; 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 $0$ .

(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 $0$ at the end of the game is independent of the specific sequence of steps. Determine this number.