Kvant 2020

Part of Kvant Problems

Subcontests

(54)

1

Rather suspicious flavor-text

In a country, the time for presidential elections has approached. There are exactly 20 million voters in the country, of which only one percent supports the current president, Miraflores. Naturally, he wants to be elected again, but on the other hand, he wants the elections to seem democratic.
Miraflores established the following voting process: all the voters are divided into several equal groups, then each of these groups is again divided into a number of equal groups, and so on. In the smallest groups, a representative is chosen. Then, the chosen electors choose representatives in the second-smallest groups, to vote in an even larger group, and so on. Finally, the representatives of the largest groups choose the president.
Miraflores divides voters into groups as he wants and instructs his supporters how to vote. Will he be able to organize the elections in such a way that he will be elected president? (If the votes are equal, the opposition wins.)
From the 32nd Moscow Mathematical Olympiad

1

Writing numbers on a segment

Two digits one are written at the ends of a segment. In the middle, their sum is written, the number 2. Then, in the middle between each two neighboring numbers written, their sum is written again, and so on, 1973 times. How many times will the number 1973 be written?
Proposed by G. Halperin

1

Series of sum of cubes diverges

[*]The sum of several numbers is equal to one. Can the sum of their cubes be greater than one? [*]The same question as before, for numbers not exceeding one. [*]Can it happen that the series

a_1+a_2+\cdots

converges, but the series

a_1^3+a_2^3+\cdots

1

Equal values of continuous function

Determine the positive numbers

a{}

for which the following statement true: for any function

f:[0,1]\to\mathbb{R}

which is continuous at each point of this interval and for which

f(0)=f(1)=0

f(x+a)-f(x)=0

has at least one solution.
Proposed by I. Yaglom

1

Fixed distance from cyclists

Two cyclists ride on two intersecting circles. Each of them rides on his own circle at a constant speed. Having left at the same time from one of the points of intersection of the circles and having made one lap each, the cyclists meet again at this point. Prove that there exists a fixed point in the plane, the distances from which to cyclists are the same all the time, regardless of the directions they travel in.
Proposed by N. Vasiliev and I. Sharygin

1

Uniform colorings of a polygon

k{}

vertices of a regular

n{}

-gon are colored red. We will call a coloring uniform 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.
Proposed by M. Kontsevich

1

Polyline inscribed in an arc

AMB

is inscribed in the arc

AB{}

, consisting of two segments, and

AM>MB

K

be the midpoint of the arc

AB{}

. Prove that the foot

H{}

of the perpendicular from

K

AM

divides the polyline in two equal segments:

AH=HM+MB.

Discovered by Archimedes

1

Involutions and bijections

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.
Proposed by N. Konstantinov and A. Shnirelman

1

Beautiful Combinatorics from St. Petersburg 1993

An ant crawls clockwise along the contour of each face of a convex polyhedron. It is known that their speeds at any given time are not less than 1 mm/h. Prove that sooner or later two ants will collide.
Proposed by A. Klyachko

1

Polyline divides triangle into equal figures

In an acute triangle

ABC

O{}

is the circumcenter,

H_1

is the foot of the perpendicular from

A{}

BC

M_H

N_H

are the projections of

H_1

AC

AB{}

, respectively. Prove that the polyline

M_HON_H

divides the triangle

ABC

in two figures of equal area.
Proposed by I. A. Kushner

1

Distances between red dots

There are 100 blue lines drawn on the plane, among which there are no parallel lines and no three of which pass through one point. The intersection points of the blue lines are marked in red. Could it happen that the distance between any two red dots lying on the same blue line is equal to an integer?
From the folklore

1

Integers that cannot be represented in a certain manner

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

n{}

k{}

are non-negative integers?
Proposed by F. Petrov

1

Polygon with colorful isosceles triangles

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.
From foreign Olympiads

1

Linear combinations of sin and cos

It is known that for some

x{}

y{}

\sin x+ \cos y

\sin y + \cos x

are positive rational numbers. Prove that there exist natural numbers

m{}

n{}

m\sin x+n\cos x

is a natural number.
Proposed by N. Agakhanov

1

Covering chessboard with crosses and dominoes

Kolya and Dima play a game on an

8\times 8

board, making moves in turn. During his turn, Kolya must put one cross in any empty cell (i.e., in a cell in which a cross has not yet been drawn and which has not yet been covered with a domino). Dima must cover two adjacent cells with a domino (which are not yet covered with other dominoes), in which there are an even number of crosses in total (0 or 2). The one who can't make a move loses. Which of does the player have a winning strategy, if
[*]Dima makes the first move? [*]Kolya makes the first move?
Proposed by M. Didin

