Olympiad problems

Kvant 2021, M2643

Tags: geometry , Kvant

The circles $\omega$ and $\Omega$ touch each other internally at $A{}$. In a larger circle $\Omega$ consider the chord $CD$ which touches $\omega$ at $B{}$. It is known that the chord $AB$ is not a diameter of $\omega$. The point $M{}$ is the middle of the segment $AB{}$. Prove that the circumcircle of the triangle $CMD$ passes through the center of $\omega$. [i]Proposed by P. Bibikov[/i]

Kvant 2021, M2678

Tags: geometry , Kvant

The triangle $ABC$ is given. Let $A', B'$ and $C'$ be the midpoints of the sides $BC, CA$ and $AB$ and $O_a,O_b$ and $O_c$ be the circumcenters of the triangles $CAC', ABA'$ and $BCB'$ respectively. Prove that the triangles $ABC$ and $O_aO_bO_c$ are similar. [i]Proposed by Don Luu (Vietnam)[/i]

Kvant 2021, M2656

Tags: number theory , Kvant

The increasing sequence of natural numbers $a_1,a_2,\ldots$ is such that for every $n>100$ the number $a_n$ is equal to the smallest natural number greater than $a_{n-1}$ and not divisible by any of the numbers $a_1,\ldots,a_{n-1}$. Prove that there is only a finite number of composite numbers in such a sequence. [i]Proposed by P. Kozhevnikov[/i]

Kvant 2021, M2670

Tags: geometry , combinatorial geometry , Kvant

There are 100 points on the plane so that any 10 of them are vertices of a convex polygon. Does it follow from this that all these points are the vertices of a convex 100-gon? [i]From the folklore[/i]

2021/2022 Tournament of Towns, P4

Tags: game , combinatorics , Tournament of Towns , Kvant

The number 7 is written on a board. Alice and Bob in turn (Alice begins) write an additional digit in the number on the board: it is allowed to write the digit at the beginning (provided the digit is nonzero), between any two digits or at the end. If after someone’s turn the number on the board is a perfect square then this person wins. Is it possible for a player to guarantee the win? [i]Alexandr Gribalko[/i]

2021/2022 Tournament of Towns, P5

Tags: combinatorics , Tournament of Towns , Process , Kvant

Consider the segment $[0; 1]$. At each step we may split one of the available segments into two new segments and write the product of lengths of these two new segments onto a blackboard. Prove that the sum of the numbers on the blackboard never will exceed $1/2$. [i]Mikhail Lukin[/i]

Kvant 2020, M1069

Tags: combinatorics , function , Kvant

Every day, some pairs of families living in a city may choose to exchange their apartments. A family may only participate in one exchange in a day. Prove that any complex exchange of apartments between several families can be carried out in two days. [i]Proposed by N. Konstantinov and A. Shnirelman[/i]

2020/2021 Tournament of Towns, P7

Tags: combinatorics , Combinatorial Number Theory , Tournament of Towns , Kvant

Let $p{}$ and $q{}$ be two coprime positive integers. A frog hops along the integer line so that on every hop it moves either $p{}$ units to the right or $q{}$ units to the left. Eventually, the frog returns to the initial point. Prove that for every positive integer $d{}$ with $d < p + q$ there are two numbers visited by the frog which differ just by $d{}$. [i]Nikolay Belukhov[/i]

Kvant 2021, M2671

Tags: algebra , number theory , Kvant

Let $x_1$ and $x_2$ be the roots of the equation $x^2-px+1=0$ where $p>2$ is a prime number. Prove that $x_1^p+x_2^p$ is an integer divisible by $p^2$. [i]From the folklore[/i]

Kvant 2022, M2723

Tags: combinatorics , Tournament of Towns , Kvant

It is known that among several banknotes of pairwise distinct face values (which are positive integers) there are exactly $N{}$ fakes. In a single test, a detector determines the sum of the face values of all real banknotes in an arbitrary set we have selected. Prove that by using the detector $N{}$ times, all fake banknotes can be identified, if a) $N=2$ and b) $N=3$. [i]Proposed by S. Tokarev[/i]

Kvant 2021, M2647

Tags: combinatorics , Kvant

For which natural numbers $n{}$ it is possible to mark several cells of an $n\times n$ board in such a way that there are an even number of marked cells in all rows and columns, and an odd number on all diagonals whose length is more than one cell? [i]Proposed by S. Berlov[/i]

Kvant 2020, M2609

Tags: combinatorics , board , Kvant

All cells of an $n\times n$ table are painted in several colors so that there is no monochromatic $2\times2$ square. A sequence of different cells $a_1,a_2,\ldots,a_k$ is called a [i]colorful[/i] if any two consecutive cells are adjacent and are painted in different colors. What is the largest $k{}$ for which there is a colorful sequence of length $k{}$ regardless of the coloring of the cells of the table? [i]Proposed by N. Belukhov[/i]

Russian TST 2019, P1

Tags: algebra , polynomial , Kvant

Let $t\in (1,2)$. Show that there exists a polynomial $P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ with the coefficients in $\{1,-1\}$ such that $\left|P(t)-2019\right| \leqslant 1.$ [i]Proposed by N. Safaei (Iran)[/i]

Kvant 2022, M2721

Tags: Kvant , number theory , polynomial

Let $n{}$ be a natural number and $f{}$ be polynomial with integer coefficients. It is known that for any integer $m{}$ there is an integer $k{}$ such that $f(k)-m$ is divisible by $n{}$. Prove that there exists a polynomial $g{}$ with integer coefficients such that $f(g(m))-m$ is divisible by $n{}$ for any integer $m{}$. [i]From the folklore[/i]

