Found problems: 100
2024 Miklos Schweitzer, 4
Let $\pi$ be a given permutation of the set $\{1, 2, \dots, n\}$. Determine the smallest possible value of
\[
\sum_{i=1}^n |\pi(i) - \sigma(i)|,
\]
where $\sigma$ is a permutation chosen from the set of all $n$-cycles. Express the result in terms of the number and lengths of the cycles in the disjoint cycle decomposition of $\pi$, including the fixed points.
2017 Pan-African Shortlist, I4
Find the maximum and minimum of the expression
\[
\max(a_1, a_2) + \max(a_2, a_3), + \dots + \max(a_{n-1}, a_n) + \max(a_n, a_1),
\]
where $(a_1, a_2, \dots, a_n)$ runs over the set of permutations of $(1, 2, \dots, n)$.
2016 IMC, 5
Let $S_n$ denote the set of permutations of the sequence $(1,2,\dots, n)$. For every permutation $\pi=(\pi_1, \dots, \pi_n)\in S_n$, let $\mathrm{inv}(\pi)$ be the number of pairs $1\le i < j \le n$ with $\pi_i>\pi_j$; i. e. the number of inversions in $\pi$. Denote by $f(n)$ the number of permutations $\pi\in S_n$ for which $\mathrm{inv}(\pi)$ is divisible by $n+1$.
Prove that there exist infinitely many primes $p$ such that $f(p-1)>\frac{(p-1)!}{p}$, and infinitely many primes $p$ such that $f(p-1)<\frac{(p-1)!}{p}$.
(Proposed by Fedor Petrov, St. Petersburg State University)
1997 ITAMO, 5
Let $X$ be the set of natural numbers whose all digits in the decimal representation are different. For $n \in N$, denote by $A_n$ the set of numbers whose digits are a permutation of the digits of $n$, and $d_n$ be the greatest common divisor of the numbers in $A_n$. (For example, $A_{1120} =\{112,121,...,2101,2110\}$, so $d_{1120} = 1$.)
Find the maximum possible value of $d_n$.
2007 Nicolae Păun, 3
In the following exercise, $ C_G (e) $ denotes the centralizer of the element $ e $ in the group $ G. $
[b]a)[/b] Prove that $ \max_{\sigma\in S_n\setminus\{1\}} \left| C_{S_n} (\sigma ) \right| <\frac{n!}{2} , $ for any natural number $ n\ge 4. $
[b]b)[/b] Show that $ \lim_{n\to\infty} \left(\frac{1}{n!}\cdot\max_{\sigma\in S_n\setminus\{1\}} \left| C_{S_n} (\sigma ) \right|\right) =0. $
[i]Alexandru Cioba[/i]
2015 Romania Team Selection Tests, 3
Let $n$ be a positive integer . If $\sigma$ is a permutation of the first $n$ positive integers , let $S(\sigma)$ be the set of all distinct sums of the form $\sum_{i=k}^{l} \sigma(i)$ where $1 \leq k \leq l \leq n$ .
[b](a)[/b] Exhibit a permutation $\sigma$ of the first $n$ positive integers such that $|S(\sigma)|\geq \left \lfloor{\frac{(n+1)^2}{4}}\right \rfloor $.
[b](b)[/b] Show that $|S(\sigma)|>\frac{n\sqrt{n}}{4\sqrt{2}}$ for all permutations $\sigma$ of the first $n$ positive integers .
1979 Romania Team Selection Tests, 3.
Let $M_n$ be the set of permutations $\sigma\in S_n$ for which there exists $\tau\in S_n$ such that the numbers
\[\sigma (1)+\tau(1),\, \sigma(2)+\tau(2),\ldots,\sigma(n)+\tau(n),\]
are consecutive. Show that \((M_n\neq \emptyset\Leftrightarrow n\text{ is odd})\) and in this case for each $\sigma_1,\sigma_2\in M_n$ the following equality holds:
\[\sum_{k=1}^n k\sigma_1(k)=\sum_{k=1}^n k\sigma_2(k).\]
[i]Dan Schwarz[/i]
2023 IMC, 5
Fix positive integers $n$ and $k$ such that $2 \le k \le n$ and a set $M$ consisting of $n$ fruits. A [i]permutation[/i] is a sequence $x=(x_1,x_2,\ldots,x_n)$ such that $\{x_1,\ldots,x_n\}=M$. Ivan [i]prefers[/i] some (at least one) of these permutations. He realized that for every preferred permutation $x$, there exist $k$ indices $i_1 < i_2 < \ldots < i_k$ with the following property: for every $1 \le j < k$, if he swaps $x_{i_j}$ and $x_{i_{j+1}}$, he obtains another preferred permutation.
\\ Prove that he prefers at least $k!$ permutations.
2005 Gheorghe Vranceanu, 1
Let be a natural number $ n\ge 2 $ and the $ n\times n $ matrix whose entries at the $ \text{i-th} $ line and $ \text{j-th} $ column is $ \min (i,j) . $ Calculate:
[b]a)[/b] its determinant.
[b]b)[/b] its inverse.
2020 Regional Olympiad of Mexico Northeast, 3
A permutation of the integers \(2020, 2021,...,2118, 2119\) is a list \(a_1,a_2,a_3,...,a_{100}\) where each one of the numbers appears exactly once. For each permutation we define the partial sums.
$s_1=a_1$
$s_2=a_1+a_2$
$s_3=a_1+a_2+a_3$
$...$
$s_{100}=a_1+a_2+...+a_{100}$
How many of these permutations satisfy that none of the numbers \(s_1,...,s_{100}\) is divisible by $3$?
2017 China National Olympiad, 4
Let $n \geq 2$ be a natural number. For any two permutations of $(1,2,\cdots,n)$, say $\alpha = (a_1,a_2,\cdots,a_n)$ and $\beta = (b_1,b_2,\cdots,b_n),$ if there exists a natural number $k \leq n$ such that
$$b_i = \begin{cases} a_{k+1-i}, & \text{ }1 \leq i \leq k; \\ a_i, & \text{} k < i \leq n, \end{cases}$$
we call $\alpha$ a friendly permutation of $\beta$.
Prove that it is possible to enumerate all possible permutations of $(1,2,\cdots,n)$ as $P_1,P_2,\cdots,P_m$ such that for all $i = 1,2,\cdots,m$, $P_{i+1}$ is a friendly permutation of $P_i$ where $m = n!$ and $P_{m+1} = P_1$.
2005 Bosnia and Herzegovina Team Selection Test, 5
If for an arbitrary permutation $(a_1,a_2,...,a_n)$ of set ${1,2,...,n}$ holds $\frac{{a_k}^2}{a_{k+1}}\leq k+2$,
$k=1,2,...,n-1$, prove that $a_k=k$ for $k=1,2,...,n$
2012 IFYM, Sozopol, 1
Let $n\in \mathbb{N}$ be a number multiple of 4. We take all permutations $(a_1,a_2...a_n)$ of the numbers $(1,2...n)$, for which $\forall j$, $a_i+j=n+1$ where $i=a_j$. Prove that there exist $\frac{(\frac{1}{2}n)!}{(\frac{1}{4}n)!}$ such permutations.
2021 Kyiv City MO Round 1, 10.2
The $1 \times 1$ cells located around the perimeter of a $4 \times 4$ square are filled with the numbers $1,
2, \ldots, 12$ so that the sums along each of the four sides are equal. In the upper left corner cell is the number $1$, in the upper right - the number $5$, and in the lower right - the number $11$.
[img]https://i.ibb.co/PM0ry1D/Kyiv-City-MO-2021-Round-1-10-2.png[/img]
Under these conditions, what number can be located in the last corner cell?
[i]Proposed by Mariia Rozhkova[/i]
1987 IMO, 1
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.
2010 ELMO Shortlist, 1
For a permutation $\pi$ of $\{1,2,3,\ldots,n\}$, let $\text{Inv}(\pi)$ be the number of pairs $(i,j)$ with $1 \leq i < j \leq n$ and $\pi(i) > \pi(j)$.
[list=1]
[*] Given $n$, what is $\sum \text{Inv}(\pi)$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$?
[*] Given $n$, what is $\sum \left(\text{Inv}(\pi)\right)^2$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$?[/list]
[i]Brian Hamrick.[/i]
2006 Germany Team Selection Test, 3
Suppose that $ a_1$, $ a_2$, $ \ldots$, $ a_n$ are integers such that $ n\mid a_1 \plus{} a_2 \plus{} \ldots \plus{} a_n$.
Prove that there exist two permutations $ \left(b_1,b_2,\ldots,b_n\right)$ and $ \left(c_1,c_2,\ldots,c_n\right)$ of $ \left(1,2,\ldots,n\right)$ such that for each integer $ i$ with $ 1\leq i\leq n$, we have
\[ n\mid a_i \minus{} b_i \minus{} c_i
\]
[i]Proposed by Ricky Liu & Zuming Feng, USA[/i]
2017 Kyiv Mathematical Festival, 1
Several dwarves were lined up in a row, and then they lined up in a row in a different order. Is it possible that exactly one third of the dwarves have both of their neighbours remained and exactly one third of the dwarves have only one of their neighbours remained, if the number of the dwarves is a) 6; b) 9?
1988 Tournament Of Towns, (190) 3
Let $a_1 , a_2 ,... , a_n$ be an arrangement of the integers $1,2,..., n$. Let $$S=\frac{a_1}{1}+\frac{a_2}{2}+\frac{a_3}{3}+...+\frac{a_n}{1}.$$ Find a natural number $n$ such that among the values of $S$ for all arrangements $a_1 , a_2 ,... , a_n$ , all the integers from $n$ to $n + 100$ appear .
2024 Kyiv City MO Round 2, Problem 4
There are $n \geq 1$ notebooks, numbered from $1$ to $n$, stacked in a pile. Zahar repeats the following operation: he randomly chooses a notebook whose number $k$ does not correspond to its location in this stack, counting from top to bottom, and returns it to the $k$th position, counting from the top, without changing the location of the other notebooks. If there is no such notebook, he stops.
Is it guaranteed that Zahar will arrange all the notebooks in ascending order of numbers in a finite number of operations?
[i]Proposed by Zahar Naumets[/i]
2018 Puerto Rico Team Selection Test, 2
Let $A = \{a_1, a_2, a_3, a_4, a_5\}$ be a set of $5$ positive integers.
Show that for any rearrangement of $A$, $a_{i1}$, $a_{i2}$, $a_{i3}$, $a_{i4}$, $a_{i5}$, the product $$(a_{i1} -a_1) (a_{i2} -a_2) (a_{i3} -a_3) (a_{i4} -a_4) (a_{i5} -a_5)$$
is always even.
2020 IMEO, Problem 4
Anna and Ben are playing with a permutation $p$ of length $2020$, initially $p_i = 2021 - i$ for $1\le i \le 2020$. Anna has power $A$, and Ben has power $B$. Players are moving in turns, with Anna moving first.
In his turn player with power $P$ can choose any $P$ elements of the permutation and rearrange them in the way he/she wants.
Ben wants to sort the permutation, and Anna wants to not let this happen. Determine if Ben can make sure that the permutation will be sorted (of form $p_i = i$ for $1\le i \le 2020$) in finitely many turns, if
a) $A = 1000, B = 1000$
b) $A = 1000, B = 1001$
c) $A = 1000, B = 1002$
[i]Anton Trygub[/i]
1999 Kazakhstan National Olympiad, 8
Let $ {{a} _ {1}}, {{a} _ {2}}, \ldots, {{a} _ {n}} $ be permutation of numbers $ 1,2, \ldots, n $, where $ n \geq 2 $.
Find the maximum value of the sum $$ S (n) = | {{a} _ {1}} - {{a} _ {2}} | + | {{a} _ {2}} - {{a} _ {3}} | + \cdots + | {{a} _ {n-1}} - {{a} _ {n}} |. $$
1987 IMO Shortlist, 16
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.[i](IMO Problem 1)[/i]
[b][i]Original formulation [/i][/b]
Let $S$ be a set of $n$ elements. We denote the number of all permutations of $S$ that have exactly $k$ fixed points by $p_n(k).$ Prove:
(a) $\sum_{k=0}^{n} kp_n(k)=n! \ ;$
(b) $\sum_{k=0}^{n} (k-1)^2 p_n(k) =n! $
[i]Proposed by Germany, FR[/i]
2010 USAJMO, 1
A [i]permutation[/i] of the set of positive integers $[n] = \{1, 2, . . . , n\}$ is a sequence $(a_1 , a_2 , \ldots, a_n ) $ such that each element of $[n]$ appears precisely one time as a term of the sequence. For example, $(3, 5, 1, 2, 4)$ is a permutation of $[5]$. Let $P (n)$ be the number of permutations of $[n]$ for which $ka_k$ is a perfect square for all $1 \leq k \leq n$. Find with proof the smallest $n$ such that $P (n)$ is a multiple of $2010$.