Found problems: 815
Initially, the numbers $1$ and $2$ are written on the board. A move consists of choosing a positive real number $x$ and replacing $(a,b)$ on the board by $\left(a+\frac{x}{b},b+\frac{x}{a}\right)$. Is it possible to create in finitely many moves a situation where the numbers on the board are $2$ and $3$?
A set of lines in the plane is in [i]general position[/i] if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its [i]finite regions[/i]. Prove that for all sufficiently large $n$, in any set of $n$ lines in general position it is possible to colour at least $\sqrt{n}$ lines blue in such a way that none of its finite regions has a completely blue boundary.
[i]Note[/i]: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$.
Suppose that $a,b,c,d$ are positive real numbers satisfying $(a+c)(b+d)=ac+bd$. Find the smallest possible value of
$$\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}.$$
[i]Israel[/i]
Pasha and Vova play the following game, making moves in turn; Pasha moves first. Initially, they have a large piece of plasticine. By a move, Pasha cuts one of the existing pieces into three(of arbitrary sizes), and Vova merges two existing pieces into one. Pasha wins if at some point there appear to be $100$ pieces of equal weights. Can Vova prevent Pasha's win?
Petya chooses $100$ pairwise distinct positive numbers less than $1$ and arranges them in a circle. In one operation, he may take three consecutive numbers \( a, b, c \) (in this order) and replace \( b \) with \( a - b + c \). What is the greatest value of \( k \) such that Petya could initially choose the numbers and perform several operations so that \( k \) of the resulting numbers are integers? \\
There are $n \geq 3$ islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route.
After each year, the ferry company will close a ferry route between some two islands $X$ and $Y$. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected to a ferry route to exactly one of $X$ and $Y$, a new route between this island and the other of $X$ and $Y$ is added.
Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.
Three numbers are initially written on the board: 2023, 2024, and 2025. In each move, you can increase any two of these numbers by 1 and decrease the third one by 2.
a) Determine whether it is possible to perform a sequence of operations such that the board eventually contains two numbers that are equal.
b) Calculate the number of all possible ordered triples of positive integers that can be obtained by performing such operations some number of times.
[i]Proposed by Giorgi Arabidze, Georgia [/i]
Two players $A$ and $B$ take turns playing the following game: There is a pile of $2003$ stones. In his first turn, $A$ selects a divisor of $2003$ and removes this number of stones from the pile. $B$ then chooses a divisor of the number of remaining stones, and removes that number of stones from the new pile, and so on. The player who has to remove the last stone loses. Show that one of the two players has a winning strategy and describe the strategy.
Let $S$ be a set of three, not necessarily distinct, positive integers. Show that one can transform $S$ into a set containing $0$ by a finite number of applications of the following rule: Select two of the integers $x$ and $y$, where $x\leq y$ and replace them with $2x$ and $y-x.$
Let $ABC$ be an isosceles triangle with $AC=BC$, whose incentre is $I$. Let $P$ be a point on the circumcircle of the triangle $AIB$ lying inside the triangle $ABC$. The lines through $P$ parallel to $CA$ and $CB$ meet $AB$ at $D$ and $E$, respectively. The line through $P$ parallel to $AB$ meets $CA$ and $CB$ at $F$ and $G$, respectively. Prove that the lines $DF$ and $EG$ intersect on the circumcircle of the triangle $ABC$.
[i]Proposed by Hojoo Lee, Korea[/i]
Let $a_1, a_2, \ldots, a_n$ be $n$ positive integers, and let $b_1, b_2, \ldots, b_m$ be $m$ positive integers such that $a_1 a_2 \cdots a_n = b_1 b_2 \cdots b_m$. Prove that a rectangular table with $n$ rows and $m$ columns can be filled with positive integer entries in such a way that
* the product of the entries in the $i$-th row is $a_i$ (for each $i \in \left\{1,2,\ldots,n\right\}$);
* the product of the entries in the $j$-th row is $b_j$ (for each $i \in \left\{1,2,\ldots,m\right\}$).
Let $a,b$ be two positive integers, such that $ab\neq 1$. Find all the integer values that $f(a,b)$ can take, where \[ f(a,b) = \frac { a^2+ab+b^2} { ab- 1} . \]
Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps $L_0, \ldots, L_{n-1},$ each of of which can either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, $Step_0, Step_1, \ldots .$ If $L_{j-1}$ ($j$ is taken mod $n$) is ON then $Step_j$ changes the state of $L_j$ (it goes from ON to OFF or from OFF to ON) but does not change the state of any of the other lamps. If $L_{j-1}$ is OFF then $Step_j$ does not change anything at all. Show that:
(i) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again,
(ii) If $n$ has the form $2^k$ then all the lamps are ON after $n^2-1$ steps,
(iii) If $n$ has the form $2^k + 1$ then all lamps are ON after $n^2 - n + 1$ steps.
The following $100$ numbers are written on the board: $$2^1 - 1, 2^2 - 1, 2^3 - 1, \dots, 2^{100} - 1.$$
Alice chooses two numbers $a,b,$ erases them and writes the number $\dfrac{ab - 1}{a+b+2}$ on the board. She keeps doing this until a single number remains on the board.
If the sum of all possible numbers she can end up with is $\dfrac{p}{q}$ where $p, q$ are coprime, then what
is the value of $\log_{2}(p+q)$?
$n$ people (with names $1,2,\dots,n$) are around a table. Some of them are friends. At each step 2 friend can change their place. Find a necessary and sufficient condition for friendship relation between them that with these steps we can always reach to all of posiible permutations.
Each of $999$ numbers placed in a circular way is either $1$ or $-1$. (Both values appear). Consider the total sum of the products of every $10$ consecutive numbers.
$(a)$ Find the minimal possible value of this sum.
$(b)$ Find the maximal possible value of this sum.
Ivan and Kolya play a game, Ivan starts. Initially, the polynomial $x-1$ is written of the blackboard. On one move, the player deletes the current polynomial $f(x)$ and replaces it with $ax^{n+1}-f(-x)-2$, where $\deg(f)=n$ and $a$ is a real root of $f$. The player who writes a polynomial which does not have real roots loses. Can Ivan beat Kolya?
Five numbers 1,2,3,4,5 are written on a blackboard. A student may
erase any two of the numbers a and b on the board and write the
numbers a+b and ab replacing them. If this operation is performed repeatedly, can the numbers 21,27,64,180,540 ever appear on the board?
Consider the two square matrices
\[A=\begin{bmatrix} +1 & +1 &+1& +1 &+1 \\+1 &+1 &+1&-1 &-1 \\ +1 &-1&-1 &+1& +1 \\ +1 & -1 & -1 & -1 & +1 \\ +1 &+1&-1 &+1&-1 \end{bmatrix} \quad \text{ and } \quad B=\begin{bmatrix} +1 & +1 &+1& +1 &+1 \\+1 &+1 &+1&-1 &-1 \\ +1 &+1&-1& +1&-1 \\ +1 &-1& -1& +1& +1 \\ +1 & -1& +1&-1 &+1 \end{bmatrix}\]
with entries $+1$ and $-1$. The following operations will be called elementary:
(1) Changing signs of all numbers in one row;
(2) Changing signs of all numbers in one column;
(3) Interchanging two rows (two rows exchange their positions);
(4) Interchanging two columns.
Prove that the matrix $B$ cannot be obtained from the matrix $A$ using these operations.
Start with a finite sequence $ a_1,a_2,\dots,a_n$ of positive integers. If possible, choose two indices $ j < k$ such that $ a_j$ does not divide $ a_k$ and replace $ a_j$ and $ a_k$ by $ \gcd(a_j,a_k)$ and $ \text{lcm}\,(a_j,a_k),$ respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note: $ \gcd$ means greatest common divisor and lcm means least common multiple.)
Suppose that $n$ people $A_1$, $A_2$, $\ldots$, $A_n$, ($n \geq 3$) are seated in a circle and that $A_i$ has $a_i$ objects such that
\[ a_1 + a_2 + \cdots + a_n = nN \]
where $N$ is a positive integer. In order that each person has the same number of objects, each person $A_i$ is to give or to receive a certain number of objects to or from its two neighbours $A_{i-1}$ and $A_{i+1}$. (Here $A_{n+1}$ means $A_1$ and $A_n$ means $A_0$.) How should this redistribution be performed so that the total number of objects transferred is minimum?
The number 2021 is fantabulous. For any positive integer $m$, if any element of the set $\{m, 2m+1, 3m\}$ is fantabulous, then all the elements are fantabulous. Does it follow that the number $2021^{2021}$ is fantabulous?
On a flat plane in Camelot, King Arthur builds a labyrinth $\mathfrak{L}$ consisting of $n$ walls, each of which is an infinite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue.
At the intersection of two walls there are four corners: two diagonally opposite corners where a red side and a blue side meet, one corner where two red sides meet, and one corner where two blue sides meet. At each such intersection, there is a two-way door connecting the two diagonally opposite corners at which sides of different colours meet.
After Merlin paints the walls, Morgana then places some knights in the labyrinth. The knights can walk through doors, but cannot walk through walls.
Let $k(\mathfrak{L})$ be the largest number $k$ such that, no matter how Merlin paints the labyrinth $\mathfrak{L},$ Morgana can always place at least $k$ knights such that no two of them can ever meet. For each $n,$ what are all possible values for $k(\mathfrak{L}),$ where $\mathfrak{L}$ is a labyrinth with $n$ walls?
Numbers $1$ through $2014$ are written on a board. A valid operation is to erase two numbers $a$ and $b$ on the board and replace them with the greatest common divisor and the least common multiple of $a$ and $b$.
Prove that, no matter how many operations are made, the sum of all the numbers that remain on the board is always larger than $2014$ $\times$ $\sqrt[2014]{2014!}$
$L$ is a fullrank lattice in $\mathbb R^{2}$ and $K$ is a sub-lattice of $L$, that $\frac{A(K)}{A(L)}=m$. If $m$ is the least number that for each $x\in L$, $mx$ is in $K$. Prove that there exists a basis $\{x_{1},x_{2}\}$ for $L$ that $\{x_{1},mx_{2}\}$ is a basis for $K$.