Kvant 2022

Part of Kvant Problems

Subcontests

(45)

1

Largest tax the mayor can collect

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?
Proposed by I. Bogdanov

1

Collinear points and incircle

T_a, T_b

T_c

be the tangent points of the incircle

\Omega

of the triangle

ABC

BC, CA

AB{}

respectively. Let

X, Y

Z{}

be points on the circle

\Omega

A{}

lies on the ray

YX

B{}

lies on the ray

ZY

C{}

lies on the ray

XZ

P{}

be the intersection point of the segments

ZX

T_bT_c

, and similarly

Q=XY \cap T_cT_a

R=YZ\cap T_aT_b

. Prove that the points

A, B

C{}

lie on the lines

RP, PQ

QR{}

, respectively.
Proposed by L. Shatunov (11th grade student)

1

Labeling the vertices of an n-gon

We have a regular

n{}

n\geqslant 4

. We consider the arrangements of

n{}

numbers on its vertices, each of which is equal to 1 or 2. For each such arrangement

K{}

, we find the number of odd sums among all sums of numbers in several consecutive vertices. This number is denoted by

\alpha(K)

.
[*]Find the largest possible value of

\alpha(K)

. [*]Find the number of arrangements for which

\alpha(K)

takes this largest possible value.
Proposed by P. Kozhevnikov

1

Volleyball tournament

At a two-round volleyball tournament participated 99 teams. Each played a match at home and a match away. Each team won exactly half of their home matches and exactly half of their away matches. Prove that one of the teams beat another team twice.
Proposed by M. Antipov

1

Candies of various types

n{}

candies of several types, where

n>145

. It is known that for any group of at least 145 candies, there is a type of candy which appears exactly 10 times. Find the largest possible value of

n{}

.
Proposed by A. Antropov

1

Angles of triangles are integers

N{}

points marked on the plane. Any three of them form a triangle, the values of the angles of which in are expressed in natural numbers (in degrees). What is the maximum

N{}

for which this is possible?
Proposed by E. Bakaev

1

Poncelet Porism configuration

\Omega

ABCDEF

is inscribed. It is known that the point

D{}

divides the arc

BC

in half, and the triangles

ABC

DEF

have a common inscribed circle. The line

BC

intersects segments

DF

DE

X

Y

EF

intersects segments

AB

AC

Z

T

respectively. Prove that the points

X, Y, T

Z

lie on the same circle.
Proposed by D. Brodsky

1

Sum of digits of factorial

Prove that there exists a natural number

b

such that for any natural

n>b

the sum of the digits of

n!

is not less than

10^{100}

.
Proposed by D. Khramtsov

1

Interesting numbers

Call a natural number

n{}

interesting if any natural number not exceeding

n{}

can be represented as the sum of several (possibly one) pairwise distinct positive divisors of

n{}

.
[*]Find the largest three-digit interesting number. [*]Prove that there are arbitrarily large interesting numbers other than the powers of two.
Proposed by N. Agakhanov

1

Conditions for collinearity and cyclicity

\Omega

\ell

intersect at two different points

A{}

B{}

. For different and non-points. Let

X

T

\ell

Y

Z

\Omega

, all of them different from

A{}

B{}

. Prove the following statements:
[*]The points

X,Y

Z

lie on the same line if and only if

\frac{\overline{AX}}{\overline{BX}}=\pm\frac{AY}{BY}\cdot\frac{AZ}{BZ}.

X,Y,Z

T

lie on the same circle if and only if

\frac{\overline{AX}}{\overline{BX}}\cdot\frac{\overline{AT}}{\overline{BT}}=\pm\frac{AY}{BY}\cdot\frac{AZ}{BZ}.

Note: In both points, the sign

+

is selected in the right parts of the equalities if the points

Y{}

Z{}

lie on the same arc

AB

\Omega

-

Y{}

Z{}

lie on different arcs

AB

\overline{AX}/\overline{BX}

, we indicate the ratio of the lengths of

AX

BX

, taken with the sign

+

-

depending on whether the

AX

BX

vectors are co-directed or oppositely directed.
Proposed by M. Skopenkov

1

Even number of prime divisors

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

j{}

?
From the folklore

1

Two drivers on a circular highway

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.
Proposed by I. Bogdanov

1

Trigonometric inequality

ABC

be a triangle, with

\angle A=\alpha,\angle B=\beta

\angle C=\gamma

\sum_{\text{cyc}}\tan \frac{\alpha}{2}\tan\frac{\beta}{2}\cot\frac{\gamma}{2}\geqslant\sqrt{3}.

Proposed by R. Regimov (Azerbaijan)

1

Iterated points

Three pairwise externally tangent circles

\omega_1,\omega_2

\omega_3

K_{12}

be the point of tangency between

\omega_1

\omega_2

K_{23}

K_{31}

similarly. Consider the point

A_1

\omega_1

A_2

be the second intersection of the line

A_1K_{12}

\omega_2

A_2K_{23}

then intersects