Kvant 2021, M2642

Tags: algebra , inequalities , Kvant

The nonzero numbers $x{}$ and $y{}$ satisfy the inequalities $x^{2n}-y^{2n}>x$ and $y^{2n}-x^{2n}>y$ for some natural number $n{}$. Can the product $xy$ be a negative number? [i]Proposed by N. Agakhanov[/i]

Kvant 2022, M2710

Tags: combinatorics , Kvant , board , geometry

We are given an $(n^2-1)\times(n^2-1)$ checkered board. A set of $n{}$ cells is called [i]progressive[/i] if the centers of the cells lie on a straight line and form $n-1$ equal intervals. Find the number of progressive sets. [i]Proposed by P. Kozhevnikov[/i]

Kvant 2019, M2561

Tags: combinatorics , phi function , Kvant

On the grid plane all possible broken lines with the following properties are constructed: each of them starts at the point $(0, 0)$, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding [i]worm[/i], the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles $2\times 1$ and $1\times 2$) in exactly $n > 2$ different ways, is equal to the number of positive integers that are less than n and relatively prime to $n$. (Ilke Chanakchi, Ralf Schiffler)

2019 Tournament Of Towns, 3

Tags: geometry , fixed , angle bisector , Fixed point , circles , Coloring , Kvant

Two not necessarily equal non-intersecting wooden disks, one gray and one black, are glued to a plane. An infinite angle with one gray side and one black side can be moved along the plane so that the disks remain outside the angle, while the colored sides of the angle are tangent to the disks of the same color (the tangency points are not the vertices). Prove that it is possible to draw a ray in the angle, starting from the vertex of the angle and such that no matter how the angle is positioned, the ray passes through some fixed point of the plane. (Egor Bakaev, Ilya Bogdanov, Pavel Kozhevnikov, Vladimir Rastorguev) (Junior version [url=https://artofproblemsolving.com/community/c6h2094701p15140671]here[/url]) [hide=note]There was a mistake in the text of the problem 3, we publish here the correct version. The solutions were estimated according to the text published originally.[/hide]

Kvant 2022, M2717

Tags: Kvant , geometry

In an acute triangle $ABC$ the heights $AD, BE$ and $CF$ intersecting at $H{}$. Let $O{}$ be the circumcenter of the triangle $ABC$. The tangents to the circle $(ABC)$ drawn at $B{}$ and $C{}$ intersect at $T{}$. Let $K{}$ and $L{}$ be symmetric to $O{}$ with respect to $AB$ and $AC$ respectively. The circles $(DFK)$ and $(DEL)$ intersect at a point $P{}$ different from $D{}$. Prove that $P, D$ and $T{}$ lie on the same line. [i]Proposed by Don Luu (Vietnam)[/i]

Kvant 2019, M2574

Tags: number theory , Kvant

Let $n>1$ be a positive integer. Show that the number of residues modulo $n^2$ of the elements of the set $\{ x^n + y^n : x,y \in \mathbb{N} \}$ is at most $\frac{n(n+1)}{2}$. [I]Proposed by N. Safaei (Iran)[/i]

Kvant 2020, M2615

Tags: geometry , Kvant

In the triangle $ABC$, the inscribed circle touches the sides $CA{}$ and $AB{}$ at the points $B_1{}$ and $C_1{}$, respectively. An arbitrary point $D{}$ is selected on the side $AB{}$. The point $L{}$ is the center of the inscribed circle of the triangle $BCD$. The bisector of the angle $ACD$ intersects the line $B_1C_1$ at the point $M{}$. Prove that $\angle CML=90^\circ$. [i]Proposed by Chan Quang Heung (Vietnam)[/i]

2019 IOM, 5

Tags: geometry , 3D geometry , pyramid , sphere , Kvant

We are given a convex four-sided pyramid with apex $S$ and base face $ABCD$ such that the pyramid has an inscribed sphere (i.e., it contains a sphere which is tangent to each race). By making cuts along the edges $SA,SB,SC,SD$ and rotating the faces $SAB,SBC,SCD,SDA$ outwards into the plane $ABCD$, we unfold the pyramid into the polygon $AKBLCMDN$ as shown in the figure. Prove that $K,L,M,N$ are concyclic. [i] Tibor Bakos and Géza Kós [/i]

Kvant 2022, M2726

Tags: Kvant , algebra

Let $a_1=1$ and $a_{n+1}=2/(2+a_n)$ for all $n\geqslant 1$. Similarly, $b_1=1$ and $b_{n+1}=3/(3+b_n)$ for all $n\geqslant 1$. Which is greater between $a_{2022}$ and $b_{2022}$? [i]Proposed by P. Kozhevnikov[/i]

2021/2022 Tournament of Towns, P2

Tags: board , Chess rook , Tournament of Towns , combinatorics , Kvant

There was a rook at some square of a $10 \times 10{}$ chessboard. At each turn it moved to a square adjacent by side. It visited each square exactly once. Prove that for each main diagonal (the diagonal between the corners of the board) the following statement is true: in the rook’s path there were two consecutive steps at which the rook first stepped away from the diagonal and then returned back to the diagonal. [i]Alexandr Gribalko[/i]

Kvant 2022, M2686

Tags: Kvant , combinatorics , graph theory

At a two-round volleyball tournament participated 99 teams. Each played a match at home and a match away. Each team won exactly half of their home matches and exactly half of their away matches. Prove that one of the teams beat another team twice. [i]Proposed by M. Antipov[/i]