1

Geometrical inequality with circumscribed quadrilateral

\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

AD

.
Proposed by O. Yuzhakov

1

Nice and easy NT

p{}

be a prime number greater than 3. Prove that there exists a natural number

y{}

p/2

and such that the number

py + 1

cannot be represented as a product of two integers, each of which is greater than

y{}

.
Proposed by M. Antipov

1

Triangular polygons

For a given natural number

k{}

, a convex polygon is called

k{}

-triangular if it is the intersection of some

k{}

triangles.
[*]What is the largest

n{}

for which there exist a

k{}

n{}

-gon? [*]What is the largest

n{}

for which any convex

n{}

k{}

-triangular?
Proposed by P. Kozhevnikov

1

Colorful paths on a board

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 colorful 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?
Proposed by N. Belukhov

1

Polygon remains non-rigid

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?
Proposed by A. Zaslavsky
[img width="40"]https://i.ibb.co/dgqSvLQ/Screenshot-2023-03-09-231327.png

1

Set with a divisibility criterion

n

be a natural number. The set

A{}

of natural numbers has the following property: for any natural number

m\leqslant n

A{}

there is a number divisible by

m{}

. What is the smallest value that the sum of all the elements of the set

A{}

can take?
Proposed by A. Kuznetsov

1

Geometry with three circles

\omega_1,\omega_2

\omega_3

pass through one point

D{}

A{}

be the intersection of

\omega_1

\omega_3

E{}

be the intersections of

\omega_3

\omega_2

F{}

be the intersection of

\omega_2

\omega_1

. It is known that

\omega_3

passes through the center

B{}

\omega_2

EF

\omega_1

a second time at the point

G{}

\angle GAB=90^\circ

.
Proposed by K. Knop

1

Permuting asterisks under main diagonal

n\times n

table, it is allowed to rearrange rows, as well as rearrange columns. Asterisks are placed in some

k{}

cells of the table. What maximum

k{}

for which it is always possible to ensure that all the asterisks are on the same side of the main diagonal (and that there are no asterisks on the main diagonal itself)?
Proposed by P. Kozhevnikov

1

The angle CML is right

In the triangle

ABC

, the inscribed circle touches the sides

CA{}

AB{}

B_1{}

C_1{}

, respectively. An arbitrary point

D{}

is selected on the side

AB{}

L{}

is the center of the inscribed circle of the triangle

BCD

. The bisector of the angle

ACD

intersects the line

B_1C_1

M{}

\angle CML=90^\circ

.
Proposed by Chan Quang Heung (Vietnam)

1

Sum of powers of near-factorials

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

1

Monochromatic triangle of area one

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

1

Where is the largest segment

Consider a triangle

ABC

AB<BC<CA

. The excircles touch the sides

BC, CA,

AB

A_1, B_1

C_1

respectively. A circle is drawn through the points

A_1, B_1

C_1

which intersects the sides

BC, CA

AB

for the second time at the points

A_2, B_2

C_2

respectively. On which side of the triangle can lie the largest of the segments

A_1A_2, B_1B_2

C_1C_2

?
Proposed by I. Weinstein

1

Lattice triangles with certain properties

a\leqslant b\leqslant c

be non-negative integers. A triangle on a checkered plane with vertices in the nodes of the grid is called an

(a,b,c)

-triangle if there are exactly

a{}

nodes on one side of it (not counting vertices), exactly

b{}

nodes on the second side, and exactly

c{}

nodes on the third side.
[*]Does there exist a

(9,10,11)

-triangle? [*]Find all triples of non-negative integers

a\leqslant b\leqslant c

for which there exists an

(a,b,c)

-triangle. [*]For each such triple, find the minimum possible area of the

(a,b,c)

-triangle.
Proposed by P. Kozhevnikov

1

Satellites cover the entirety of the planet

A satellite is considered accessible from the point

A{}

of the planet's surface if it is located relative to the tangent plane drawn at point

A{}

, strictly on the other side than the planet. What is the smallest number of satellites that need to be launched over a spherical planet so that at some point the signals of at least two satellites are available from each point on the planet's surface?
Proposed by S. Volchenkov

1

Variant of floor function

For a given number

\alpha{}

f_\alpha

be a function defined as

f_\alpha(x)=\left\lfloor\alpha x+\frac{1}{2}\right\rfloor.

\alpha>1

\beta=1/\alpha

. Prove that for any natural

n{}

