Olympiad problems

Kvant 2021, M2673

There are $n{}$ passengers in the queue to board a $n{}$-seat plane. The first one in the queue is an absent-minded old lady who, after boarding the plane, sits down at a randomly selected place. Each subsequent passenger sits in his seat if it is free, and in a random seat otherwise. How many passengers will be out of their seats on average? [i]Proposed by A. Zaslavsky[/i]

Kvant 2019, M2575

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

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

Tags: geometry , geometric inequality , Kvant

The circle $\omega{}$ is inscribed in the quadrilateral $ABCD$. Prove that the diameter of the circle $\omega{}$ does not exceed the length of the segment connecting the midpoints of the sides $BC$ and $AD$. [i]Proposed by O. Yuzhakov[/i]

Kvant 2020, M2608

Tags: geometry , polygon , Kvant

A hinged convex quadrilateral was made of four slats. Then, two points on its opposite sides were connected with another slat, but the structure remained non-rigid. Does it follow from this that this quadrilateral is a parallelogram? [i]Proposed by A. Zaslavsky[/i] [center][img width="40"]https://i.ibb.co/dgqSvLQ/Screenshot-2023-03-09-231327.png[/img][/center]

Kvant 2019, M2548

Tags: number theory , Kvant

A non-negative integer $n$ is called [I]redundant[/I] if the sum of all his proper divisors is bigger than $n$. Prove that for each non-negative integer $N$ there are $N$ consecutive redundant non-negative integers. [I]Proposed by V. Bragin[/I]

2019 Tournament Of Towns, 3

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.

2019 Caucasus Mathematical Olympiad, 7

Tags: geometry , Kvant

On sides $BC$, $CA$, $AB$ of a triangle $ABC$ points $K$, $L$, $M$ are chosen, respectively, and a point $P$ is inside $ABC$ is chosen so that $PL\parallel BC$, $PM\parallel CA$, $PK\parallel AB$. Determine if it is possible that each of three trapezoids $AMPL$, $BKPM$, $CLPK$ has an inscribed circle.

Kvant 2020, M2602

Tags: geometry , combinatorial geometry , Kvant

For a given natural number $k{}$, a convex polygon is called $k{}$[i]-triangular[/i] if it is the intersection of some $k{}$ triangles. [list=a] [*]What is the largest $n{}$ for which there exist a $k{}$-triangular $n{}$-gon? [*]What is the largest $n{}$ for which any convex $n{}$-gon is $k{}$-triangular? [/list] [i]Proposed by P. Kozhevnikov[/i]

Kvant 2019, M2576

Tags: combinatorics , dominoes , Kvant

A $8\times 8$ board is divided in dominoes (rectangles with dimensions $1 \times 2$ or $2 \times 1$). [list=a] [*] Prove that the total length of the border between horizontal and vertical dominoes is at most $52$. [*] Determine the maximum possible total length of the border between horizontal and vertical dominoes. [/list] [i]Proposed by B. Frenkin, A. Zaslavsky, E. Arzhantseva[/i]

Kvant 2020, M2616

Tags: number theory , Divisibility , Kvant

Let $p>5$ be a prime number. Prove that the sum \[\left(\frac{(p-1)!}{1}\right)^p+\left(\frac{(p-1)!}{2}\right)^p+\cdots+\left(\frac{(p-1)!}{p-1}\right)^p\]is divisible by $p^3$.

Kvant 2019, M2545

Tags: geometry , incenter , Kvant

Let $N,K,L$ be points on the sides $\overline{AB}, \overline{BC}, \overline{CA}$ respectively. Suppose $AL=BK$ and $\overline{CN}$ is the internal bisector of angle $ACB$. Let $P$ be the intersection of lines $\overline{AK}$ and $\overline{BL}$ and let $I,J$ be the incenters of triangles $APL$ and $BPK$ respectively. Let $Q$ be the intersection of lines $\overline{IJ}$ and $\overline{CN}$. Prove that $IP=JQ$.

Kvant 2020, M2628

Tags: combinatorics , weights , Kvant

There are $m$ identical two-pan weighting scales. One of them is broken and it shows any outcome, at random. The other scales always show the correct outcome. Moreover, the weight of the broken scale differs from those of the other scales, which are all equal. At a move, we may choose a scale and place some of the other scales on its pans. Determine the greatest value of $m$ for which we may find the broken scale with no more than three moves. [i]Proposed by A. Gribalko and O. Manzhina[/i]

