MathDB

9.7

Part of 2021 Ukraine National Mathematical Olympiad

Problems(1)

Line them up

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

12/21/2023
The All-Ukrainian Mathematical Olympiad was attended by 100100 children from 1010 regions of Ukraine, 1010 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 11 second. (You can only swap one pair of children per second).
For which shortest time TT 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
combinatoricsInversion