Kvant 2021

Part of Kvant Problems

Subcontests

(44)

1

Geometry with parabola

Consider a parabola. The parabolic length 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

CD

are drawn, intersecting at the point

N{}

. Prove that the product of the parabolic lengths of the segments

AN

BN

is equal to the product of the parabolic lengths of the segments

CN

DN

.
Proposed by M. Panov

1

Sum of inradii does not exceed M

In the triangle

ABC

, the lengths of the sides

BC, CA

AB

a,b

c{}

respectively. Several segments are drawn from the vertex

C{}

, which cut the triangle

ABC

into several triangles. Find the smallest number

M{}

for which, with each such cut, the sum of the radii of the circles inscribed in triangles does not exceed

M{}

.
Porposed by O. Titov

1

Are there infinitely many simple primes?

We call a natural number

p{}

simple if for any natural number

k{}

2\leqslant k\leqslant \sqrt{p}

\{p/k\}\geqslant 0,01

holds. Is the set of simple prime numbers finite?
Proposed by M. Didin

1

Game on 3x100 board

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?
Proposed by P. Svyatokum, A. Khuzieva and D. Shabanov

1

Weird inequality

The nonzero numbers

x{}

y{}

satisfy the inequalities

x^{2n}-y^{2n}>x

y^{2n}-x^{2n}>y

for some natural number

n{}

. Can the product

xy

be a negative number?
Proposed by N. Agakhanov

1

Internal tangent circles

\omega

\Omega

touch each other internally at

A{}

. In a larger circle

\Omega

consider the chord

CD

\omega

B{}

. It is known that the chord

AB

is not a diameter of

\omega

M{}

is the middle of the segment

AB{}

. Prove that the circumcircle of the triangle

CMD

passes through the center of

\omega

.
Proposed by P. Bibikov

1

Game on 100x100 board

Petya and Vasya are playing on an

100\times 100

board. Initially, all the cells of the board are white. With each of his moves, Petya paints one or more white cells standing on the same diagonal in black. With each of his moves, Vasya paints one or more white cells standing on the same column in black. Petya makes the first move. The one who can't make a move loses. Who has a winning strategy?
Proposed by M. Didin

1

NT game with common multiples

Vitya wrote down

n{}

different natural numbers in his notebook. For each pair of numbers from the notebook, he wrote out their smallest common multiple on the board. Could it happen for some

n>100

n(n-1)/2

numbers on the board are (in some order) consecutive terms of a non-constant arithmetic progression?
Proposed by S. Berlov

1

Bank account balance fluctuations

Koshchey opened an account at the bank. Initially, it had 0 rubles. On the first day, Koshchey puts

k>0

rubles in, and every next day adds one ruble more there than the day before. Each time after Koshchey deposits money into the account, the total amount in the account is divided by two by the bank. Find all such

k{}

for which the amount on the account will always be an integer number of rubles.
Proposed by S. Berlov

1

Parity differs from lines to diagonals

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?
Proposed by S. Berlov

1

Geometry with qual inradii

ABC

is given. Consider the point

C'{}

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

t_b

. Express the area of triangle

ABC

t_a,t_b

t_c

.
Proposed by K. Mosevich

1

Math with particles

Initially, the point-like particles

A, B

C{}

are located respectively at the points

(0,0), (1,0)

