Maths Olympiad Prep

Library / /49 of 144

Combinatorics Difficulty 8.0 Shortlist Find the answer

Let nn be a positive integer. We start with nn 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 nn) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine the smallest number of nonempty piles of pebbles that can be obtained when starting with n n 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 a a and b b pebbles each.
- Removing k k pebbles from each pile (1kmin(a,b) 1 \leq k \leq \min(a, b) ).
- Forming a new pile with the 2k 2k pebbles removed.

The total number of pebbles in the system remains constant at n n . After such a move, the number of piles changes as follows: two piles are reduced by k k pebbles each, and a new pile of size 2k 2k is created.

Step 2: Characterizing Optimal Configuration

When n n 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 2 2 piles of 1 1 pebble and combine them to get 1 1 pile with 2 2 pebbles.
- Now pair this 2 2 pebble pile with another 2 2 pebble pile to get a pile of 4 4 pebbles.
- Continue doubling in this way until all pebbles are in one pile.

Thus, for such cases:
1 \boxed{1}

When n n 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 n n 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 n n is not a power of two, the minimum number of piles is:
2 \boxed{2}

Final Solution

The smallest number of nonempty piles possible, depending on whether n n is a power of 2 or not, is given by:
{1if n is a power of 22otherwise. \boxed{ \begin{cases} 1 & \text{if }n\text{ is a power of }2 \\ 2 & \text{otherwise} \end{cases} }.

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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.