On a table, ten boxes can be found, each containing some coins. The arrangement of the coins can be changed in two ways. One option is to take one coin from each of nine boxes and put these nine coins into the tenth box. The other is the reverse of this: take nine coins from one box and distribute them one by one among the other nine. It is allowed to have empty boxes after a move, but it is not possible to take a coin from an empty box. Initially, the boxes contain coins respectively. Can we achieve that the number of coins in any two boxes is different? (H)
Solution
Let's examine how the remainder of the number of coins in the purses changes with each step when divided by 10. When we take one coin from each of nine purses and put it into the tenth, the remainder decreases by 1 for each purse; in the other type of step, it increases by 1. The key is that the remainders change in the same way: they either increase or decrease by 1.
Suppose we manage to achieve that the number of coins in any two purses is different. Initially, the remainders are: ; that is, five different remainders appear, and each one exactly twice. According to the above, this will also be true in the final state.
Let's examine how many coins must be in the purses in total! The number of coins in purses with the same remainder differs by at least ten, and since a negative number of coins is not possible, there must be at least
coins in total in the purses. Initially, however, there were only 60, which means we could not have achieved our goal, and the answer to the question of the problem is negative.
Based on the work of Csaba Megyeri (Nagykanizsa, Batthyány L. Gymnasium, III. grade)
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.