Found problems: 175
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.
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.
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$.
Consider an odd prime $p$ and a positive integer $N < 50p$. Let $a_1, a_2, \ldots , a_N$ be a list of positive integers less than $p$ such that any specific value occurs at most $\frac{51}{100}N$ times and $a_1 + a_2 + \cdots· + a_N$ is not divisible by $p$. Prove that there exists a permutation $b_1, b_2, \ldots , b_N$ of the $a_i$ such that, for all $k = 1, 2, \ldots , N$, the sum $b_1 + b_2 + \cdots + b_k$ is not divisible by $p$.
[i]Will Steinberg, United Kingdom[/i]
How many permutations $s$ does the set $\{1,2,..., 15\}$ have with the following properties:
for every $1 \le k \le 13$ we have $s(k) < s(k+2)$ and for every $1 \le k \le 12$ we have $s(k) < s(k+3)$?
The $1 \times 1$ cells located around the perimeter of a $3 \times 3$ square are filled with the numbers $1,
2, \ldots, 8$ so that the sums along each of the four sides are equal. In the upper left corner cell is the number $8$, and in the upper left is the number $6$ (see the figure below).
[img]https://i.ibb.co/bRmd12j/Kyiv-MO-2021-Round-1-8-2.png[/img]
How many different ways to fill the remaining cells are there under these conditions?
[i]Proposed by Mariia Rozhkova[/i]
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]
From all possible permutations from $(a_1,a_2,...,a_n)$ from the set $\{1,2,..,n\}$, $n\geq 1$, consider the sets that satisfies the $2(a_1+a_2+...+a_m)$ is divisible by $m$, for every $m=1,2,...,n$. Find the total number of permutations.
1) Prove that there are infinitely many positive integers $n$ such that there exists a permutation of $1, 2, 3, . . . , n$ with the property that the difference between any two adjacent numbers is equal to either $2015$ or $2016$.
2) Let $k$ be a positive integer. Is the statement in 1) still true if we replace the numbers $2015$ and $2016$ by $k$ and $k + 2016$, respectively?
We consider an integer $n \ge 3,$ the set $S=\{1,2,3,\ldots,n\}$ and the set $\mathcal{F}$ of the functions from $S$ to $S.$ We say that $\mathcal{G} \subset \mathcal{F}$ is a generating set for $\mathcal{H} \subset \mathcal{F}$ if any function in $\mathcal{H}$ can be represented as a composition of functions from $\mathcal{G}.$
a) Let the functions $a:S \to S,$ $a(n-1)=n,$ $a(n)=n-1$ and $a(k)=k$ for $k \in S \setminus \{n-1,n\}$ and $b:S \to S,$ $b(n)=1$ and $b(k)=k+1$ for $k \in S \setminus \{n\}.$ Prove that $\{a,b\}$ is a generating set for the set $\mathcal{B}$ of bijective functions of $\mathcal{F}.$
b) Prove that the smallest number of elements that a generating set of $\mathcal{F}$ has is $3.$
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]
$a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, $a_7$ and $b_1$, $b_2$, $b_3$, $b_4$, $b_5$, $b_6$, $b_7$ are two permutations of $1, 2, 3, 4, 5, 6, 7$. Show that $|a_1 - b_1|$, $|a_2 - b_2|$, $|a_3 - b_3|$, $|a_4 - b_4|$, $|a_5 - b_5|$, $|a_6 - b_6|$, $|a_7 - b_7|$ are not all different.
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$.
Determine the highest possible value of:
$$S = a_1a_2a_3 + a_4a_5a_6 +... + a_{2017}a_{2018}a_{2019} + a_{2020}$$
where $(a_1, a_2, a_3,..., a_{2020})$ is a permutation of $(1,2,3,..., 2020)$.
Clarification: In $S$, each term, except the last one, is the multiplication of three numbers.
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]
Let $\sigma, \tau$ be two permutations of the quantity $\{1, 2,. . . , n\}$.
Prove that there is a function $f: \{1, 2,. . . , n\} \to \{-1, 1\}$ such that for any $1 \le i \le j \le n$,
we have $\left|\sum_{k=i}^{j} f(\sigma (k)) \right| \le 2$ and $\left|\sum_{k=i}^{j} f(\tau (k))\right| \le 2$
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$.
Let $S$ be a set of positive integers $n_1, n_2, \cdots, n_6$ and let $n(f)$ denote the number $n_1n_{f(1)} +n_2n_{f(2)} +\cdots+n_6n_{f(6)}$, where $f$ is a permutation of $\{1, 2, . . . , 6\}$. Let
\[\Omega=\{n(f) | f \text{ is a permutation of } \{1, 2, . . . , 6\} \} \]
Give an example of positive integers $n_1, \cdots, n_6$ such that $\Omega$ contains as many elements as possible and determine the number of elements of $\Omega$.
From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that :
[b](i)[/b] each pair of consecutive teams on the list have one member in common and
[b](ii)[/b] the chain of teams on the list are in rank order.
[i]Alternative formulation.[/i]
Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$ , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
In a permutation $(x_1, x_2, \dots , x_n)$ of the set $1, 2, \dots , n$ we call a pair $(x_i, x_j )$ discordant if $i < j$ and $x_i > x_j$. Let $d(n, k)$ be the number of such permutations with exactly $k$ discordant pairs. Find $d(n, 2)$ and $d(n, 3).$
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)$.
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 .
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]
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)
In a permutation $(x_1, x_2, \dots , x_n)$ of the set $1, 2, \dots , n$ we call a pair $(x_i, x_j )$ discordant if $i < j$ and $x_i > x_j$. Let $d(n, k)$ be the number of such permutations with exactly $k$ discordant pairs. Find $d(n, 2)$ and $d(n, 3).$