f_\beta(f_\alpha(n))=n

holds.
Proposed by I. Dorofeev

1

Checkered figure must have a hole

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. Prove that there is a hole in the figure.
Proposed by Y. Markelov and A. Sairanov

1

Football tournament

In a one-round football tournament, three points were awarded for a victory. All the teams scored different numbers of points. If not three, but two points were given for a victory, then all teams would also have a different number of points, but each team's place would be different. What is the smallest number of teams for which this is possible?
Proposed by A. Zaslavsky

1

Rhombus geometry

E, F, G

H{}

are located on the sides

DA, AB, BC

CD

ABCD

respectively, so that the segments

EF

GH

touch the circle inscribed in the rhombus. Prove that

FG\parallel HE

.
Proposed by V. Eisenstadt

1

Another infinite hotel

An infinite number of participants gathered for the Olympiad, who were registered under the numbers

1, 2,\ldots

. It turns out that for every

n = 1, 2,\ldots

a participant with number

n{}

n{}

friends among the remaining participants (note: friendship is mutual). There is a hotel with an infinite number of double rooms. Prove that the participants can be accommodated in double rooms so that there is a couple of friends in each room.
Proposed by V. Bragin, P. Kozhevnikov

1

Products of terms of progression

An infinite arithmetic progression is given. The products of the pairs of its members are considered. Prove that two of these numbers differ by no more than 1.
Proposed by A. Kuznetsov

1

Very hard weighting problem

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.
Proposed by A. Gribalko and O. Manzhina

1

Iterated polygons and areas

The figure shows an arbitrary (green) triangle in the center. White squares were built on its sides to the outside. Some of their vertices were connected by segments, white squares were built on them again to the outside, and so on. In the spaces between the squares, triangles and quadrilaterals were formed, which were painted in different colors. Prove that
[*]all colored quadrilaterals are trapezoids; [*]the areas of all polygons of the same color are equal; [*]the ratios of the bases of one-color trapezoids are equal; [*]if

S_0=1

is the area of the original triangle, and

S_i

is the area of the colored polygons at the

i^{\text{th}}

S_1=1

S_2=5

n\geqslant 3

S_n=5S_{n-1}-S_{n-2}

is satisfied.
Proposed by F. Nilov [img width="40"]https://i.ibb.co/n8gt0pV/Screenshot-2023-03-09-174624.png

1

Fractions on board

Alice and Bob play the following game. They write some fractions of the form

1/n

n{}

is positive integer, onto the blackboard. The first move is made by Alice. Alice writes only one fraction in each her turn and Bob writes one fraction in his first turn, two fractions in his second turn, three fractions in his third turn and so on. Bob wants to make the sum of all the fractions on the board to be an integer number after some turn. Can Alice prevent this?
Andrey Arzhantsev

1

Sides of quadrangle cannot form triangles

There is a convex quadrangle

ABCD

such that no three of its sides can form a triangle. Prove that:
[*]one of its angles is not greater than

60^\circ{}

; [*]one of its angles is at least

120^\circ

1

Good wizard VS evil sorcerer

There are two round tables with

n{}

dwarves sitting at each table. Each dwarf has only two friends: his neighbours to the left and to the right. A good wizard wants to seat the dwarves at one round table so that each two neighbours are friends. His magic allows him to make any

2n

pairs of dwarves into pairs of friends (the dwarves in a pair may be from the same or from different tables). However, he knows that an evil sorcerer will break

n{}

of those new friendships. For which

n{}

is the good wizard able to achieve his goal no matter what the evil sorcerer does?
Mikhail Svyatlovskiy

1

Pairs with integer means

Let us say that a pair of distinct positive integers is nice if their arithmetic mean and their geometric mean are both integer. Is it true that for each nice pair there is another nice pair with the same arithmetic mean? (The pairs

(a, b)

(b, a)

are considered to be the same pair.)
Boris Frenkin

1

Two disjoints sets

We divide the set

\{1,2,\cdots,2n\}

into two disjoint sets :

\{a_1,a_2,\cdots,a_n\}

\{b_1,b_2,\cdots,b_n\}

a_1<a_2<\cdots<a_n\text{ and } b_1>b_2>\cdots>b_n.

|a_1-b_1|+\cdots+|a_n-b_n|=n^2.

1

blackboard numbers: a -> a:Ν mod N -> ... ->0 , sum of ... >100N

Gleb picked positive integers

N

a

a < N

). He wrote the number

a

on a blackboard. Then each turn he did the following: he took the last number on the blackboard, divided the number

