Olympiad problems

Kvant 2021, M2676

Let $ABCD$ be a parallelogram and let $P{}$ be a point inside it such that $\angle PDA= \angle PBA$. Let $\omega_1$ be the excircle of $PAB$ opposite to the vertex $A{}$. Let $\omega_2$ be the incircle of the triangle $PCD$. Prove that one of the common tangents of $\omega_1$ and $\omega_2$ is parallel to $AD$. [i]Ivan Frolov[/i]

Kvant 2019, M2550

Tags: inequalities , algebra , Kvant

Let $a,b,c>0$ be real numbers. Prove that $$\frac{a+b}{\sqrt{b+c}}+\frac{b+c}{\sqrt{c+a}}+\frac{c+a}{\sqrt{a+b}}\geq \sqrt{2a}+ \sqrt{2b}+ \sqrt{2c}$$ Б. Кайрат (Казахстан), А. Храбров

Kvant 2021, M2662

Tags: geometry , Kvant

In the parallelogram $ABCD$, rays are released from its vertices towards its interior. The rays coming out of the vertices $A{}$ and $D{}$ intersect at $E{}$ and the rays coming out of the vertices $B{}$ and $C{}$ at point $F{}$. It is known that $\angle BAE=\angle BCF$ and $\angle CDE = \angle CBF$. Prove that $AB \parallel EF$. [i]Proposed by V. Eisenstadt[/i]

Kvant 2021, M2677

Tags: combinatorics , Tournament of Towns , Kvant

There are 20 buns with jam and 20 buns with treacle arranged in a row in random order. Alice and Bob take in turn a bun from any end of the row. Alice starts, and wants to finally obtain 10 buns of each type; Bob tries to prevent this. Is it true for any order of the buns that Alice can win no matter what are the actions of Bob? [i]Alexandr Gribalko[/i]

Kvant 2021, M2675

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 2021, M2634

Tags: parabola , geometry , Kvant

Consider a parabola. The [i]parabolic length[/i] of a segment is the length of the projection of this segment on a straight line perpendicular to the axis of symmetry of the parabola. In the parabola, two chords $AB$ and $CD$ are drawn, intersecting at the point $N{}$. Prove that the product of the parabolic lengths of the segments $AN$ and $BN$ is equal to the product of the parabolic lengths of the segments $CN$ and $DN$. [i]Proposed by M. Panov[/i]

Kvant 2019, M2577

Tags: geometry , isogonal conjugates , Kvant

Inside the acute-angled triangle $ABC$ we take $P$ and $Q$ two isogonal conjugate points. The perpendicular lines on the interior angle-bisector of $\angle BAC$ passing through $P$ and $Q$ intersect the segments $AC$ and $AB$ at the points $B_p\in AC$, $B_q\in AC$, $C_p\in AB$ and $C_q\in AB$, respectively. Let $W$ be the midpoint of the arc $BAC$ of the circle $(ABC)$. The line $WP$ intersects the circle $(ABC)$ again at $P_1$ and the line $WQ$ intersects the circle $(ABC)$ again at $Q_1$. Prove that the points $P_1$, $Q_1$, $B_p$, $B_q$, $C_p$ and $C_q$ lie on a circle. [i]Proposed by P. Bibikov[/i]

Kvant 2019, M2583

Tags: geometry , pantagon , Kvant

On the side $DE$ and on the diagonal $BE$ of the regular pentagon $ABCDE$ we consider the squares $DEFG$ and $BEHI$. [list=a] [*] Prove that $A,I,$ and $G$ are collinear. [*] Prove that on this line lies also the centre $O$ of the square $BDJK$. [/list]

Kvant 2021, M2637

Tags: game , board , combinatorics , Kvant

A table with three rows and 100 columns is given. Initially, in the left cell of each row there are $400\cdot 3^{100}$ chips. At one move, Petya marks some (but at least one) chips on the table, and then Vasya chooses one of the three rows. After that, all marked chips in the selected row are shifted to the right by a cell, and all marked chips in the other rows are removed from the table. Petya wins if one of the chips goes beyond the right edge of the table; Vasya wins if all the chips are removed. Who has a winning strategy? [i]Proposed by P. Svyatokum, A. Khuzieva and D. Shabanov[/i]

2019 Tournament Of Towns, 7

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)

Kvant 2021, M2653

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 2022, M2711

Tags: geometry , Kvant

Three pairwise externally tangent circles $\omega_1,\omega_2$ and $\omega_3$ are given. Let $K_{12}$ be the point of tangency between $\omega_1$ and $\omega_2$ and define $K_{23}$ and $K_{31}$ similarly. Consider the point $A_1$ on $\omega_1$. Let $A_2$ be the second intersection of the line $A_1K_{12}$ with $\omega_2$. The line $A_2K_{23}$ then intersects $\omega_3$ the second time at $A_3$, and then line $A_3K_{31}$ intersects $\omega_1$ again at $A_4$ and so on. [list=a] [*]Prove that after six steps, the process will loop; that is, $A_7=A_1$. [*]Prove that the lines $A_1A_2$ and $A_4A_5$ are perpendicular. [*]Prove that the triples of lines $A_1A_2,A_3A_4$ and $A_5A_6$ and $A_2A_3,A_4A_5$ and $A_6A_1$ intersect at two diametrically opposite points on the circle $(K_{12}K_{23}K_{31})$. [/list] [i]Proposed by E. Morozov[/i]

