what is the smallest number of commands

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

what is the smallest number of commands

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 7th European Mathematical Cup , Junior Category, Q4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

41026 posts

sqing

#1 h Dec 25, 2018, 10:18 AM • 2 Y

Y by AwesomeYRY, Adventure10

Let $n$ be a positive integer. Ana and Banana are playing the following game:
First, Ana arranges $2n$ 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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1446 posts

#2 h Jan 5, 2019, 3:11 AM • 1 Y

Y by Adventure10

Each swap decreases one such configuration as a possibility. As we start with one known configuration, it will take at most $\binom{2n}{2} - 1 = 2n^2 - n - 1$ swaps to "determine" where the hole is. We then take one additional move to put the ball in the hole, making a total of $\boxed{2n^2 - n}$ . I'm not quite sure how to prove that sometimes it will require this many moves.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#3 h Jan 5, 2019, 6:49 PM • 5 Y

Y by danepale, WindTheorist, AwesomeYRY, adityaguharoy, Adventure10

The answer is $3n^2 - 2n$ . Have Banana (pretend to) procure $2n$ different balls, arranged in a row and numbered from 1 to $2n$ in left to right order. Whenever Banana calls out a move to Ana, she swaps the balls in the corresponding positions in her own row. Forgetting about Ana, Banana's goal is to make it so that each of her $2n$ balls occupies every position at some point in time.

First, we'll show the lower bound. Mark a ball with L if it visited position 1 before position $2n$ , and mark it with R otherwise. Each pair of balls with the same letter (both L or both R) must swap with each other at least twice. Each pair of balls with different letters (one L and one R) must swap with each other at least once. Let $m_L$ be the total number of L balls and $m_R$ be the total number of R balls. Then we have shown that at least
$\binom{m_L}{2} + \binom{m_R}{2} + \binom{2n}{2}$ moves are required. By convexity and $m_L + m_R = 2n$ , this is minimized for $m_L = m_R = n$ . The above simplifies to $3n^2 - 2n$ , our claimed answer.

Now we just need to show this is obtainable.
Step 1: For $1 \leq i \leq n-1$ in order, take ball $2n-i$ , still in its initial position, and move it right $i$ times. After this, the configuration is $1, 2, \ldots, n, 2n, 2n-1, \ldots, n+1$ . All of balls $n+1$ to $2n$ inclusive have visited position $2n$ .
Step 2: For $1 \leq i \leq n$ in order, take ball $i$ , currently in the leftmost position, and move it right $2n-1$ times. After all of this, the configuration is $2n, 2n-1, \ldots, n+1, 1, 2, \ldots, n$ . The only thing left to do is have balls $n+1$ to $2n$ inclusive visit position 1.
Step 3: For $1 \leq i \leq n-1$ in order, take ball $2n-i$ , currently in position $i+1$ , and move it left $i$ times. All balls have now visited both 1 and $2n$ , which implies they have visited every position.

Both steps 1 and 3 needed $\frac{n(n-1)}{2}$ moves, and step 2 needed $2n^2 - n$ moves. Adding these up gives $3n^2 - 2n$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#4 h Aug 24, 2021, 8:55 PM • 2 Y

Y by Jalil_Huseynov, DrYouKnowWho

We claim the answer is $3n^2-2n$ . Note that this problem is equivalent to finding the number of swaps needed to make all cups visit all positions.

We first show this value is necessary. Label the positions from $1,2,\ldots 2n$ . Firstly, clearly all $\binom{2n}{2}$ pairs of cups must be swapped at some point (can't jump over). Next, we claim that each cup $I$ starting at position $i$ will swap twice with either the cups in the set $\{1,2,\ldots i-1\}$ or $\{i+1,\ldots, 2n\}$ . This is clearly true because the cups along the way from $I$ to the first endpoint it reaches will be swapped twice. Thus, by double counting, the minimum number of pairs of cups that are swapped twice is at least
$\text{(A,B) where A is closer to endpoint} \geq \sum_{i=1}^{2n} \min(i-1,2n-i) = 1+\cdots + (n-1)+(n-1) + \cdots+1 = n^2-n$ Thus, in total at least $\binom{2n}{2}+n^2-n = n(2n-1)+n^2-n = 3n^2-2n$ cups are needed. $\blacksquare$ .

We now provide a construction. It consists of two phases.

Phase 1: In $n^2-n$ moves we flip $(1,2,\ldots n),(n+1,\ldots 2n)$ into $(n,n-1,\ldots,1)(2n,2n-1,\ldots n+1)$ . We do the $[1,n]$ case, the other one is symmetric. For $i\geq 2, i\leq n$ , use swaps to directly send cup $i$ to position 1. This will take $1+\cdots n-1 = \frac{n(n-1)}{2}$ moves, and means that each cup $\leq n$ will only need to go rightwards. $\square$ .

Phase 2: In each of $n$ iterations, we send the central pair $(i,2n-i+1)$ to the endpoints $(i \to 2n, 2n-i+1\to 1)$ . this will always take $1+2\cdot (n-1)=2n-1$ moves for each iteration, for a total of $n\cdot (2n-1)$ , and this clearly takes each cup through each position. $\square$ .

Thus, we have provided a bound and a construction, so we have shown that the answer is $3n^2-2n$ and we're done. $\blacksquare$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a