N

by this last number with remainder and wrote the remainder onto the board. When he wrote the number

0

onto the board, he stopped. Could he pick

N

a

such that the sum of the numbers on the blackboard would become greater than

100N

?
Ivan Mitrofanov

1

3 lines concurrency , 4 circles related, cyclic ABCD related

ABCD

be an inscribed quadrilateral. Let the circles with diameters

AB

CD

intersect at two points

X_1

Y_1

, the circles with diameters

BC

AD

intersect at two points

X_2

Y_2

, the circles with diameters

AC

BD

intersect at two points

X_3

Y_3

. Prove that the lines

X_1Y_1, X_2Y_2

X_3Y_3

are concurrent.
Maxim Didin

1

Henry invited 2N guests to his birthday party, N white and N black hats

2N

guests to his birthday party. He has

N

N

black hats. He wants to place hats on his guests and split his guests into one or several dancing circles so that in each circle there would be at least two people and the colors of hats of any two neighbours would be different. Prove that Henry can do this in exactly

(2N)!

different ways. (All the hats with the same color are identical, all the guests are obviously distinct,

(2N)! = 1 \cdot 2 \cdot . . . \cdot (2N)

.)
Gleb Pogudin

1

2 cross-sections of tetrahedron by 2 different cutting planes are 2 squares,

Is it possible that two cross-sections of a tetrahedron by two different cutting planes are two squares, one with a side of length no greater than

1

and another with a side of length at least

100

?
Mikhail Evdokimov

1

good sequences, when each derivative consists of positive numbers

For an infinite sequence

a_1, a_2,. . .

denote as it's first derivative is the sequence

a'_n= a_{n + 1} - a_n

n = 1, 2,..

k

- th derivative as the first derivative of its

(k-1)

-th derivative (

k = 2, 3,...

). We call a sequence good if it and all its derivatives consist of positive numbers. Prove that if

a_1, a_2,. . .

b_1, b_2,. . .

are good sequences, then sequence

a_1\cdot b_1, a_2 \cdot b_2,..

is also a good one.
R. Salimov

1

Easy Geometry , concyclicity wanted

\triangle ABC

AB\neq{AC}

M

be the midpoint of

AB

K

be the midpoint of the arc

BAC

in the circumcircle of

\triangle ABC

, and let the perpendicular bisector of

AC

meet the bisector of

\angle BAC

P

A, M, K, P

1

Nice integer FE

Find all functions

f : \mathbb{N}\rightarrow{\mathbb{N}}

such that for all positive integers

m

n

f(m)+n-m

is divisible by

f(n)

1

Coin & board game

Peter and Basil play the following game on a horizontal table

1\times{2019}

. Initially Peter chooses

n

positive integers and writes them on a board. After that Basil puts a coin in one of the cells. Then at each move, Peter announces a number s among the numbers written on the board, and Basil needs to shift the coin by

s

cells, if it is possible: either to the left, or to the right, by his decision. In case it is not possible to shift the coin by

s

cells neither to the left, nor to the right, the coin stays in the current cell. Find the least

n

such that Peter can play so that the coin will visit all the cells, regardless of the way Basil plays.

1

Vertices of a regular 100-gon are colored in 10 colors

All vertices of a regular 100-gon are colored in 10 colors. Prove that there exist 4 vertices of the given 100-gon which are the vertices of a rectangle and which are colored in at most 2 colors.

1

Strange NT

For each integer

n \geq 2

F(n)

denote the greatest prime factor of

n

. A strange pair is a pair of distinct primes

p

q

such that there is no integer

n \geq 2

F(n)F(n+1)=pq

.
Prove that there exist infinitely many strange pairs.

1

Right Triangle with Incircle

ABC

be a triangle with a right angle at

C

I

be the incentre of triangle

ABC

D

be the foot of the altitude from

C

AB

\omega

ABC

is tangent to sides

BC

CA

AB

A_1

B_1

C_1

, respectively. Let

E

F

be the reflections of

C

C_1A_1

C_1B_1

, respectively. Let

K

L

be the reflections of

D

C_1A_1

C_1B_1

, respectively.
Prove that the circumcircles of triangles

A_1EI

B_1FI

C_1KL

have a common point.

1

Inequality on integers [Poland 2017, P3]

a_1, a_2, \ldots, a_n

1<a_1<a_2<\ldots < a_n < 2a_1.

m

is the number of distinct prime factors of

a_1a_2\cdots a_n

, then prove that

(a_1a_2\cdots a_n)^{m-1}\geq (n!)^m.