(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.
[*]Can the particle

A{}

be at the point

(3,3)

? What about the point

(2,3)

? [*]Can the particles

B{}

C{}

be at the same time at the points

(0,100)

(100,0)

respectively?
Proposed by K. Krivosheev

1

Sequence has finitely many composite numbers

The increasing sequence of natural numbers

a_1,a_2,\ldots

is such that for every

n>100

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.
Proposed by P. Kozhevnikov

1

Rays from vertices of parallelogram

In the parallelogram

ABCD

, rays are released from its vertices towards its interior. The rays coming out of the vertices

A{}

D{}

E{}

and the rays coming out of the vertices

B{}

C{}

F{}

. It is known that

\angle BAE=\angle BCF

\angle CDE = \angle CBF

AB \parallel EF

.
Proposed by V. Eisenstadt

1

Point always lies inside triangle

O{}

is given in the plane. Find all natural numbers

n{}

n{}

points in the plane can be colored red, so that for any two red points

A{}

B{}

there is a third red point

C{}

O{}

lies strictly inside the triangle

ABC

.
From the folklore

1

Polynomials yield regular polygon

The polynomials

f(x)

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

n{}

-gon. Prove that the degree of at least one of

f{}

g{}

n-1

.
Proposed by V. Bragin

1

Divisibility with quadratic form

x{}

y{}

be natural numbers greater than 1. It turns out that

x^2+y^2-1

is divisible by

x+y-1

x+y-1

is composite.
From the folklore

1

Identity with bicentric quadrilateral

Two circles are given for which there is a family of quadrilaterals circumscribed around the first circle and inscribed in the second. Let's denote by

a, b, c

d{}

the consecutive lengths of the sides of one of these quadrilaterals. Prove that the sum

\frac{a}{c}+\frac{c}{a}+\frac{b}{d}+\frac{d}{b}

does not depend on the choice of the quadrilateral.
Proposed by I. Weinstein

1

Groups with sum equal to a power of three

Prove that for any natural number

n{}

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.
Proposed by V. Novikov

1

Must the 100-gon be convex?

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?
From the folklore

1

Roots raised to the p-th power

x_1

x_2

be the roots of the equation

x^2-px+1=0

p>2

is a prime number. Prove that

x_1^p+x_2^p

is an integer divisible by

p^2

.
From the folklore

1

Incircle geometry

Let the inscribed circle

\omega

of the triangle

ABC

I{}

and touch the sides

BC, CA

AB

D, E

F{}

respectively. Let

M{}

N{}

be points on the straight line

EF

BM \parallel AC

CN \parallel AB

P{}

Q{}

be points on the segments

DM{}

DN{}

, respectively, such that

BP \parallel CQ

. Prove that the intersection point of the lines

PF

QE

\omega

.
Proposed by Don Luu (Vietnam)

1

An absent-minded old lady

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?
Proposed by A. Zaslavsky

1

Two similar triangles

ABC

A', B'

C'

be the midpoints of the sides

BC, CA

AB

O_a,O_b

O_c

be the circumcenters of the triangles

CAC', ABA'

BCB'

respectively. Prove that the triangles

ABC

O_aO_bO_c

are similar.
Proposed by Don Luu (Vietnam)

1

Equality in regular (2^n-1)-gon

n>1

be a natural number and

A_0A_1\ldots A_{2^n-2}

be a regular polygon. Prove that

\frac{1}{A_0A_1}=\frac{1}{A_0A_2}+\frac{1}{A_0A_4}+\frac{1}{A_0A_8}+\cdots+\frac{1}{A_0A_{2^{n-1}}}.

Proposed by Le Hoang and Ngoc Thai (Vietnam)

1

Numbers raised to themselves

Find all pairs of distinct rational numbers

(a,b)

a^a=b^b

.
Proposed by I. Dorofeev

1

Nice combinatorial NT

p{}

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{}

d < p + q

there are two numbers visited by the frog which differ just by

d{}

.
Nikolay Belukhov

1

When can the tourists select their rooms

A hundred tourists arrive to a hotel at night. They know that in the hotel there are single rooms numbered as

1, 2, \ldots , n

, and among them

k{}

(the tourists do not know which) are under repair, the other rooms are free. The tourists, one after another, check the rooms in any order (maybe different for different tourists), and the first room not under repair is taken by the tourist. The tourists don’t know whether a room is occupied until they check it. However it is forbidden to check an occupied room, and the tourists may coordinate their strategy beforehand to avoid this situation. For each

k{}

find the smallest

n{}

for which the tourists may select their rooms for sure.
Fyodor Ivlev

1

Number of sweets received by the boys is invariant

In a room there are several children and a pile of 1000 sweets. The children come to the pile one after another in some order. Upon reaching the pile each of them divides the current number of sweets in the pile by the number of children in the room, rounds the result if it is not integer, takes the resulting number of sweets from the pile and leaves the room. All the boys round upwards and all the girls round downwards. The process continues until everyone leaves the room. Prove that the total number of sweets received by the boys does not depend on the order in which the children reach the pile.
Maxim Didin

1

Easy ToT number theory

n{}

is it possible that a product of

n{}

consecutive positive integers is equal to a sum of

n{}

consecutive (not necessarily the same) positive integers?
Boris Frenkin

1

Easy ToT geo

ABCD

be a parallelogram and let

P{}

be a point inside it such that

\angle PDA= \angle PBA

\omega_1

be the excircle of

PAB

opposite to the vertex

A{}

\omega_2

be the incircle of the triangle

PCD

. Prove that one of the common tangents of

\omega_1

\omega_2

AD

1

Rook moves on 10x10 board

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.
Alexandr Gribalko

1

Do you prefer jam or treacle?

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?
Alexandr Gribalko

1

Alice and Bob play a game

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?
Alexandr Gribalko

1

Sum of numbers on board is bounded

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

.
Mikhail Lukin

1

Silk Road 2021 P2

For every positive integer

m

prove the inquality

|\{\sqrt{m}\} - \frac{1}{2}| \geq \frac{1}{8(\sqrt m+1)}

(The integer part

[x]

x

is the largest integer not exceeding

x

. The fractional part of the number

x

\{x\}

[x]+\{x\}=x

.)
A. Golovanov

1

center of mass of 10 points in the plane

Does there exist a set

S

100

points in a plane such that the center of mass of any

10

S

is also a point in

S

1

NT about non-squarefree integers

Given are positive integers

n>20

k>1

k^2

n

. Prove that there exist positive integers

a, b, c

n=ab+bc+ca

1

Grid game in ARO

A teacher and her 30 students play a game on an infinite cell grid. The teacher starts first, then each of the 30 students makes a move, then the teacher and so on. On one move the person can color one unit segment on the grid. A segment cannot be colored twice. The teacher wins if, after the move of one of the 31 players, there is a

1\times 2

2\times 1

rectangle , such that each segment from it's border is colored, but the segment between the two adjacent squares isn't colored. Prove that the teacher can win.

1

parallelogram given, tangency wanted

BC

of the parallelogram

ABCD

E

F

E

B

F

) and the diagonals

