Found problems: 175
$x_1, x_2, ... , x_8$ is a permutation of $1, 2, ..., 8$. A move is to take $x_3$ or $x_8$ and place it at the start to from a new sequence. Show that by a sequence of moves we can always arrive at $1, 2, ..., 8$.
Consider $n$ students with numbers $1, 2, \ldots, n$ standing in the order $1, 2, \ldots, n.$ Upon a command, any of the students either remains on his place or switches his place with another student. (Actually, if student $A$ switches his place with student $B,$ then $B$ cannot switch his place with any other student $C$ any more until the next command comes.)
Is it possible to arrange the students in the order $n,1, 2, \ldots, n-1$ after two commands ?
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.
Find all positive integers $n\geqslant 2$ such that there exists a permutation $a_1$, $a_2$, $a_3$, \ldots, $a_{2n}$ of the numbers $1, 2, 3, \ldots, 2n$ satisfying $$a_1\cdot a_2 + a_3\cdot a_4 + \ldots + a_{2n-3} \cdot a_{2n-2} = a_{2n-1} \cdot a_{2n}.$$
$(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.$
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$.
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.
Determine the number of permutations $a_1, a_2, \dots, a_n$ of $1, 2, \dots, n$ such that for every positive integer $k$ with $1 \le k \le n$, there exists an integer $r$ with $0 \le r \le n - k$ which satisfies
\[ 1 + 2 + \dots + k = a_{r+1} + a_{r+2} + \dots + a_{r+k}. \]
We choose a random permutation of $1,2,\ldots,n$ with uniform distribution. Prove that the expected value of the length of the longest increasing subsequence in the permutation is at least $\sqrt{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.
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)$.
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)
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.
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)$.
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.
Let $n$ be a positive integer. Marc has $2n$ boxes, and in particular, he has one box filled with $k$ apples for each $k=1,2,3,\ldots,2n$. Every day, Marc opens a box and eats all the apples in it. However, if he eats strictly more than $2n+1$ apples in two consecutive days, he gets stomach ache. Prove that Marc has exactly $2^n$ distinct ways of choosing the boxes so that he eats all the apples but doesn't get stomach ache.
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$?
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]
What is the largest possible value of $|a_1 - 1| + |a_2-2|+...+ |a_n- n|$ where $a_1, a_2,..., a_n$ is a permutation of $1,2,..., n$?
Let $n$ be a positive integer. Determine the smallest value of the sum $a_1b_1+a_2b_2+...+a_{2n+2}b_{2n+2}$
where $(a_1,a_2,...,a_{2n+2})$ and $(b_1,b_2,...,b_{2n+2})$ are rearrangements of the binomial coefficients $2n+1 \choose 0$, $2n+1 \choose 1$,...,$2n+1 \choose 2n+1$. Justify your answer
There are $n$ students standing in line positions $1$ to $n$. While the teacher looks away, some students change their positions. When the teacher looks back, they are standing in line again. If a student who was initially in position $i$ is now in position $j$, we say the student moved for $|i-j|$ steps. Determine the maximal sum of steps of all students that they can achieve.
Let $n,k$, $1\le k\le n$ be fixed integers. Alice has $n$ cards in a row, where the card has position $i$ has the label $i+k$ (or $i+k-n$ if $i+k>n$). Alice starts by colouring each card either red or blue. Afterwards, she is allowed to make several moves, where each move consists of choosing two cards of different colours and swapping them. Find the minimum number of moves she has to make (given that she chooses the colouring optimally) to put the cards in order (i.e. card $i$ is at position $i$).
NOTE: edited from original phrasing, which was ambiguous.
Find all positive integers $k$ such that there exists some permutation of $(1, 2,...,1000)$ namely $(a_1, a_2,..., a_{1000}) $ and satisfy $|a_i - i| = k$ for all $i = 1,1000$.
Let $n$ be a positive integer such that there exists a positive integer that is less than $\sqrt{n}$ and does not divide $n$. Let $(a_1, . . . , a_n)$ be an arbitrary permutation of $1, . . . , n$. Let $a_{i1} < . . . < a_{ik}$ be its maximal increasing subsequence and let $a_{j1} > . . . > a_{jl}$ be its maximal decreasing subsequence.
Prove that tuples $(a_{i1}, . . . , a_{ik})$ and $(a_{j1}, . . . , a_{jl} )$ altogether contain at least one number that does not divide $n$.