Found problems: 175
Find all permutations $(a_1, a_2, \cdots, a_{2024})$ of $(1, 2, \cdots, 2024)$ such that there exists a polynomial $P$ with integer coefficients satisfying $P(i) = a_i$ for each $i = 1, 2, \cdots, 2024$.
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.
A permutation of the integers $1, 2, \ldots, m$ is called [i]fresh[/i] if there exists no positive integer $k < m$ such that the first $k$ numbers in the permutation are $1, 2, \ldots, k$ in some order. Let $f_m$ be the number of fresh permutations of the integers $1, 2, \ldots, m$.
Prove that $f_n \ge n \cdot f_{n - 1}$ for all $n \ge 3$.
[i]For example, if $m = 4$, then the permutation $(3, 1, 4, 2)$ is fresh, whereas the permutation $(2, 3, 1, 4)$ is not.[/i]
Each row of a $24 \times 8$ table contains some permutation of the numbers $1, 2, \cdots , 8.$ In each column the numbers are multiplied. What is the minimum possible sum of all the products?
[i](C. Wu)[/i]
Consider the string of length $6$ composed of three characters $a, b, c$. For each string, if two $a$s are next to each other, or two $b$s are next to each other, then replace $aa$ by $b$, and replace $bb$ by $a$. Also, if $a$ and $b$ are next to each other, or two $c$s are next to each other, remove all two of them (i.e. delete $ab, ba, cc$). Determine the number of strings that can be reduced to $c$, the string of length $1$, by the reducing processes mentioned above.
For each permutation $\sigma$ of the set $\{1, 2, \ldots , N\}$ we define its [i]correctness[/i] as the number of triples $1 \leqslant i < j < k \leqslant N$ such that the number $\sigma(j)$ lies between the numbers $\sigma(i)$ and $\sigma(k)$. Find the difference between the number of permutations with even correctness and the number of permutations with odd correctness if a) $N = 2018$ and b) $N = 2019$.
Does there exist a sequence of positive integers \( a_1, a_2, \ldots, a_{100} \) such that every number from \( 1 \) to \( 100 \) appears exactly once, and for each \( 1 \leq i \leq 100 \), the condition
\[
a_{a_i + i} = i
\]
holds? Here it is assumed that \( a_{k+100} = a_k \) for each \( 1 \leq k \leq 100 \).
[i]Proposed by Mykhailo Shtandenko[/i]
On a table, cards numbered $1, 2, \ldots , 200$ are laid out in a row in some order, and a line is drawn on the table between some two of them. It is allowed to swap two adjacent cards if the number on the left is greater than the number on the right. After a few such moves, the cards were arranged in ascending order. Prove we have swapped pairs of cards separated by the line no more than 1884 times.
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$
We say that a permutation $(a_1, \dots, a_n)$ of $(1, 2, \dots, n)$ is good if the sums $a_1 + a_2 + \dots + a_i$ are all distinct modulo $n$. Prove that there exists a positive integer $n$ such that there are at least $2020$ good permutations of $(1, 2, \dots, n)$.
[i]Proposed by Ariel García[/i]
Consider a table of cyclic permutations ($n\ge2$)
\[
\begin{matrix}
1, & 2, & \ldots, & n-1, & n \\
2, & 3, & \ldots, & n, & 1, \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
n, & 1, & \ldots, & n-2, & n-1.
\end{matrix}
\]
Then multiply each number of the first row by that number of the $k$-th row that is in the same column. Sum all these products and denote $s_k$ the result (e.g. $s_2=1\cdot2+2\cdot3+\cdots+(n-1)\cdot n+n\cdot1$).
a) Find a recursive relation for $s_k$ in terms of $s_{k-1}$ and determine the explicit formula for $s_k$.
b) Determine both an index $k$ and the value of $s_k$ such that the sum $s_k$ is minimal.
How many permutations $(s_1, s_2,...,s_n) $of $(1,2 ,...,n)$ are there satisfying the condition $s_i > s_j$ for all $i \ge j + 3$ when $n = 5$ and when $n = 7$?
An $ n \times n, n \geq 2$ chessboard is numbered by the numbers $ 1, 2, \ldots, n^2$ (and every number occurs). Prove that there exist two neighbouring (with common edge) squares such that their numbers differ by at least $ n.$
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$?
Find all positive integer $n$ such that there exists a permutation $(a_1, a_2,...,a_n)$ of $(1, 2,3,..., n)$ satisfying the condition:
$a_1 + a_2 +... + a_k$ is divisible by $k$ for each $k = 1, 2,3,..., n$.
Let $n$ be a prime number. Show that there is a permutation $a_1,a_2,...,a_n$ of $1,2,...,n$ so that $a_1,a_1a_2,...,a_1a_2...a_n$ leave distinct remainders when divided by $n$
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} . $
We consider two sequences of real numbers $x_{1} \geq x_{2} \geq \ldots \geq x_{n}$ and $\ y_{1} \geq y_{2} \geq \ldots \geq y_{n}.$ Let $z_{1}, z_{2}, .\ldots, z_{n}$ be a permutation of the numbers $y_{1}, y_{2}, \ldots, y_{n}.$ Prove that $\sum \limits_{i=1}^{n} ( x_{i} -\ y_{i} )^{2} \leq \sum \limits_{i=1}^{n}$ $( x_{i} - z_{i})^{2}.$
Let $n\geq 3$ an integer. Determine whether there exist permutations $(a_1,a_2, \ldots, a_n)$ of the numbers $(1,2,\ldots, n)$ and $(b_1, b_2, \ldots, b_n)$ of the numbers $(n+1,n+2,\ldots, 2n)$ so that $(a_1b_1, a_2b_2, \ldots a_nb_n)$ is a strictly increasing arithmetic progression.
Decide whether for every arrangement of the numbers $1,2,3, . . . ,15$ in a sequence one can color these numbers with at most four different colors in such a way that the numbers of each color form a monotone subsequence.
Consider two finite sequences of real numbers \( a_1, a_2, \dots, a_n \) and \( b_1, b_2, \dots, b_n \). Let \( \alpha(x) = \#\{i | a_i = x \} \) and \( \beta(x) = \#\{i | b_i = -x \} \). Prove that there exists a permutation \( \sigma \in S_n \) (the symmetric group of \( n \) elements) such that \( a_{\sigma(i)} + b_i \neq 0 \) for all \( i = 1, \dots, n \) if and only if \( \alpha(x) + \beta(x) \leq n \) for all \( x \in \mathbb{R} \).
Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which
\[k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.\]
Find the number of elements of the set $A_n$.
[i]Proposed by Vidan Govedarica, Serbia[/i]
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.
Cards numbered 1 to 9 are arranged at random in a row. In a move, one may choose any block of consecutive cards whose numbers are in ascending or descending order, and switch the block around. For example, 9 1 $\underline{6\ 5\ 3}$ $2\ 7\ 4\ 8$ may be changed to $9 1$ $\underline{3\ 5\ 6}$ $2\ 7\ 4\ 8$. Prove that in at most 12 moves, one can arrange the 9 cards so that their numbers are in ascending or descending order.
In a hidden friend, suppose no one takes oneself. We say that the hidden friend has "marmalade" if
there are two people $A$ and $ B$ such that A took $B$ and $ B $ took $A$. For each positive integer n, let $f (n)$ be the number of hidden friends with n people where there is no “marmalade”, i.e. $f (n)$ is equal to the number of permutations $\sigma$ of {$1, 2,. . . , n$} such that:
*$\sigma (i) \neq i$ for all $i=1,2,...,n$
* there are no $ 1 \leq i <j \leq n $ such that $ \sigma (i) = j$ and $\sigma (j) = i. $
Determine the limit
$\lim_{n \to + \infty} \frac{f(n)}{n!}$