\omega_3

the second time at

A_3

, and then line

A_3K_{31}

\omega_1

A_4

and so on.
[*]Prove that after six steps, the process will loop; that is,

A_7=A_1

. [*]Prove that the lines

A_1A_2

A_4A_5

are perpendicular. [*]Prove that the triples of lines

A_1A_2,A_3A_4

A_5A_6

A_2A_3,A_4A_5

A_6A_1

intersect at two diametrically opposite points on the circle

(K_{12}K_{23}K_{31})

.
Proposed by E. Morozov

1

Progressive sets of cells.

We are given an

(n^2-1)\times(n^2-1)

checkered board. A set of

n{}

cells is called progressive if the centers of the cells lie on a straight line and form

n-1

equal intervals. Find the number of progressive sets.
Proposed by P. Kozhevnikov

1

Nice collinearity

In an acute triangle

ABC

AD, BE

CF

intersecting at

H{}

O{}

be the circumcenter of the triangle

ABC

. The tangents to the circle

(ABC)

B{}

C{}

T{}

K{}

L{}

be symmetric to

O{}

with respect to

AB

AC

respectively. The circles

(DFK)

(DEL)

intersect at a point

P{}

D{}

P, D

T{}

lie on the same line.
Proposed by Don Luu (Vietnam)

1

Product divisible with factorial

Find all pairs of natural numbers

(k, m)

such that for any natural

n{}

(n+m)(n+2m)\cdots(n+km)

is divisible by

k!{}

.
Proposed by P. Kozhevnikov

1

Rook with limited movement

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

?
From the folklore

1

Divisibility and polynomials 2

f{}

g{}

be polynomials with integers coefficients. The leading coefficient of

g{}

is equal to 1. It is known that for infinitely many natural numbers

n{}

f(n)

is divisible by

g(n)

f(n)

is divisible by

g(n)

for all positive integers

n{}

g(n)\neq 0

.
From the folklore

1

Divisibility and polynomials

n{}

be a natural number and

f{}

be polynomial with integer coefficients. It is known that for any integer

m{}

there is an integer

k{}

f(k)-m

is divisible by

n{}

. Prove that there exists a polynomial

g{}

with integer coefficients such that

f(g(m))-m

is divisible by

n{}

for any integer

m{}

.
From the folklore

1

Area inequality

\Omega

be the circumcircle of the triangle

ABC

M_a,M_b

M_c

are the midpoints of the sides

BC, CA

AB{}

, respectively. Let

A_l, B_l

C_l

be the intersection points of

\Omega

M_cM_b, M_aM_c

M_bM_a

respectively. Similarly, let

A_r, B_r

C_r

be the intersection points of

\Omega

M_bM_c, M_cM_a

M_aM_b

respectively. Prove that the mean of the areas of the triangles

A_lB_lC_l

A_rB_rC_r

is not less than the area of the triangle

ABC

.
Proposed by L. Shatunov and T. Kazantseva

1

Unique set of residues

For an odd positive integer

n>1

S_n

to be the set of the residues of the powers of two, modulo

n{}

. Do there exist distinct

n{}

m{}

whose corresponding sets

S_n

S_m

coincide?
Proposed by D. Kuznetsov

1

Exponential equality

Determine all positive integers

n{}

m{}

m^n=n^{3m}

.
Proposed by I. Dorofeev

1

Broken line inside 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.
Proposed by L. Emelyanov

1

Areas and circumcenters

A convex quadrilateral

ABCD

O_a

be the circumcenter of the triangle

DBC

O_b,O_c

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

BO_cDO_a

.
Proposed by V. Dubrovsky

1

Iterated fractions

a_1=1

a_{n+1}=2/(2+a_n)

n\geqslant 1

b_1=1

b_{n+1}=3/(3+b_n)

n\geqslant 1

. Which is greater between

a_{2022}

b_{2022}

?
Proposed by P. Kozhevnikov

1

Two 2n-gons and perpendicular bisectors

Two equally oriented regular

2n

A_1A_2\ldots A_{2n}

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

\ell_{i+1}

intersect at the point

K_i

(hereafter we reduce indices modulo

2n

m_i

K_iK_{i+n}

n{}

m_i

intersect at one point and at that the angles between the lines

m_i

m_{i+1}

are equal.
Proposed by Chan Quang Hung (Vietnam)

1

Sum of digits in arithmetic progression

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

1

Stop faking banknotes

It is known that among several banknotes of pairwise distinct face values (which are positive integers) there are exactly

N{}

fakes. In a single test, a detector determines the sum of the face values of all real banknotes in an arbitrary set we have selected. Prove that by using the detector

N{}

times, all fake banknotes can be identified, if a)

N=2

N=3

.
Proposed by S. Tokarev

1

Cutting triangles

Consider an acute non-isosceles triangle. In a single step it is allowed to cut any one of the available triangles into two triangles along its median. Is it possible that after a finite number of cuttings all triangles will be isosceles?
Proposed by E. Bakaev

