Found problems: 815
Let $r>1$ be a rational number. Alice plays a solitaire game on a number line. Initially there is a red bead at $0$ and a blue bead at $1$. In a move, Alice chooses one of the beads and an integer $k \in \mathbb{Z}$. If the chosen bead is at $x$, and the other bead is at $y$, then the bead at $x$ is moved to the point $x'$ satisfying $x'-y=r^k(x-y)$.
Find all $r$ for which Alice can move the red bead to $1$ in at most $2021$ moves.
Each of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowed
Type 1) Choose a non-empty box $B_j$, $1\leq j \leq 5$, remove one coin from $B_j$ and add two coins to $B_{j+1}$;
Type 2) Choose a non-empty box $B_k$, $1\leq k \leq 4$, remove one coin from $B_k$ and swap the contents (maybe empty) of the boxes $B_{k+1}$ and $B_{k+2}$.
Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$ become empty, while box $B_6$ contains exactly $2010^{2010^{2010}}$ coins.
[i]Proposed by Hans Zantema, Netherlands[/i]
A positive integer $a$ is selected, and some positive integers are written on a board. Alice and Bob play the following game. On Alice's turn, she must replace some integer $n$ on the board with $n+a$, and on Bob's turn he must replace some even integer $n$ on the board with $n/2$. Alice goes first and they alternate turns. If on his turn Bob has no valid moves, the game ends.
After analyzing the integers on the board, Bob realizes that, regardless of what moves Alice makes, he will be able to force the game to end eventually. Show that, in fact, for this value of $a$ and these integers on the board, the game is guaranteed to end regardless of Alice's or Bob's moves.
Let $n$ be an odd positive integer. Some of the unit squares of an $n\times n$ unit-square board are colored green. It turns out that a chess king can travel from any green unit square to any other green unit squares by a finite series of moves that visit only green unit squares along the way. Prove that it can always do so in at most $\tfrac{1}{2}(n^2-1)$ moves. (In one move, a chess king can travel from one unit square to another if and only if the two unit squares share either a corner or a side.)
[i]Proposed by Nikolai Beluhov[/i]
Let $S$ be a nonempty set of positive integers. We say that a positive integer $n$ is [i]clean[/i] if it has a unique representation as a sum of an odd number of distinct elements from $S$. Prove that there exist infinitely many positive integers that are not clean.
Find all positive integers $(a,b,c)$ such that
$$ab-c,\quad bc-a,\quad ca-b$$ are all powers of $2$.
[i]Proposed by Serbia[/i]
Fix a positive real number $c>1$ and positive integer $n$. Initially, a blackboard contains the numbers $1,c,\ldots, c^{n-1}$. Every minute, Bob chooses two numbers $a,b$ on the board and replaces them with $ca+c^2b$. Prove that after $n-1$ minutes, the blackboard contains a single number no less than \[\left(\dfrac{c^{n/L}-1}{c^{1/L}-1}\right)^L,\] where $\phi=\tfrac{1+\sqrt 5}2$ and $L=1+\log_\phi(c)$.
A "[size=100][i]walking sequence[/i][/size]" is a sequence of integers with $a_{i+1} = a_i \pm 1$ for every $i$ .Show that there exists a sequence $b_1, b_2, . . . , b_{2016}$ such that for every walking sequence $a_1, a_2, . . . , a_{2016}$ where $1 \leq a_i \leq1010$, there is for some $j$ for which $a_j = b_j$ .
Let $M$ be a set of $n \ge 4$ points in the plane, no three of which are collinear. Initially these points are connected with $n$ segments so that each point in $M$ is the endpoint of exactly two segments. Then, at each step, one may choose two segments $AB$ and $CD$ sharing a common interior point and replace them by the segments $AC$ and $BD$ if none of them is present at this moment. Prove that it is impossible to perform $n^3 /4$ or more such moves.
[i]Proposed by Vladislav Volkov, Russia[/i]
To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.
The only pieces on an $8\times8$ chessboard are three rooks. Each moves along a row or a column without running to or jumping over another rook. The white rook starts at the bottom left corner, the black rook starts in the square directly above the white rook, and the red rook starts in the square directly to the right of the white rook. The white rook is to finish at the top right corner, the black rook in the square directly to the left of the white rook, and the red rook in the square directly below the white rook. At all times, each rook must be either in the same row or the same column as another rook. Is it possible to get the rooks to their destinations?
After elections, every parliament member (PM), has his own absolute rating. When the parliament set up, he enters in a group and gets a relative rating. The relative rating is the ratio of its own absolute rating to the sum of all absolute ratings of the PMs in the group. A PM can move from one group to another only if in his new group his relative rating is greater. In a given day, only one PM can change the group. Show that only a finite number of group moves is possible.
[i](A rating is positive real number.)[/i]
Let $n,k$ be positive integers such that $n>k$. There is a square-shaped plot of land, which is divided into $n\times n$ grid so that each cell has the same size. The land needs to be plowed by $k$ tractors; each tractor will begin on the lower-left corner cell and keep moving to the cell sharing a common side until it reaches the upper-right corner cell. In addition, each tractor can only move in two directions: up and right. Determine the minimum possible number of unplowed cells.
The operations below can be applied on any expression of the form \(ax^2+bx+c\).
$(\text{I})$ If \(c \neq 0\), replace \(a\) by \(4a-\frac{3}{c}\) and \(c\) by \(\frac{c}{4}\).
$(\text{II})$ If \(a \neq 0\), replace \(a\) by \(-\frac{a}{2}\) and \(c\) by \(-2c+\frac{3}{a}\).
$(\text{III}_t)$ Replace \(x\) by \(x-t\), where \(t\) is an integer. (Different values of \(t\) can be used.)
Is it possible to transform \(x^2-x-6\) into each of the following by applying some sequence of the above operations?
$(\text{a})$ \(5x^2+5x-1\)
$(\text{b})$ \(x^2+6x+2\)
Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.
For a finite simple graph $G$, we define $G'$ to be the graph on the same vertex set as $G$, where for any two vertices $u \neq v$, the pair $\{u,v\}$ is an edge of $G'$ if and only if $u$ and $v$ have a common neighbor in $G$.
Prove that if $G$ is a finite simple graph which is isomorphic to $(G')'$, then $G$ is also isomorphic to $G'$.
[i]Mehtaab Sawhney and Zack Chroman[/i]
We are given an infinite deck of cards, each with a real number on it. For every real number $x$, there is exactly one card in the deck that has $x$ written on it. Now two players draw disjoint sets $A$ and $B$ of $100$ cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions:
1. The winner only depends on the relative order of the $200$ cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner.
2. If we write the elements of both sets in increasing order as $A =\{ a_1 , a_2 , \ldots, a_{100} \}$ and $B= \{ b_1 , b_2 , \ldots , b_{100} \}$, and $a_i > b_i$ for all $i$, then $A$ beats $B$.
3. If three players draw three disjoint sets $A, B, C$ from the deck, $A$ beats $B$ and $B$ beats $C$ then $A$ also beats $C$.
How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets $A$ and $B$ such that $A$ beats $B$ according to one rule, but $B$ beats $A$ according to the other.
[i]Proposed by Ilya Bogdanov, Russia[/i]
On a blackboard there are $2010$ natural nonzero numbers. We define a "move" by erasing $x$ and $y$ with $y\neq0$ and replacing them with $2x+1$ and $y-1$, or we can choose to replace them by $2x+1$ and $\frac{y-1}{4}$ if $y-1$ is divisible by 4.
Knowing that in the beginning the numbers $2006$ and $2008$ have been erased, show that the original set of numbers cannot be attained again by any sequence of moves.
There are a) $2022$, b) $2023$ plates placed around a round table and on each of them there is one coin. Alice and Bob are playing a game that proceeds in rounds indefinitely as follows. In each round, Alice first chooses a plate on which there is at least one coin. Then Bob moves one coin from this plate to one of the two adjacent plates, chosen by him. Determine whether it is possible for Bob to select his moves so that, no matter how Alice selects her moves, there are never more than two coins on any plate.
Determine all integers $n\geqslant 2$ with the following property: every $n$ pairwise distinct integers whose sum is not divisible by $n$ can be arranged in some order $a_1,a_2,\ldots, a_n$ so that $n$ divides $1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n.$
[i]Arsenii Nikolaiev, Anton Trygub, Oleksii Masalitin, and Fedir Yudin[/i]
Determine all integers $n\geqslant 2$ with the following property: every $n$ pairwise distinct integers whose sum is not divisible by $n$ can be arranged in some order $a_1,a_2,\ldots, a_n$ so that $n$ divides $1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n.$
[i]Arsenii Nikolaiev, Anton Trygub, Oleksii Masalitin, and Fedir Yudin[/i]
$ 1994$ girls are seated at a round table. Initially one girl holds $ n$ tokens. Each turn a girl who is holding more than one token passes one token to each of her neighbours.
a.) Show that if $ n < 1994$, the game must terminate.
b.) Show that if $ n \equal{} 1994$ it cannot terminate.
Let $x_1,\cdots, x_n$ be nonzero vectors of a vector space $V$ and $\varphi:V\to V$ be a linear transformation such that $\varphi x_1 = x_1$, $\varphi x_k = x_k - x_{k-1}$ for $k = 2, 3,\ldots,n$.
Prove that the vectors $x_1,\ldots,x_n$ are linearly independent.
The numbers $1, 2, \dots , 50$ are written on a board. Letícia performs the following actions: she erases two numbers $a$ and $b$ on the board, writes the number $a+b$ on it and notes the number $ab(a+b)$ in her notebook. After performing these operations $49$ times, when there is only one number written on the board, Letícia calculates the sum $S$ of the $49$ numbers in the notebook.
a) Prove that $S$ doesn't depend on the order Letícia chooses the numbers to perform the operations.
b) Find the value of $S$.
In the following sum: $1 + 2 + 3 + 4 + 5 + 6$, if we remove the first two “+” signs, we obtain the new sum $123 + 4 + 5 + 6 = 138$. By removing three “$+$” signs, we can obtain $1 + 23 + 456 = 480$. Let us now consider the sum $1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13$, in which some “$+$” signs are to be removed. What are the three smallest multiples of $100$ that we can get in this way?