Fix an integer $n \ge 3$ and let $a_0 = n$. Does there exist a permutation $a_1, a_2,..., a_{n-1}$ of the first $n-1$ positive integers such that $\Sigma_{j=0}^{k-1} a_j$ is divisible by $a_k$ for all indices $k < n$?

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.

For any permutation $p$ of set $\{1, 2, \ldots, n\}$, define $d(p) = |p(1) - 1| + |p(2) - 2| + \ldots + |p(n) - n|$. Denoted by $i(p)$ the number of integer pairs $(i, j)$ in permutation $p$ such that $1 \leqq < j \leq n$ and $p(i) > p(j)$. Find all the real numbers $c$, such that the inequality $i(p) \leq c \cdot d(p)$ holds for any positive integer $n$ and any permutation $p.$

$(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.$

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.$

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.

An $n$ by $n$ table has an integer in each cell, such that no two cells within a row share the same number. Prove that it is possible to permute the elements within each row to obtain a table that has $n$ distinct numbers in each column.

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)

Let $a_1, a_2, \ldots, a_n$ be positive reals for $n \geq 2$. For a permutation $(b_1, b_2, \ldots, b_n)$ of $(a_1, a_2, \ldots, a_n)$, define its $\textit{score}$ to be $$\sum_{i=1}^{n-1}\frac{b_i^2}{b_{i+1}}.$$ Show that some two permutations of $(a_1, a_2, \ldots, a_n)$ have scores that differ by at most $3|a_1-a_n|$.

Let $p$ be a prime number. For any $\sigma \in S_p$ (the permutation group of $\{1,2,...,p \}),$ define the matrix $A_{\sigma}=(a_{ij}) \in \mathcal{M}_p(\mathbb{Z})$ as $a_{ij} = \sigma^{i-1}(j),$ where $\sigma^0$ is the identity permutation and $\sigma^k = \underbrace{\sigma \circ \sigma \circ ... \circ \sigma}_k.$ Prove that $D = \{ |\det A_{\sigma}| : \sigma \in S_p \}$ has at most $1+ (p-2)!$ elements.

Five students $ A, B, C, D, E$ took part in a contest. One prediction was that the contestants would finish in the order $ ABCDE$. This prediction was very poor. In fact, no contestant finished in the position predicted, and no two contestants predicted to finish consecutively actually did so. A second prediction had the contestants finishing in the order $ DAECB$. This prediction was better. Exactly two of the contestants finished in the places predicted, and two disjoint pairs of students predicted to finish consecutively actually did so. Determine the order in which the contestants finished.

Let $S$ be the set of all 9-digit natural numbers, which are written only with the digits 1, 2, and 3. Find all functions $f:S\rightarrow \{1,2,3\}$ which satisfy the following conditions: (1) $f(111111111)=1$, $f(222222222)=2$, $f(333333333)=3$, $f(122222222)=1$; (2) If $x,y\in S$ differ in each digit position, then $f(x)\neq f(y)$.

For every integer $n \ge 2$ let $B_n$ denote the set of all binary $n$-nuples of zeroes and ones, and split $B_n$ into equivalence classes by letting two $n$-nuples be equivalent if one is obtained from the another by a cyclic permutation.(for example 110, 011 and 101 are equivalent). Determine the integers $n \ge 2$ for which $B_n$ splits into an odd number of equivalence classes.

An illusionist and his assistant are about to perform the following magic trick. Let $k$ be a positive integer. A spectator is given $n=k!+k-1$ balls numbered $1,2,…,n$. Unseen by the illusionist, the spectator arranges the balls into a sequence as he sees fit. The assistant studies the sequence, chooses some block of $k$ consecutive balls, and covers them under her scarf. Then the illusionist looks at the newly obscured sequence and guesses the precise order of the $k$ balls he does not see. Devise a strategy for the illusionist and the assistant to follow so that the trick always works. (The strategy needs to be constructed explicitly. For instance, it should be possible to implement the strategy, as described by the solver, in the form of a computer program that takes $k$ and the obscured sequence as input and then runs in time polynomial in $n$. A mere proof that an appropriate strategy exists does not qualify as a complete solution.)

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)

If permutations of the numbers $2, 3,4,..., 102$ are denoted by $a_i,a_2, a_3,...,a_{101}$, find all such permutations in which $a_k$ is divisible by $k$ for all $k$.

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]

The natural numbers $M$ and $K$ are represented by different permutations of the same digits. Prove that (a) The sum of the digits of $2M$ equals the sum of the digits of $2K$. (b) The sum of the digits of $M/2$ equals the sum of the digits of $K/2$ ($M, K$ both even). (c) The sum of the digits of $5M$ equals the sum of the digits of $5 K$. (AD Lisitskiy)

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]

For positive integers $k$ and $n$, express the number of permutation $P=x_1x_2...x_{2n}$ consisting of $A$ and $B$ that satisfies all three of the following conditions, using $k$ and $n$. $ $ $ $ $(i)$ $A, B$ appear exactly $n$ times respectively in $P$. $ $ $ $ $(ii)$ For each $1\le i\le n$, if we denote the number of $A$ in $x_1,x_2,...,x_i$ as $a_i$ $,$ then $\mid 2a_i -i\mid \le 1$. $ $ $ $ $(iii)$ $AB$ appears exactly $k$ times in $P$. (For example, $AB$ appears 3 times in $ABBABAAB$)

For any permutation $p$ of the set $\{1,2,...,n\}$, let us denote $d(p) = |p(1)-1|+|p(2)-2|+...+|p(n)-n|$. Let $i(p)$ be the number of inversions of $p$, i.e. the number of pairs $1 \le i < j \le n$ with $p(i) > p(j)$. Prove that $d(p)\le 2i(p)$$.

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 $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!$.

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]

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.