The positive integers from 1 to \(n\) are arranged in a sequence, initially in ascending order. In one move, we can swap the positions of two of the numbers, provided they share a common divisor greater than 1. Let \(s_n\) be the number of sequences that can be obtained with a finite number of moves. Prove that \(s_n = a_n!\), where the sequence of positive integers \((a_n)_{n\geq 1}\) is such that for any \(\delta > 0\), there exists an integer \(N\), for which for all \(n\geq N\), the following is true: \[ n - \left(\frac{1}{2}+\delta\right)\frac{n}{\log n} < a_n < n - \left(\frac{1}{2}-\delta\right)\frac{n}{\log n}. \]
Problem
Source: XIII International Festival of Young Mathematicians Sozopol 2024, Theme for 10-12 grade
Tags: combinatorics