1

Weird weighted graph

Given is a graph

G

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

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

1

Parity of edges

m\times n

grid is tiled by mosaics

2\times2

1\times3

(horizontal and vertical). Prove that the number of ways to choose a

1\times2

rectangle (horizontal and vertical) such that one of its cells is tiled by

2\times2

mosaic and the other cell is tiled by

1\times3

mosaic [horizontal and vertical] is an even number.

1

2022TTsJA2

Prove that for any convex quadrilateral it is always possible to cut out three smaller quadrilaterals similar to the original one with the scale factor equal to 1/2. (The angles of a smaller quadrilateral are equal to the corresponding original angles and the sides are twice smaller then the corresponding sides of the original quadrilateral.)

1

Tournament of Towns 2022 SA4

A rock travelled through an n x n board, stepping at each turn to the cell neighbouring the previous one by a side, so that each cell was visited once. Bob has put the integer numbers from 1 to n^2 into the cells, corresponding to the order in which the rook has passed them. Let M be the greatest difference of the numbers in neighbouring by side cells. What is the minimal possible value of M?

1

Tournament of Towns 2022 Spring SA6

The king assembled 300 wizards and gave them the following challenge. For this challenge, 25 colors can be used, and they are known to the wizards. Each of the wizards receives a hat of one of those 25 colors. If for each color the number of used hats would be written down then all these number would be different, and the wizards know this. Each wizard sees what hat was given to each other wizard but does not see his own hat. Simultaneously each wizard reports the color of his own hat. Is it possible for the wizards to coordinate their actions beforehand so that at least 150 of them would report correctly?

1

43rd INTERNATIONAL MATHEMATICS TOURNAMENT OF TOWNS

What is the maximal possible number of roots on the interval (0,1) for a polynomial of degree 2022 with integer coefficients and with the leading coefficient equal to 1?

1

Monotonic blocks in a sequence

Given an infinite sequence of numbers

a_1, a_2,...

, in which there are no two equal members. Segment

a_i, a_{i+1}, ..., a_{i+m-1}

of this sequence is called a monotone segment of length

m

a_i < a_{i+1} <...<a_{i+m-1}

a_i > a_{i+1} >... > a_{i+m-1}

. It turned out that for each natural

k

a_k

is contained in some monotonic segment of length

k + 1

. Prove that there exists a natural

N

such that the sequence

a_N , a_{N+1} ,...

1

Incenter-excenter geo

Given is triangle

ABC

I

A

J

\omega_b

centered at point

O_b

passes through point

B

and is tangent to line

CI

I

\omega_c

O_c

passes through point

C

and touches line

BI

I

O_bO_c

IJ

intersect at point

K

. Find the ratio

IK/KJ

1

Strange operation on a board again

Initially, a pair of numbers

(1,1)

is written on the board. If for some

x

y

one of the pairs

(x, y-1)

(x+y, y+1)

is written on the board, then you can add the other one. Similarly for

(x, xy)

(\frac {1} {x}, y)

. Prove that for each pair that appears on the board, its first number will be positive.

1

Drawing segments

Given is a natural number

n>4

n

points marked on the plane, no three of which lie on the same line. Vasily draws one by one all the segments connecting pairs of marked points. At each step, drawing the next segment

S

, Vasily marks it with the smallest natural number, which hasn't appeared on a drawn segment that has a common end with

S

. Find the maximal value of

k

, for which Vasily can act in such a way that he can mark some segment with the number

k

1

Unlucky coloring of graph edges

n > 2022

cities in the country. Some pairs of cities are connected with straight two-ways airlines. Call the set of the cities {\it unlucky}, if it is impossible to color the airlines between them in two colors without monochromatic triangle (i.e. three cities

A

B

C

with the airlines

AB

AC

BC

of the same color).
The set containing all the cities is unlucky. Is there always an unlucky set containing exactly 2022 cities?

1

Pairwise distances are consecutive numbers

Do there exist 100 points on the plane such that the pairwise distances between them are pairwise distinct consecutive integer numbers larger than 2022?

1

Representation in sum of fractions

Prove that infinitely many positive integers can be represented as

(a-1)/b + (b-1)/c + (c-1)/a

a

b

c

are pairwise distinct positive integers greater than 1.

1

Number of teams with non-negative balance of wins

16 NHL teams in the first playoff round divided in pairs and to play series until 4 wins (thus the series could finish with score 4-0, 4-1, 4-2, or 4-3). After that 8 winners of the series play the second playoff round divided into 4 pairs to play series until 4 wins, and so on. After all the final round is over, it happens that

k

teams have non-negative balance of wins (for example, the team that won in the first round with a score of 4-2 and lost in the second with a score of 4-3 fits the condition: it has

4+3=7

2+4=6

losses). Find the least possible

k

1

Pairwise distances of lattice points are consecutive numbers

Do there exist 2021 points with integer coordinates on the plane such that the pairwise distances between them are pairwise distinct consecutive integers?