Problem

Source: 2024 China MO, Day 2, Problem 6

Tags: combinatorics



Let $P$ be a regular $99$-gon. Assign integers between $1$ and $99$ to the vertices of $P$ such that each integer appears exactly once. (If two assignments coincide under rotation, treat them as the same. ) An operation is a swap of the integers assigned to a pair of adjacent vertices of $P$. Find the smallest integer $n$ such that one can achieve every other assignment from a given one with no more than $n$ operations. Proposed by Zhenhua Qu