Let be a positive integer. We start with piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of ) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.
Problem 1711
Official solution
To solve this problem, we need to determine the smallest number of nonempty piles of pebbles that can be obtained when starting with piles, each with one pebble, by performing a series of moves. In each move, we choose two piles, take an equal number of pebbles from each, and form a new pile with these pebbles.
Step 1: Understanding the Moves
Each move involves:
- Selecting two piles, say with and pebbles each.
- Removing pebbles from each pile ().
- Forming a new pile with the pebbles removed.
The total number of pebbles in the system remains constant at . After such a move, the number of piles changes as follows: two piles are reduced by pebbles each, and a new pile of size is created.
Step 2: Characterizing Optimal Configuration
When is a power of 2, it is possible to perform moves such that all pebbles are eventually concentrated into a single pile. This can be achieved through successive pairings:
- Start with piles of pebble and combine them to get pile with pebbles.
- Now pair this pebble pile with another pebble pile to get a pile of pebbles.
- Continue doubling in this way until all pebbles are in one pile.
Thus, for such cases:
When is not a power of 2, pairing cannot result in a single pile because repeatedly dividing by 2 will not terminate at 1. In this situation, regardless of the moves, we are unable to end up with just a single pile, but we can reach a state with exactly two piles:
- Use binary representation: every positive integer can be expressed as a sum of distinct powers of 2.
- If is not a power of 2, this decomposition into powers of 2 has more than one term.
- Therefore, we can make moves such that pebbles eventually consolidate into two piles, each representing the largest possible sum of grouping the binary terms.
Hence, when is not a power of two, the minimum number of piles is:
Final Solution
The smallest number of nonempty piles possible, depending on whether is a power of 2 or not, is given by: