Swapping blocks of equal number of elements
Source: MEMO 2022 T3
September 2, 2022
combinatorics
Problem Statement
Let be a positive integer. There are purple and white cows queuing in a line in some order. Tim wishes to sort the cows by colour, such that all purple cows are at the front of the line. At each step, he is only allowed to swap two adjacent groups of equally many consecutive cows. What is the minimal number of steps Tim needs to be able to fulfill his wish, regardless of the initial alignment of the cows?