AC, BD

O

. If it's known that

AE, DF

are tangent to the circumcircle of

\triangle AOD

, prove that they're tangent to the circumcircle of

\triangle EOF

1

Unordinary functional equation

An infinite table whose rows and columns are numbered with positive integers, is given. For a sequence of functions

f_1(x), f_2(x), \ldots

let us place the number

f_i(j)

(i,j)

of the table (for all

i, j\in \mathbb{N}

f_1(x), f_2(x), \ldots

is said to be {\it nice}, if all the numbers in the table are positive integers, and each positive integer appears exactly once. Determine if there exists a nice sequence of functions

f_1(x), f_2(x), \ldots

, such that each

f_i(x)

is a polynomial of degree 101 with integer coefficients and its leading coefficient equals to 1.

1

4 tokens in the plane

4 tokens are placed in the plane. If the tokens are now at the vertices of a convex quadrilateral

P

, then the following move could be performed: choose one of the tokens and shift it in the direction perpendicular to the diagonal of

P

not containing this token; while shifting tokens it is prohibited to get three collinear tokens.
Suppose that initially tokens were at the vertices of a rectangle

\Pi

, and after a number of moves tokens were at the vertices of one another rectangle

\Pi'

\Pi'

\Pi

but not equal to

\Pi

\Pi

1

A game on coloring in three different colors

A row of 2021 balls is given. Pasha and Vova play a game, taking turns to perform moves; Pasha begins. On each turn a boy should paint a non-painted ball in one of the three available colors: red, yellow, or green (initially all balls are non-painted). When all the balls are colored, Pasha wins, if there are three consecutive balls of different colors; otherwise Vova wins. Who has a winning strategy?

1

Any number is divisible by the sum of the other numbers

n>2

non-zero integers such that each one of them is divisible by the sum of the other

n-1

numbers. Prove that the sum of all the given numbers is zero.