2022 Saint Petersburg Mathematical Olympiad, 7

Tags: combinatorics , graph theory , algebra , Kvant

Given is a graph $G$ of $n+1$ vertices, which is constructed as follows: initially there is only one vertex $v$, and one a move we can add a vertex and connect it to exactly one among the previous vertices. The vertices have non-negative real weights such that $v$ has weight $0$ and each other vertex has a weight not exceeding the avarage weight of its neighbors, increased by $1$. Prove that no weight can exceed $n^2$.

Kvant 2021, M2649

Tags: combinatorics , combinatorial geometry , Kvant

Initially, the point-like particles $A, B$ and $C{}$ are located respectively at the points $(0,0), (1,0)$ and $(0,1)$ in the coordinate plane. Every minute some two particles repel each other along the straight line connecting their current positions, moving the same (positive) distance. [list=a] [*]Can the particle $A{}$ be at the point $(3,3)$? What about the point $(2,3)$? [*]Can the particles $B{}$ and $C{}$ be at the same time at the points $(0,100)$ and $(100,0)$ respectively? [/list] [i]Proposed by K. Krivosheev[/i]

Kvant 2019, M2549

Tags: number theory , Kvant

For each non-negative integer $n$ find the sum of all $n$-digit numbers with the digits in a decreasing sequence. [I]Proposed by P. Kozhevnikov[/I]

Kvant 2020, M2618

Tags: algebra , floor function , Kvant

For a given number $\alpha{}$ let $f_\alpha$ be a function defined as \[f_\alpha(x)=\left\lfloor\alpha x+\frac{1}{2}\right\rfloor.\]Let $\alpha>1$ and $\beta=1/\alpha$. Prove that for any natural $n{}$ the relation $f_\beta(f_\alpha(n))=n$ holds. [i]Proposed by I. Dorofeev[/i]

Kvant 2022, M2697

Tags: Kvant , combinatorics

There are some gas stations on a circular highway. The total amount of gasoline in them is enough for two laps. Two drivers want to refuel at one station and starting from it, go in different directions, both of them completing an entire lap. Along the way, they can refuel at other stations, without necessarily taking all the gasoline. Prove that drivers will always be able to do this. [i]Proposed by I. Bogdanov[/i]

Kvant 2019, M2560

Tags: combinatorics , Kvant

A dog has infinitely many pieces of meat, but on each piece of meat there is a fly. At each move, the dog does the following: [list=1] [*] He eats a piece of meat together with all flies lying on it; [*] He moves a fly from a piece of meat to another. [/list] The dog doesn't want to eat more than one milion flies. Prove that he cannot ensure that each piece of meat is eaten at some point. [i]Proposed by I. Mitrofanov[/i]

Kvant 2019, M2558

Tags: Line , game , game strategy , combinatorics , Tournament of Towns , ToT , Kvant

$2019$ point grasshoppers sit on a line. At each move one of the grasshoppers jumps over another one and lands at the point the same distance away from it. Jumping only to the right, the grasshoppers are able to position themselves so that some two of them are exactly $1$ mm apart. Prove that the grasshoppers can achieve the same, jumping only to the left and starting from the initial position. (Sergey Dorichenko)

Kvant 2019, M2551

Tags: combinatorics , Kvant

The vertices of a convex polygon with $n\geqslant 4$ sides are coloured with black and white. A diagonal is called [i]multicoloured[/i] if its vertices have different colours. A colouring of the vertices is [i]good[/i] if the polygon can be partitioned into triangles by using only multicoloured diagonals which do not intersect in the interior of the polygon. Find the number of good colourings. [i]Proposed by S. Berlov[/i]

Kvant 2019, M2579

Tags: combinatorics , Kvant

There are 100 students taking an exam. The professor calls them one by one and asks each student a single person question: “How many of 100 students will have a “passed” mark by the end of this exam?” The students answer must be an integer. Upon receiving the answer, the professor immediately publicly announces the student’s mark which is either “passed” or “failed.” After all the students have got their marks, an inspector comes and checks if there is any student who gave the correct answer but got a “failed” mark. If at least one such student exists, then the professor is suspended and all the marks are replaced with “passed.” Otherwise no changes are made. Can the students come up with a strategy that guarantees a “passed” mark to each of them? [i] Denis Afrizonov [/i]

Kvant 2019, M2580

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, M2696

Tags: Kvant , number theory

Does there exist a sequence of natural numbers $a_1,a_2,\ldots$ such that the number $a_i+a_j$ has an even number of different prime divisors for any two different natural indices $i{}$ and $j{}$? [i]From the folklore[/i]

Kvant 2020, M818

Tags: combinatorics , Coloring , Kvant

Some $k{}$ vertices of a regular $n{}$-gon are colored red. We will call a coloring [i]uniform[/i] if for any $m$ the number of red vertices in any two sets of $m$ consecutive vertices of the $n{}$-gon coincide or differ by 1. Prove that a uniform coloring exists for any $k<n$ and is unique, up to rotations of the $n{}$-gon. [i]Proposed by M. Kontsevich[/i]

Kvant 2021, M2666

Tags: number theory , Kvant

Let $x{}$ and $y{}$ be natural numbers greater than 1. It turns out that $x^2+y^2-1$ is divisible by $x+y-1$. Prove that $x+y-1$ is composite. [i]From the folklore[/i]