Kvant 2022, M2713

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

Tags: geometry , inradius , Kvant

The triangle $ABC$ is given. Consider the point $C'{}$ on the side $AB$ such that the segment $CC'$ divides the triangle into two triangles with equal radii of inscribed circles. Denote by $t_c$ the length of the segment $CC'$. Similarly, we define $t_a$ and $t_b$. Express the area of triangle $ABC$ in terms of $t_a,t_b$ and $t_c$. [i]Proposed by K. Mosevich[/i]

Kvant 2023, M2731

Tags: Kvant , number theory , Perfect Squares

There are 2023 natural written in a row. The first number is 12, and each number starting from the third is equal to the product of the previous two numbers, or to the previous number increased by 4. What is the largest number of perfect squares that can be among the 2023 numbers? [i]Based on the British Mathematical Olympiad[/i]

Kvant 2022, M2715

Tags: Kvant , combinatorics , board

A lame rook lies on a $9\times 9$ chessboard. It can move one cell horizontally or vertically. The rook made $n{}$ moves, visited each cell at most once, and did not make two moves consecutively in the same direction. What is the largest possible value of $n{}$? [i]From the folklore[/i]

Kvant 2022, M2694

Tags: Kvant , number theory

Call a natural number $n{}$ [i]interesting[/i] if any natural number not exceeding $n{}$ can be represented as the sum of several (possibly one) pairwise distinct positive divisors of $n{}$. [list=a] [*]Find the largest three-digit interesting number. [*]Prove that there are arbitrarily large interesting numbers other than the powers of two. [/list] [i]Proposed by N. Agakhanov[/i]

Kvant 2020, M2617

Tags: combinatorial geometry , combinatorics , Kvant

The points in the plane are painted in 100 colors. Prove that there are three points of the same color that are the vertices of a triangle of area 1. [i]Proposed by V. Bragin[/i]

2020 Brazil Cono Sur TST, 3

Tags: Sequences , algebra , number theory , Kvant

Let $a_1,a_2, \cdots$ be a sequence of integers that satisfies: $a_1=1$ and $a_{n+1}=a_n+a_{\lfloor \sqrt{n} \rfloor} , \forall n\geq 1 $. Prove that for all positive $k$, there is $m \geq 1$ such that $k \mid a_m$.

Kvant 2022, M2725

Tags: Kvant , geometry

Two equally oriented regular $2n$-gons $A_1A_2\ldots A_{2n}$ and $B_1B_2\ldots B_{2n}$ are given. The perpendicular bisectors $\ell_i$ of the segments $A_iB_i$ are drawn. Let the lines $\ell_i$ and $\ell_{i+1}$ intersect at the point $K_i$ (hereafter we reduce indices modulo $2n$). Denote by $m_i$ the line $K_iK_{i+n}$. Prove that $n{}$ lines $m_i$ intersect at one point and at that the angles between the lines $m_i$ and $m_{i+1}$ are equal. [i]Proposed by Chan Quang Hung (Vietnam)[/i]

Kvant 2021, M2679

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]

Kvant 2019, M2554

Tags: geometry , Kvant

Two externally tangent circles $\Omega_1$ and $\Omega_2$ are internally tangent to the circle $\Omega$ at $A$ and $B$, respectively. If the line $AB$ intersects $\Omega_1$ again at $D$ and $C\in\Omega_1\cap\Omega_2$, show that $\angle BCD=90^\circ$. [i]Proposed by V. Rastorguev[/i]

Kvant 2019, M2552

Tags: Sequences , algebra , number theory , Kvant

Let $a_1,a_2, \cdots$ be a sequence of integers that satisfies: $a_1=1$ and $a_{n+1}=a_n+a_{\lfloor \sqrt{n} \rfloor} , \forall n\geq 1 $. Prove that for all positive $k$, there is $m \geq 1$ such that $k \mid a_m$.

Kvant 2022, M2728

Tags: Kvant , geometry , polygon

Given is a natural number $n\geqslant 3$. Find the smallest $k{}$ for which the following statement is true: for any $n{}$-gon and any two points inside it there is a broken line with $k{}$ segments connecting these points, lying entirely inside the $n{}$-gon. [i]Proposed by L. Emelyanov[/i]