Swapping Red and Blue Blocks
Source: SMO Junior 2019 Q5
June 29, 2019
combinatorics
Problem Statement
Let be a positive integer and consider an arrangement of blocks in a straight line, where of them are red and the rest blue. A swap refers to choosing two consecutive blocks and then swapping their positions. Let be the minimum number of swaps needed to make the first blocks all red and be the minimum number of swaps needed to make the first blocks all blue. Show that is independent of the starting arrangement and determine its value.