The following operation is allowed on several given nonnegative integers. A positive number is chosen among them, and each number is replaced by , including the choice itself. Starting with , after several operations numbers with sum are obtained. What can these numbers be? Find all possibilities
Solution
Call the set a block, for ; for consistency assume that is the empty block. Suppose that several numbers can be partitioned into blocks. The key observation is that the same holds true after any operation is applied. Indeed let be one of the blocks, and let denote the operation applied to number . If then remains unchanged. If then is replaced by the blocks and . The claim is justified.
Since the initial numbers form a block, it follows that one has a disjoint union of blocks after any number of operations. The sum of the block is , so if the total sum is then the blocks participating can be only , , , , with sums respectively. So the question reduces to representing as a sum of several numbers among . The possibilities are
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.