There are empty red and empty white baskets. At each step we choose one red and one white basket and add equal amounts of water into two chosen baskets. It was observed that after finite number of steps all baskets are non empty and any two baskets simultaneously chosen at some step contain equal amounts of water. Find all possible values of .
Turkey — Team Selection Test
Solution
Answer: .
is obviously possible: partition all baskets into pairs of red and white baskets and in each of steps choose baskets from some new pair and add any amount of water into chosen baskets.
Now let us show that is the only possible value. Define a graph on vertices where each vertex corresponds to some basket and there is an edge between two vertices if and only if baskets corresponding to these vertices are chosen at some step. Consider some connected component of the graph. In let and be the total number of vertices corresponding to red and white baskets, respectively and let and be the total amount of water in vertices corresponding to red and white baskets, respectively. Since is connected and in each step we add equal amount of water into chosen baskets we have . Since any two vertices of are path connected, in any two baskets corresponding to two vertices of there are equal amounts of water. Then implies . Since for any we are done.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.