Let be a positive integer. Ana and Banana are playing the following game:
First, Ana arranges 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?
Problem 1355
Official solution
1. Understanding the Problem:
- We have 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 .
- Assume the ball is initially under cup and the hole is under cup .
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 possible positions for the ball and possible positions for the hole.
- This gives us 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 .
8. Calculation:
- Therefore, the number of swaps required is .
9. Final Move:
- After determining the configuration, one additional move is required to place the ball into the hole.
10. Total Number of Commands:
Conclusion: