Olympiad problems

Kvant 2023, M2730

Tags: Kvant , combinatorics

On each cell of a $3\times 6$ the board lies one coin. It is known that some two coins lying on adjacent cells are fake. They have the same weigh, but are lighter than the real ones. All the other coins are real. How can one find both counterfeit coins in three weightings on a double-pan balance, without using weights? [i]Proposed by K. Knop[/i]

Russian TST 2022, P1

Tags: Kvant , geometry

A convex 51-gon is given. For each of its vertices and each diagonal that does not contain this vertex, we mark in red a point symmetrical to the vertex relative to the middle of the diagonal. Prove that strictly inside the polygon there are no more than 20400 red dots. [i]Proposed by P. Kozhevnikov[/i]

Kvant 2021, M2664

Tags: combinatorial geometry , Kvant , combinatorics

The point $O{}$ is given in the plane. Find all natural numbers $n{}$ for which $n{}$ points in the plane can be colored red, so that for any two red points $A{}$ and $B{}$ there is a third red point $C{}$ is such that $O{}$ lies strictly inside the triangle $ABC$. [i]From the folklore[/i]

Kvant 2021, M2665

Tags: algebra , polynomial , Kvant

The polynomials $f(x)$ and $g(x)$ are given. The points $A_1(f(1),g(1)),\ldots,A_n(f(n),g(n))$ are marked on the coordinate plane. It turns out that $A_1\ldots A_n$ is a regular $n{}$-gon. Prove that the degree of at least one of $f{}$ and $g{}$ is at least $n-1$. [i]Proposed by V. Bragin[/i]

Kvant 2020, M2593

Tags: combinatorics , Coloring , Kvant

Each vertex of a regular polygon is colored in one of three colors so that an odd number of vertices are colored in each of the three colors. Prove that the number of isosceles triangles whose vertices are colored in three different colors is odd. [i]From foreign Olympiads[/i]

Kvant 2020, M1000

Tags: geometry , circles , Kvant

A polyline $AMB$ is inscribed in the arc $AB{}$, consisting of two segments, and $AM>MB$. Let $K$ be the midpoint of the arc $AB{}$. Prove that the foot $H{}$ of the perpendicular from $K$ onto $AM$ divides the polyline in two equal segments: \[AH=HM+MB.\][i]Discovered by Archimedes[/i]

Kvant 2023, M2733

Tags: Kvant , geometry

A convex 51-gon is given. For each of its vertices and each diagonal that does not contain this vertex, we mark in red a point symmetrical to the vertex relative to the middle of the diagonal. Prove that strictly inside the polygon there are no more than 20400 red dots. [i]Proposed by P. Kozhevnikov[/i]

Kvant 2022, M2724

Tags: number theory , Tournament of Towns , sum of digits , Kvant

In an infinite arithmetic progression of positive integers there are two integers with the same sum of digits. Will there necessarily be one more integer in the progression with the same sum of digits? [i]Proposed by A. Shapovalov[/i]

Kvant 2022, M2727

Tags: Kvant , geometry , areas

A convex quadrilateral $ABCD$ is given. Let $O_a$ be the circumcenter of the triangle $DBC$, and define $O_b,O_c$ and $O_d$ similarly. The points $O_a, O_b, O_c, O_d$ are the vertices of a convex quadrilateral. Prove that its area is equal to half of the absolute value of the difference between the areas of $AO_bCO_d$ and $BO_cDO_a$. [i]Proposed by V. Dubrovsky[/i]

2022/2023 Tournament of Towns, P5

Tags: number theory , Tournament of Towns , sum of digits , Kvant

In an infinite arithmetic progression of positive integers there are two integers with the same sum of digits. Will there necessarily be one more integer in the progression with the same sum of digits? [i]Proposed by A. Shapovalov[/i]

Kvant 2022, M2692

Tags: Kvant , geometry , porism , hexagon

In the circle $\Omega$ the hexagon $ABCDEF$ is inscribed. It is known that the point $D{}$ divides the arc $BC$ in half, and the triangles $ABC$ and $DEF$ have a common inscribed circle. The line $BC$ intersects segments $DF$ and $DE$ at points $X$ and $Y$ and the line $EF$ intersects segments $AB$ and $AC$ at points $Z$ and $T$ respectively. Prove that the points $X, Y, T$ and $Z$ lie on the same circle. [i]Proposed by D. Brodsky[/i]

Kvant 2020, M2592

Tags: number theory , polynomial , Kvant

Let $P(x)$ be a polynomial taking integer values at integer inputs. Are there infinitely many natural numbers that are not representable in the form $P(k)-2^n$ where $n{}$ and $k{}$ are non-negative integers? [i]Proposed by F. Petrov[/i]

Kvant 2019, M2582

Tags: algebra , combinatorics , Kvant

An integer $1$ is written on the blackboard. We are allowed to perform the following operations:to change the number $x$ to $3x+1$ of to $[\frac{x}{2}]$. Prove that we can get all positive integers using this operations.

Kvant 2020, M2625

Tags: combinatorial geometry , combinatorics , Kvant

A connected checkered figure is drawn on a checkered paper. It is known that the figure can be cut both into $2\times 2$ squares and into (possibly rotated) [url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Tetromino-skew2.svg/1200px-Tetromino-skew2.svg.png]skew-tetrominoes[/url]. Prove that there is a hole in the figure. [i]Proposed by Y. Markelov and A. Sairanov[/i]

2019 Tournament Of Towns, 4

Tags: combinatorics , Kvant

A polygon is given in which any two adjacent sides are perpendicular. We call its two vertices non-friendly if the bisectors of the polygon emerging from these vertices are perpendicular. Prove that for any vertex the number of vertices that are not friends with it is even.

Kvant 2021, M2669

Tags: number theory , Kvant

Prove that for any natural number $n{}$ the numbers $1,2,\ldots,n$ can be divided into several groups so that the sum of the numbers in each group is equal to a power of three. [i]Proposed by V. Novikov[/i]

Kvant 2019, M2588

Tags: tangential , cyclic quadrilateral , Cyclic , geometry , area , Kvant

The point $M$ inside a convex quadrilateral $ABCD$ is equidistant from the lines $AB$ and $CD$ and is equidistant from the lines $BC$ and $AD$. The area of $ABCD$ occurred to be equal to $MA\cdot MC +MB \cdot MD$. Prove that the quadrilateral $ABCD$ is a) tangential (circumscribed), b) cyclic (inscribed). (Nairi Sedrakyan)

2019 Tournament Of Towns, 2

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)

2019 IOM, 2

Tags: combinatorics , Kvant

In a social network with a fixed finite setback of users, each user had a fixed set of [i]followers[/i] among the other users. Each user has an initial positive integer rating (not necessarily the same for all users). Every midnight, the rating of every user increases by the sum of the ratings that his followers had just before midnight. Let $m$ be a positive integer. A hacker, who is not a user of the social network, wants all the users to have ratings divisible by $m$. Every day, he can either choose a user and increase his rating by 1, or do nothing. Prove that the hacker can achieve his goal after some number of days. [i]Vladislav Novikov[/i]

2019 Caucasus Mathematical Olympiad, 2

Tags: number theory , LCM , least common multiple , Kvant

Determine if there exist five consecutive positive integers such that their LCM is a perfect square.

2019 IOM, 4

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

Tags: algebra , Polynomials , Kvant

Let $a_1,...,a_n$ be $n$ real numbers. If for each odd positive integer $k\leqslant n$ we have $a_1^k+a_2^k+\ldots+a_n^k=0$, then for each odd positive integer $k$ we have $a_1^k+a_2^k+\ldots+a_n^k=0$. [i]Proposed by M. Didin[/i]

Kvant 2019, M2587

Tags: combinatorics unsolved , algorithm , combinatorics , Kvant

In each cell, a strip of length $100$ is worth a chip. You can change any $2$ neighboring chips and pay $1$ rouble, and you can also swap any $2$ chips for free, between which there are exactly $4$ chips. For what is the smallest amount of rubles you can rearrange chips in reverse order?

Kvant 2019, M2544

Tags: algebra , polynomial , inequalities , Kvant

Let $P(x)=x^n +a_1x^{n-1}+a_2x^{n-2}+\ldots+a_{n-1}x+a_n$ be a polynomial of degree $n$ and $n$ real roots, all of them in the interval $(0,1)$. Prove that for all $k=\overline{1,n}$ the following inequality holds: \[(-1)^k(a_k+a_{k+1}+\ldots+a_n)>0.\] [i]Proposed by N. Safaei (Iran)[/i]

Kvant 2022, M2689

Tags: combinatorics , Kvant

There are 1000 gentlemen listed in the register of a city with numbers from 1 to 1000. Any 720 of them form a club. The mayor wants to impose a tax on each club, which is paid by all club members in equal shares (the tax is an arbitrary non-negative real number). At the same time, the total tax paid by a gentleman should not exceed his number in the register. What is the largest tax the mayor can collect? [i]Proposed by I. Bogdanov[/i]