Concours X ENS 24: mathématiques A MP
With the competitive entrance exam season in full swing, today we turn our attention to the prestigious X competitive entrance exam, with this problem A section MP common to the Ecole Normale competitive entrance exam.
Linear algebra is really reduced to a minimum in this problem, which is ultimately more an analysis problem with series and asymptotic developments. We tackle the symmetric group \(\mathfrak{S}_n\), counting and arithmetic.
The problem is difficult, of course, but doable because it's very well guided.
The two parts are totally independent, but the problem cleverly contrasts two beautiful results that have certain similarities, as do the proofs.
In the first part, we estimate the number of cycles involved in the decomposition of a permutation into disjointly supported cycles. Fixed points are counted as cycles of length 1.
Theorem: Let \(X_n\) be the random variable that counts the number of cycles involved in the decomposition of a randomly chosen permutation \(\sigma\in\mathfrak{S}_n\). \[\begin{array}{rl} \exists C>0\quad \forall \epsilon>0\quad\forall n\geqslant 2,\quad P(\abs{X_n-\ln n}\geqslant \epsilon\ln n) & \leqslant \frac{C}{\epsilon^2\ln n}\ \end{array}\]
In particular, VA \(\frac{X_n}{\ln n}\) converges in probability to 1.
In the second part, we move on to the decomposition of an integer into prime factors, and count the prime factors involved in the decomposition.
Theorem: \[\begin{array}{rCl} \omega(n) = \#\{p\text{ premier},\quad p\mid n \} & \underset{n\to+\infty}{\sim}& \ln(\ln n)\ \end{array}\] except maybe on a set \(\mathscr{S}\) of zero density.
An illustration of the idea in question 10, with \(n=6\) and \(\sigma(1)=j=3\):
Answers to the Maths A test on April 15 in MP concours X ENS 2024:
Problem statement: