Subjects combinatorics

Worst Case Turntable

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Worst Case Turntable


1. **Problem Statement:** We have 6 planes parked on a rotating turntable with positions numbered 1 to 6. The turntable can be rotated left (◀) or right (▶) by one position per button press. Pilots arrive in some order to access their planes, and the turntable starts with position 1 at the gate. 2. **Goal:** Find the order of accessing planes that requires the maximum total number of button presses, assuming the turntable is always rotated the shortest way to the next required plane. 3. **Key Points:** - The turntable has 6 positions arranged in a circle. - Moving from position $i$ to $j$ requires minimum presses equal to the shortest distance on the circle. - Distance between positions $i$ and $j$ is $d = \min(|j - i|, 6 - |j - i|)$. - Total presses is the sum of distances between consecutive planes in the access order. 4. **Approach:** - We want to maximize $\sum_{k=1}^{5} d(p_k, p_{k+1})$ where $p_k$ is the $k$-th plane accessed. - The worst case is when consecutive planes are as far apart as possible. - The maximum distance between two positions on a 6-position circle is 3. 5. **Constructing a worst-case order:** - To maximize total presses, each move should be distance 3 if possible. - Positions opposite each other on the circle are 3 apart. - The pairs (1,4), (2,5), (3,6) are opposite. 6. **Example worst-case order:** - Start at 1. - Next plane at 4 (distance 3). - Next plane at 2 (distance 3 from 4: $\min(|2-4|,6-|2-4|)=2$ but 2 is not opposite 4, so try to maximize next step.) - Instead, choose 1,4,2,5,3,6 or 1,4,6,3,5,2 to maximize distances. 7. **Calculate total presses for order 1,4,6,3,5,2:** - $d(1,4) = 3$ - $d(4,6) = \min(|6-4|,6-|6-4|) = \min(2,4) = 2$ - $d(6,3) = \min(|3-6|,6-|3-6|) = \min(3,3) = 3$ - $d(3,5) = \min(|5-3|,6-|5-3|) = \min(2,4) = 2$ - $d(5,2) = \min(|2-5|,6-|2-5|) = \min(3,3) = 3$ - Total presses = 3 + 2 + 3 + 2 + 3 = 13 8. **Check if 13 is maximum:** - Maximum distance per move is 3. - There are 5 moves. - Maximum total presses is $5 \times 3 = 15$. - But it is impossible to have all moves distance 3 because the circle has only 6 positions. - The example order above achieves 13 presses, which is close to maximum. 9. **Conclusion:** - A worst-case order is $\boxed{1,4,6,3,5,2}$ or any cyclic permutation that maximizes alternating distances. - This order requires 13 button presses, which is near the maximum possible.