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
Problem
Source: 2024 China MO, Day 2, Problem 6
Tags: combinatorics
29.11.2023 17:48
Related Problem: 1990 Vietnam TST P6.
02.12.2023 00:43
Is there any solution
03.12.2023 10:49
2401, is it right? It seems impossible for me to prove.
03.12.2023 11:39
Is this true? Let G be a directed graph with 2k+1 vertices where there is at most one directed edge (arrow) between each pair of vertices. Suppose the arrows are transitive, meaning that a \to b, b\to c implies a \to c, and the indegree and outdegree of any vertex are <=k, then there are at most k^2 arrows.
03.12.2023 11:42
hellnish wrote: 2401, is it right? It seems impossible for me to prove. The answer is exactly 2401
09.01.2024 19:49
I hope this is correct
11.07.2024 09:48
I think the proposer Zhenhua Qu underestimated the difficulty of this problem. Only 2 people (all this year's IMO team member) solved this in the contest but non got full score.