Found problems: 5802
Given a permutation $(a_{1}, a_{1},...,a_{n})$ of the numbers $1, 2,...,n$ one may interchange any two consecutive "blocks" - that is, one may transform
($a_{1}, a_{2},...,a_{i}$,$\underbrace {a_{i+1},... a_{i+p},}_{A} $ $ \underbrace{a_{i+p+1},...,a_{i+q},}_{B}...,a_{n}) $
into
$ (a_{1}, a_{2},...,a_{i},$ $ \underbrace {a_{i+p+1},...,a_{i+q},}_{B} $ $ \underbrace {a_{i+1},... a_{i+p}}_{A}$$,...,a_{n}) $
by interchanging the "blocks" $A$ and $B$. Find the least number of such changes which are needed to transform $(n, n-1,...,1)$ into $(1,2,...,n)$
Let $k$ and $n$ be integers with $1\leq k<n$. Alice and Bob play a game with $k$ pegs in a line of $n$ holes. At the beginning of the game, the pegs occupy the $k$ leftmost holes. A legal move consists of moving a single peg to any vacant hole that is further to the right. The players alternate moves, with Alice playing first. The game ends when the pegs are in the $k$ rightmost holes, so whoever is next to play cannot move and therefore loses. For what values of $n$ and $k$ does Alice have a winning strategy?
Let $S_n$ be the sum of the first $n$ prime numbers. For example,
\[ S_5 = 2 + 3 + 5 + 7 + 11 = 28.\]
Does there exist an integer $k$ such that $S_{2023} < k^2 < S_{2024}$?
Let $ABCD$ be a square with side $20$ and $T_1, T_2, ..., T_{2000}$ are points in $ABCD$ such that no $3$ points in the set $S = \{A, B, C, D, T_1, T_2, ..., T_{2000}\}$ are collinear. Prove that there exists a triangle with vertices in $S$, such that the area is less than $1/10$.
You are given $n\geq 4$ positive real numbers. Consider all $\frac{n(n-1)}{2}$ pairwise sums of these numbers. Show that some two of these sums differ in at most $\sqrt[n-2]{2}$ times.
[i]Proposed by Anton Trygub[/i]
Let $w = w_1 w_2 \dots w_n$ be a word. Define a [i]substring[/i] of $w$ to be a word of the form $w_i w_{i + 1} \dots w_{j - 1} w_j$, for some pair of positive integers $1 \le i \le j \le n$. Show that $w$ has at most $n$ distinct palindromic substrings.
For example, $aaaaa$ has $5$ distinct palindromic substrings, and $abcata$ has $5$ ($a$, $b$, $c$, $t$, $ata$).
For a natural number $k>1$, define $S_k$ to be the set of all triplets $(n,a,b)$ of natural numbers, with $n$ odd and $\gcd (a,b)=1$, such that $a+b=k$ and $n$ divides $a^n+b^n$. Find all values of $k$ for which $S_k$ is finite.
We have $ n \geq 2$ lamps $ L_{1}, . . . ,L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp $ L_{i}$ and its neighbours (only one neighbour for $ i \equal{} 1$ or $ i \equal{} n$, two neighbours for other $ i$) are in the same state, then $ L_{i}$ is switched off; – otherwise, $ L_{i}$ is switched on.
Initially all the lamps are off except the leftmost one which is on.
$ (a)$ Prove that there are infinitely many integers $ n$ for which all the lamps will eventually be off.
$ (b)$ Prove that there are infinitely many integers $ n$ for which the lamps will never be all off.
Consider a sequence $\{a_n\}$ of integers, satisfying $a_1=1, a_2=2$ and $a_{n+1}$ is the largest prime divisor of $a_1+a_2+\ldots+a_n$. Find $a_{100}$.
Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$, letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$. For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$. Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.
Let $p_1,p_2,\ldots,p_n$ be distinct primes greater than $3$. Show that $2^{p_1p_2\cdots p_n}+1$ has at least $4^n$ divisors.
Find all ordered triples of nonnegative integers $(a,b,c)$ satisfying $2^a \cdot 5^b - 3^c = 1.$
Three non-collinear points $A_1, A_2, A_3$ are given in a plane. For $n = 4, 5, 6, \ldots$, $A_n$ be the centroid of the triangle $A_{n-3}A_{n-2}A_{n-1}$.
[list]
a) Show that there is exactly one point $S$, which lies in the interior of the triangle $A_{n-3}A_{n-2}A_{n-1}$ for all $n\ge 4$.
b) Let $T$ be the intersection of the line $A_1A_2$ with $SA_3$. Determine the two ratios, $A_1T : TA_2$ and $TS : SA_3$.
[/list]
Find all functions $f\colon \mathbb{Z}^2 \to [0, 1]$ such that for any integers $x$ and $y$,
\[f(x, y) = \frac{f(x - 1, y) + f(x, y - 1)}{2}.\]
[i]Proposed by Yang Liu and Michael Kural[/i]
Show that there exists a degree $58$ monic polynomial
$$P(x) = x^{58} + a_1x^{57} + \cdots + a_{58}$$
such that $P(x)$ has exactly $29$ positive real roots and $29$ negative real roots and that $\log_{2017} |a_i|$ is a positive integer for all $1 \leq i \leq 58$.
Let $k$ be the largest integer such that $2^k$ divides
$$\left(\prod_{n=1}^{25}\left(\sum_{i=0}^n\binom{n}{i}\right)^2\right)\left(\prod_{n=1}^{25}\left(\sum_{i=0}^n\binom{n}{i}^2\right)\right).$$
Find $k$.
Let $\mathbb{Z}_{>0}$ denote the set of positive integers. For any positive integer $k$, a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is called [i]$k$-good[/i] if $\gcd(f(m) + n, f(n) + m) \le k$ for all $m \neq n$. Find all $k$ such that there exists a $k$-good function.
[i]Proposed by James Rickards, Canada[/i]
A solitaire game is played on an $m\times n$ rectangular board, using $mn$ markers which are white on one side and black on the other. Initially, each square of the board contains a marker with its white side up, except for one corner square, which contains a marker with its black side up. In each move, one may take away one marker with its black side up, but must then turn over all markers which are in squares having an edge in common with the square of the removed marker. Determine all pairs $(m,n)$ of positive integers such that all markers can be removed from the board.
There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n \minus{} 1$ is not divisible by $ 3$.
[i]Proposed by Dusan Dukic, Serbia[/i]
Let $a_0,a_1,\ldots$ be a sequence of positive integers with $a_0=1$, $a_1=2$ and
\[a_n = a_{n-1}^{a_{n-1}a_{n-2}}-1\]
for all $n\geq 2$. Show that if $p$ is a prime less than $2^k$ for some positive integer $k$, then there exists $n\leq k+1$ such that $p\mid a_n$.
In a 2025 by 2025 grid, every cell initially contains a `1'. Every minute, we simultaneously replace the number in each cell with the sum of numbers in the cells that share an edge with it. (For example, after the first minute, the number 2 is written in each of the four
corner cells.)
After 2025 minutes, we colour the board in checkerboard fashion, such that the top left corner is black. Find the difference between the sum of numbers in black cells and the sum of numbers in white cells.
[i]Proposed by chorn[/i]
Let $p,q \in \mathbb N^{\ast}$, $p,q \geq 2$. We say that a set $X$ has the property $\left( \mathcal S \right)$ if no matter how we choose $p$ subsets $B_i \subset X$, $i = \overline{1,n}$, not necessarily distinct, each with $q$ elements, there is a subset $Y \subset X$ with $p$ elements s.t. the intersection of $Y$ with each of the $B_i$'s has an element at most, $i=\overline{1,p}$. Prove that:
(a) if $p=4,q=3$ then any set composed of $9$ elements doesn't have $\left( \mathcal S \right)$;
(b) any set $X$ composed of $pq-q$ elements doesn't have the property $\left( \mathcal S \right)$;
(c) any set $X$ composed of $pq-q+1$ elements has the property $\left( \mathcal S \right)$.
[i]Dan Schwarz[/i]
Let $a_1, a_2, \dots$ be a sequence of real numbers satisfying $a_{i+j} \leq a_i+a_j$ for all $i,j=1,2,\dots$. Prove that
\[ a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n} \geq a_n \]
for each positive integer $n$.
Given a finite sequence of real numbers $a_1,a_2,\dots ,a_n$ ($\ast$), we call a segment $a_k,\dots ,a_{k+l-1}$ of the sequence ($\ast$) a “[i]long[/i]”(Chinese dragon) and $a_k$ “[i]head[/i]” of the “[i]long[/i]” if the arithmetic mean of $a_k,\dots ,a_{k+l-1}$ is greater than $1988$. (especially if a single item $a_m>1988$, we still regard $a_m$ as a “[i]long[/i]”). Suppose that there is at least one “[i]long[/i]” among the sequence ($\ast$), show that the arithmetic mean of all those items of sequence ($\ast$) that could be “[i]head[/i]” of a certain “[i]long[/i]” individually is greater than $1988$.
Let $m \neq 0 $ be an integer. Find all polynomials $P(x) $ with real coefficients such that
\[ (x^3 - mx^2 +1 ) P(x+1) + (x^3+mx^2+1) P(x-1) =2(x^3 - mx +1 ) P(x) \]
for all real number $x$.