Found problems: 100
2011 Gheorghe Vranceanu, 1
Let $ \sigma_1 ,\sigma_2 $ be two permutations of order $ n $ such that $ \sigma_1 (k)=\sigma_2 (n-k+1) $ for $ k=\overline{1,n} . $ Prove that the number of inversions of $ \sigma_1 $ plus the number of inversions of $ \sigma_2 $ is $ \frac{n(n+1)}{2} . $
2022 CIIM, 4
Given a positive integer $n$, determine how many permutations $\sigma$ of the set $\{1, 2, \ldots , 2022n\}$ have the following property: for each $i \in \{1, 2, \ldots , 2021n + 1\}$, the number $$\sigma(i) + \sigma(i + 1) + \cdots + \sigma(i + n - 1)$$ is a multiple of $n$.
1984 Tournament Of Towns, (077) 2
A set of numbers $a_1, a_2 , . . . , a_{100}$ is obtained by rearranging the numbers $1 , 2,..., 100$ . Form the numbers
$b_1=a_1$
$b_2= a_1 + a_2$
$b_3=a_1 + a_2 + a_3$
...
$b_{100}=a_1 + a_2 + ...+a_{100}$
Prove that among the remainders on dividing the numbers by $100 , 11$ of them are different .
( L . D . Kurlyandchik , Leningrad)
1992 India National Olympiad, 4
Find the number of permutations $( p_1, p_2, p_3 , p_4 , p_5 , p_6)$ of $1, 2 ,3,4,5,6$ such that for any $k, 1 \leq k \leq 5$, $(p_1, \ldots, p_k)$ does not form a permutation of $1 , 2, \ldots, k$.
2013 India IMO Training Camp, 1
Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order.
We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.
2010 Contests, 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$.
2016 Iran MO (3rd Round), 1
Find the number of all $\text{permutations}$ of $\left \{ 1,2,\cdots ,n \right \}$ like $p$ such that there exists a unique $i \in \left \{ 1,2,\cdots ,n \right \}$ that :
$$p(p(i)) \geq i$$
2012 Dutch IMO TST, 4
Let $n$ be a positive integer divisible by $4$. We consider the permutations $(a_1, a_2,...,a_n)$ of $(1,2,..., n)$ having the following property: for each j we have $a_i + j = n + 1$ where $i = a_j$ . Prove that there are exactly $\frac{ (\frac12 n)!}{(\frac14 n)!}$ such permutations.
2011 IFYM, Sozopol, 4
Let $n$ be some natural number. One boss writes $n$ letters a day numerated from 1 to $n$ consecutively. When he writes a letter he piles it up (on top) in a box. When his secretary is free, she gets the letter on the top of the pile and prints it. Sometimes the secretary isn’t able to print the letter before her boss puts another one or more on the pile in the box. Though she is always able to print all of the letters at the end of the day.
A permutation is called [i]“printable”[/i] if it is possible for the letters to be printed in this order. Find a formula for the number of [i]“printable”[/i] permutations.
1958 November Putnam, B7
Let $a_1 ,a_2 ,\ldots, a_n$ be a permutation of the integers $1,2,\ldots, n.$ Call $a_i$ a [i]big[/i] integer if $a_i >a_j$ for all $i<j.$ Find the mean number of big integers over all permutations on the first $n$ postive integers.
2017 Romania Team Selection Test, P2
Let $n$ be a positive integer, and let $S_n$ be the set of all permutations of $1,2,...,n$. let $k$ be a non-negative integer, let $a_{n,k}$ be the number of even permutations $\sigma$ in $S_n$ such that $\sum_{i=1}^{n}|\sigma(i)-i|=2k$ and $b_{n,k}$ be the number of odd permutations $\sigma$ in $S_n$ such that $\sum_{i=1}^{n}|\sigma(i)-i|=2k$. Evaluate $a_{n,k}-b_{n,k}$.
[i]* * *[/i]
2022 Philippine MO, 2
The PMO Magician has a special party game. There are $n$ chairs, labelled $1$ to $n$. There are $n$ sheets of paper, labelled $1$ to $n$.
[list]
[*] On each chair, she attaches exactly one sheet whose number does not match the number on the chair.
[*] She then asks $n$ party guests to sit on the chairs so that each chair has exactly one occupant.
[*] Whenever she claps her hands, each guest looks at the number on the sheet attached to their current chair, and moves to the chair labelled with that number.
[/list]
Show that if $1 < m \leq n$, where $m$ is not a prime power, it is always possible for the PMO Magician to choose which sheet to attach to each chair so that everyone returns to their original seats after exactly $m$ claps.
KoMaL A Problems 2017/2018, A. 727
For any finite sequence $(x_1,\ldots,x_n)$, denote by $N(x_1,\ldots,x_n)$ the number of ordered index pairs $(i,j)$ for which $1 \le i<j\le n$ and $x_i=x_j$. Let $p$ be an odd prime, $1 \le n<p$, and let $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ be arbitrary residue classes modulo $p$. Prove that there exists a permutation $\pi$ of the indices $1,2,\ldots,n$ for which
\[N(a_1+b_{\pi(1)},a_2+b_{\pi(2)},\ldots,a_n+b_{\pi(n)})\le \min(N(a_1,a_2,\ldots,a_n),N(b_1,b_2,\ldots,b_n)).\]
2003 Gheorghe Vranceanu, 4
Prove that among any $ 16 $ numbers smaller than $ 101 $ there are four of them that have the property that the sum of two of them is equal to the sum of the other two.
1988 Tournament Of Towns, (200) 3
The integers $1 , 2,..., n$ are rearranged in such a way that if the integer $k, 1 \le k\le n$, is not the first term, then one of the integers $k + 1$ or $k-1$ occurs to the left of $k$ . How many arrangements of the integers $1 , 2,..., n$ satisfy this condition?
(A. Andjans, Riga)
2017 239 Open Mathematical Olympiad, 1
Denote every permutation of $1,2,\dots, n$ as $\sigma =(a_1,a_2,\dots,n)$. Prove that the sum $$\sum \frac{1}{(a_1)(a_1+a_2)(a_1+a_2+a_3)\dots(a_1+a_2+\dots+a_n)}$$ taken over all possible permutations $\sigma$ equals $\frac{1}{n!}$.
2014 IMC, 5
For every positive integer $n$, denote by $D_n$ the number of permutations $(x_1, \dots, x_n)$ of $(1,2,\dots, n)$ such that $x_j\neq j$ for every $1\le j\le n$. For $1\le k\le \frac{n}{2}$, denote by $\Delta (n,k)$ the number of permutations $(x_1,\dots, x_n)$ of $(1,2,\dots, n)$ such that $x_i=k+i$ for every $1\le i\le k$ and $x_j\neq j$ for every $1\le j\le n$. Prove that
$$\Delta (n,k)=\sum_{i=0}^{k=1} \binom{k-1}{i} \frac{D_{(n+1)-(k+i)}}{n-(k+i)}$$
(Proposed by Combinatorics; Ferdowsi University of Mashhad, Iran; Mirzavaziri)
2016 AIME Problems, 8
For a permutation $p = (a_1,a_2,\ldots,a_9)$ of the digits $1,2,\ldots,9$, let $s(p)$ denote the sum of the three $3$-digit numbers $a_1a_2a_3$, $a_4a_5a_6$, and $a_7a_8a_9$. Let $m$ be the minimum value of $s(p)$ subject to the condition that the units digit of $s(p)$ is $0$. Let $n$ denote the number of permutations $p$ with $s(p) = m$. Find $|m - n|$.
2014 IFYM, Sozopol, 4
Let $A$ be the set of permutations $a=(a_1,a_2,…,a_n)$ of $M=\{1,2,…n\}$ with the following property: There doesn’t exist a subset $S$ of $M$ such that $a(S)=S$. For $\forall$ such permutation $a$ let $d(a)=\sum_{k=1}^n (a_k-k)^2$ . Determine the smallest value of $d(a)$.
2023 IMAR Test, P3
Let $p{}$ be an odd prime number. Determine whether there exists a permutation $a_1,\ldots,a_p$ of $1,\ldots,p$ satisfying \[(i-j)a_k+(j-k)a_i+(k-i)a_j\neq 0,\] for all pairwise distinct $i,j,k.$
2023 Austrian MO Regional Competition, 3
Determine all natural numbers $n \ge 2$ with the property that there are two permutations $(a_1, a_2,... , a_n) $ and $(b_1, b_2,... , b_n)$ of the numbers $1, 2,..., n$ such that $(a_1 + b_1, a_2 +b_2,..., a_n + b_n)$ are consecutive natural numbers.
[i](Walther Janous)[/i]
2024 Junior Balkan Team Selection Tests - Romania, P1
Let $n\geqslant 3$ be an integer and $a_1,a_2,\ldots,a_n$ be pairwise distinct positive real numbers with the property that there exists a permutation $b_1,b_2,\ldots,b_n$ of these numbers such that\[\frac{a_1}{b_1}=\frac{a_2}{b_2}=\cdots=\frac{a_{n-1}}{b_{n-1}}\neq 1.\]Prove that there exist $a,b>0$ such that $\{a_1,a_2,\ldots,a_n\}=\{ab,ab^2,\ldots,ab^n\}.$
[i]Cristi Săvescu[/i]
1969 IMO Longlists, 31
$(GDR 3)$ Find the number of permutations $a_1, \cdots, a_n$ of the set $\{1, 2, . . ., n\}$ such that $|a_i - a_{i+1}| \neq 1$ for all $i = 1, 2, . . ., n - 1.$ Find a recurrence formula and evaluate the number of such permutations for $n \le 6.$
2016 Bangladesh Mathematical Olympiad, 5
Suppose there are $m$ Martians and $n$ Earthlings at an intergalactic peace conference. To ensure the Martians stay peaceful at the conference, we must make sure that no two Martians sit together, such that between any two Martians there is always at least one Earthling.
(a) Suppose all $m + n$ Martians and Earthlings are seated in a line. How many ways can the Earthlings and Martians be seated in a line?
(b) Suppose now that the $m+n$ Martians and Earthlings are seated around a circular round-table. How many ways can the Earthlings and Martians be seated around the round-table?
2012 Dutch IMO TST, 4
Let $n$ be a positive integer divisible by $4$. We consider the permutations $(a_1, a_2,...,a_n)$ of $(1,2,..., n)$ having the following property: for each j we have $a_i + j = n + 1$ where $i = a_j$ . Prove that there are exactly $\frac{ (\frac12 n)!}{(\frac14 n)!}$ such permutations.