Several boxes are arranged in a circle. Each box may be empty or may contain one or several chips. A move consists of taking all the chips from some box and distributing them one by one into subsequent boxes clockwise starting from the next box in the clockwise direction. (a) Suppose that on each move (except for the first one) one must take the chips from the box where the last chip was placed on the previous move. Prove that after several moves the initial distribution of the chips among the boxes will reappear. (b) Now, suppose that in each move one can take the chips from any box. Is it true that for every initial distribution of the chips you can get any possible distribution?
Problem
Source: ToT - 2001 Spring Senior A-Level #7
Tags: combinatorics unsolved, combinatorics
Icarus_
17.08.2011 20:21
If originally each box is not empty and the number of boxes is greater than the maximal number of chips in a single box then each move after the first will leave a box with no chips in it, so you never get back to the original. what's up.
chaotic_iak
18.08.2011 16:45
Icarus_, you overlooked something. Try this (bold means current move): 1,2,2 2,0,3 0,1,4 2,2,1 0,3,2 1,4,0 2,1,2 3,2,0 4,0,1 1,2,2 As you said, each box is not empty, the number of boxes is greater than the maximal number of chips in a single box, but you can still go back to the original. So your claim is incorrect.
mathophile593
19.08.2011 00:33
(a) I will call a state a distribution of the chips to the boxes along with a mark on a non-empty box indicating that this is the next box to be drawn from. Since there are a finite number of states and every state has a unique successor, it suffices to show that each state has a predecessor. The following process finds such a predecessor for any state by inverting the distribution process: Beginning with the marked box and proceeding counter-clockwise, collect one chip from each box until we encounter an empty box. Place all the collected chips in the empty box and mark it. This state is the desired predecessor. (b) It is indeed possible to get any distribution desired. First, the result from (a) shows that we can undo any move by mindlessly performing the forced moves prescribed for part (a). Second, note that it is possible to go from any distribution to the boring distribution with all chips in one box. This shows that every pair of distributions is connected by a sequence of moves passing through the boring distribution, as desired.