Problem

Source: Ukrainian Mathematical Olympiad 2021. Day 2, Problem 9.7

Tags: combinatorics, Inversion



The All-Ukrainian Mathematical Olympiad was attended by $100$ children from $10$ regions of Ukraine, $10$ children from each region. At the opening ceremony, they stood in one row on the stage, but not all children from the same region stood consecutively. Two neighboring children from different regions can be swapped in $1$ second. (You can only swap one pair of children per second). For which shortest time $T$ is it always possible to make sure that the children are lined up by the regions? The regions can go in any order. Proposed by Anton Trygub