Problem 9 · 2016 Math Kangaroo
Medium
Counting & Probability
careful-counting
Step by step the word VELO is changed into the word LOVE. In every step two adjacent letters are allowed to be swapped around. What is the minimum amount of steps needed?
Show answer
Answer: B — 4
Show hints
Hint 1 of 2
Number the target positions and look at how out of order the start is.
Still stuck? Show hint 2 →
Hint 2 of 2
The fewest adjacent swaps equals the number of inversions.
Show solution
Approach: count inversions
- Target LOVE means positions L,O,V,E; the start VELO reads as 3,4,1,2 in that order.
- The out-of-order pairs are (3,1),(3,2),(4,1),(4,2) — four of them.
- So the minimum number of swaps is 4.
Mark:
· log in to save