Maths Olympiad Prep

Track / Stage 6 / 355 of 400 #1355 of 1964

Problem 1355

National olympiad, first round
Combinatorics Difficulty 6.8 Find the answer

Let nn be a positive integer. Ana and Banana are playing the following game:
First, Ana arranges 2n2n cups in a row on a table, each facing upside-down. She then places a ball under a cup
and makes a hole in the table under some other cup. Banana then gives a finite sequence of commands to Ana,
where each command consists of swapping two adjacent cups in the row.
Her goal is to achieve that the ball has fallen into the hole during the game. Assuming Banana has no information
about the position of the hole and the position of the ball at any point, what is the smallest number of commands
she has to give in order to achieve her goal?

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

Official solution

1. Understanding the Problem:
- We have 2n2n cups arranged in a row.
- One cup has a ball underneath it.
- Another cup has a hole underneath it.
- Banana's goal is to give a sequence of commands to swap adjacent cups such that the ball falls into the hole.

2. Initial Configuration:
- Let's denote the cups as C1,C2,,C2nC_1, C_2, \ldots, C_{2n}.
- Assume the ball is initially under cup CiC_i and the hole is under cup CjC_j.

3. Swapping Mechanism:
- Each command swaps two adjacent cups.
- The position of the ball and the hole relative to the cups changes with each swap.

4. Objective:
- The goal is to ensure that the ball falls into the hole, which means the ball and the hole must be under the same cup after some sequence of swaps.

5. Counting the Number of Configurations:
- Initially, there are 2n2n possible positions for the ball and 2n2n possible positions for the hole.
- This gives us 2n×2n=4n22n \times 2n = 4n^2 possible configurations.

6. Reduction of Configurations:
- Each swap changes the configuration of the cups.
- To ensure that the ball falls into the hole, we need to consider the worst-case scenario where we need to explore all possible configurations.

7. Number of Swaps Required:
- In the worst case, we need to explore all possible configurations except one (since we start with one known configuration).
- The number of swaps required to explore all configurations is given by (2n2)1\binom{2n}{2} - 1.

8. Calculation:
(2n2)=(2n)(2n1)2=2n2n \binom{2n}{2} = \frac{(2n)(2n-1)}{2} = 2n^2 - n
- Therefore, the number of swaps required is 2n2n12n^2 - n - 1.

9. Final Move:
- After determining the configuration, one additional move is required to place the ball into the hole.

10. Total Number of Commands:
2n2n1+1=2n2n 2n^2 - n - 1 + 1 = 2n^2 - n

Conclusion:
2n2n \boxed{2n^2 - n}

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