Kvant 2019

Part of Kvant Problems

Subcontests

(44)

1

Complicated operation

We have 2019 boxes. Initially, they are all empty. At one operation, we can add exactly 100 stones to some 100 boxes and exactly one stone in each of several other (perhaps none) boxes. What is the smallest possible number of moves after which all boxes will have the same (positive) number of stones.
Proposed by P. Kozhevnikov

1

GCD has no more than 14 digits

a

b

be 2019-digit numbers. Exactly 12 digits of

a

are non-zero: the five leftmost and seven rightmost, and exactly 14 digits of

b

are non-zero: the five leftmost and nine rightmost. Prove that the largest common divisor of

a

b

has no more than 14 digits.
Proposed by L. Samoilov

1

Numbers with sum of proper divisors bigger then them

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

N

consecutive redundant non-negative integers.
[I]Proposed by V. Bragin[/I]

1

Grasshopper jumps and flies on a board

A grasshopper is in the left above corner of a

10\times 10

square. At each step he can jump a square below or a square to the right. Also, he can also fly from a cell of the bottom row to a cell of the above row, and from a cell of the rightmost column to a cell of the leftmost column. Prove that the grasshopper has to do at leat

9

flies in order to visit each cell of the square at least once.
[I]Proposed by N. Vlasova[/I]

1

Sum of n-digit numbers with decreasing digits

For each non-negative integer

n

find the sum of all

n

-digit numbers with the digits in a decreasing sequence.
[I]Proposed by P. Kozhevnikov[/I]

1

Parallelism is Sangaku configuration

\omega_1

\omega_2

O_1

O_2

are externally tangent at the point

T

\omega_3

O_3

is tangent to the line

AB

(the external common tangent of

\omega_1

\omega_2

D

and externally tangent to

\omega_1

\omega_2

TD

intersects again at

\omega_1

O_1 C \parallel AB

.
[I]Proposed by V. Rastorguev[/I]

1

Nice identities with sums of powers

a,b,c

be real numbers

a + b +c = 0

. Show that
[*]

\displaystyle \frac{a^2 + b^2 + c^2}{2} \cdot \frac{a^3 + b^3 + c^3}{3} = \frac{a^5 + b^5 + c^5}{5}

\displaystyle \frac{a^2 + b^2 + c^2}{2} \cdot \frac{a^5 + b^5 + c^5}{5} = \frac{a^7 + b^7 + c^7}{7}

.
[I]Folklore[/I]

1

Nice collinearity in regular pentagon

DE

and on the diagonal

BE

of the regular pentagon

ABCDE

we consider the squares

DEFG

BEHI

.
[*] Prove that

A,I,

G

are collinear. [*] Prove that on this line lies also the centre

O

BDJK

1

Sum of odd powers is 0

a_1,...,a_n

n

real numbers. If for each odd positive integer

k\leqslant n

a_1^k+a_2^k+\ldots+a_n^k=0

, then for each odd positive integer

k

a_1^k+a_2^k+\ldots+a_n^k=0

.
Proposed by M. Didin

1

Perpendiculars from isogonal conjugates on angle-bisector

Inside the acute-angled triangle

ABC

P

Q

two isogonal conjugate points. The perpendicular lines on the interior angle-bisector of

\angle BAC

passing through

P

Q

intersect the segments

AC

AB

B_p\in AC

B_q\in AC

C_p\in AB

C_q\in AB

, respectively. Let

W

be the midpoint of the arc

BAC

(ABC)

WP

intersects the circle

(ABC)

P_1

WQ

intersects the circle

(ABC)

Q_1

. Prove that the points

P_1

Q_1

B_p

B_q

C_p

C_q

lie on a circle.
Proposed by P. Bibikov

1

Border between horizontal and vertical dominoes

8\times 8

board is divided in dominoes (rectangles with dimensions

1 \times 2

2 \times 1

).
[*] 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.
Proposed by B. Frenkin, A. Zaslavsky, E. Arzhantseva

1

Polynomial with coefficients -1 or 1

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

\left|P(t)-2019\right| \leqslant 1.

Proposed by N. Safaei (Iran)

1

x^n +y^n modulo n^2

n>1

be a positive integer. Show that the number of residues modulo

n^2

of the elements of the set

\{ x^n + y^n : x,y \in \mathbb{N} \}

\frac{n(n+1)}{2}

.
[I]Proposed by N. Safaei (Iran)

1

Sequence of binomial coefficients modulo 2^k

k

be a fixed positive integer. Prove that the sequence

\binom{2}{1},\binom{4}{2},\binom{8}{4},\ldots, \binom{2^{n+1}}{2^n},\ldots

is eventually constant modulo

2^k

.
Proposed by V. Rastorguyev

1

Cute trapezoid geometry

ABCD

be a trapezoid with

AD \parallel BC

AD < BC

E

be a point on the side

AB

F

be point on the side

CD

(AEF)

intersects the segment

AD

A_1

(CEF)

intersects these segment

BC

C_1

. Prove that the lines

A_1 C_1

BD

EF

are concurrent.
Proposed by A. Kuznetsov

1

The dog doesn't want to eat so many flies

A dog has infinitely many pieces of meat, but on each piece of meat there is a fly. At each move, the dog does the following:
[*] He eats a piece of meat together with all flies lying on it; [*] He moves a fly from a piece of meat to another.
The dog doesn't want to eat more than one milion flies. Prove that he cannot ensure that each piece of meat is eaten at some point.
Proposed by I. Mitrofanov

1

Sum from selected rows and columns in over 1000

In each cell of a

2019\times 2019

board is written the number

1

-1

. Prove that for some positive integer

k

it is possible to select

k

k

columns so that the absolute value of the sum of the

k^2

numbers in the cells at the intersection of the selected rows and columns is more than

1000

1

Easy geo with tangent circles

Two externally tangent circles

\Omega_1

\Omega_2

are internally tangent to the circle

\Omega

A

B

, respectively. If the line

AB

\Omega_1

D

C\in\Omega_1\cap\Omega_2

\angle BCD=90^\circ

.
Proposed by V. Rastorguev

1

Polygon partitioned into triangles by multicoloured diagonals

The vertices of a convex polygon with

n\geqslant 4

sides are coloured with black and white. A diagonal is called multicoloured if its vertices have different colours. A colouring of the vertices is good if the polygon can be partitioned into triangles by using only multicoloured diagonals which do not intersect in the interior of the polygon. Find the number of good colourings.
Proposed by S. Berlov

1

Polynomial with n roots in (0,1)

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

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.

Proposed by N. Safaei (Iran)

1

Algebra and NT

a_1,a_2, \cdots

be a sequence of integers that satisfies:

a_1=1

a_{n+1}=a_n+a_{\lfloor \sqrt{n} \rfloor} , \forall n\geq 1

. Prove that for all positive

k

m \geq 1

k \mid a_m

1

Ants love to move along edges

Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face

F

of the polyhedron are written the number of edges of

F

belonging to the route of the first ant and the number of edges of

F

belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers?
Proposed by Nikolai Beluhov

1

all possible broken lines constructed on grid plane

On the grid plane all possible broken lines with the following properties are constructed: each of them starts at the point

(0, 0)

, has all its vertices at integer points, each linear segment goes either up or to the right along the grid lines. For each such broken line consider the corresponding worm, the subset of the plane consisting of all the cells that share at least one point with the broken line. Prove that the number of worms that can be divided into dominoes (rectangles 2\times 1 and 1\times 2) in exactly

n > 2

different ways, is equal to the number of positive integers that are less than n and relatively prime to

n

.
(Ilke Chanakchi, Ralf Schiffler)

1

fixed point for angle bisector of gray and black sides, 2 equal wooden disks

Two not necessarily equal non-intersecting wooden disks, one gray and one black, are glued to a plane. An infinite angle with one gray side and one black side can be moved along the plane so that the disks remain outside the angle, while the colored sides of the angle are tangent to the disks of the same color (the tangency points are not the vertices). Prove that it is possible to draw a ray in the angle, starting from the vertex of the angle and such that no matter how the angle is positioned, the ray passes through some fixed point of the plane.
(Egor Bakaev, Ilya Bogdanov, Pavel Kozhevnikov, Vladimir Rastorguev) (Junior version [url=https://artofproblemsolving.com/community/c6h2094701p15140671]here) There was a mistake in the text of the problem 3, we publish here the correct version. The solutions were estimated according to the text published originally.

1

2019 point grasshoppers sit on a line, jumping around

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)

1

tangential and cyclic wanted, area of ABCD equals to MA x MC +MB x MD

M

inside a convex quadrilateral

ABCD

is equidistant from the lines

AB

CD

and is equidistant from the lines

BC

AD

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)

1

Real IMO Shortlist 2019 G6 orthocenter wanted

A circle centred at

I

is tangent to the sides

BC, CA

AB

of an acute-angled triangle

ABC

A_1, B_1

C_1

, respectively. Let

K

L

be the incenters of the quadrilaterals

AB_1IC_1

BA_1IC_1

, respectively. Let

CH

be an altitude of triangle

ABC

. Let the internal angle bisectors of angles

AHC

BHC

A_1C_1

B_1C_1

P

Q

, respectively. Prove that

Q

is the orthocenter of the triangle

KLP

.
Kolmogorov Cup 2018, Major League, Day 3, Problem 1; A. Zaslavsky

1

Infinite sequence

Consider the following sequence of positive real numbers

\dots<a_{-2}<a_{-1}<a_0<a_1<a_2<\dots

infinite in both directions. For each positive integer

k

b_k

be the least integer such that the ratio between the sum of

k

consecutive terms and the greatest of these

k

terms is less than or equal to

b_k

(This fact occurs for any sequence of

k

consecutive numbers). Prove that the sequence

b_1,b_2,b_3,...

coincides with the sequence

1,2,3,...

or is eventually constant.

1

Unexpected answer

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?

1

Not so easy

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.

1

Algebra or NT

1

is written on the blackboard. We are allowed to perform the following operations:to change the number

x

3x+1

[\frac{x}{2}]

. Prove that we can get all positive integers using this operations.

1

2019 All Russian MO Grade 11 P3

n

coins of different weights and

n

n>2

. On each turn one can choose one balance, put one coin on the right pan and one on the left pan, and then delete these coins out of the balance. It's known that one balance is wrong (but it's not known ehich exactly), and it shows an arbitrary result on every turn. What is the smallest number of turns required to find the heaviest coin?
Thanks to the user Vlados021 for translating the problem.

1

An interesting geometry

ABC

be an acute-angled triangle with

AC<BC.

A circle passes through

A

B

and crosses the segments

AC

BC

A_1

B_1

respectively. The circumcircles of

A_1B_1C

ABC

meet each other at points

P

C.

AB_1

A_1B

S.

Q

R

be the reflections of

S

CA

CB

respectively. Prove that the points

P,

Q,

R,

C

1

A game of cutting

Pasha and Vova play the following game, making moves in turn; Pasha moves first. Initially, they have a large piece of plasticine. By a move, Pasha cuts one of the existing pieces into three(of arbitrary sizes), and Vova merges two existing pieces into one. Pasha wins if at some point there appear to be

100

pieces of equal weights. Can Vova prevent Pasha's win?

1

Functional equation from R^2 to R

A

in the plane is assigned a real number

f(A).

It is known that

f(M)=f(A)+f(B)+f(C),

M

is the centroid of

\triangle ABC.

f(A)=0

A.

1

Simple Inequality from Kvant

a,b,c>0

be real numbers. Prove that

\frac{a+b}{\sqrt{b+c}}+\frac{b+c}{\sqrt{c+a}}+\frac{c+a}{\sqrt{a+b}}\geq \sqrt{2a}+ \sqrt{2b}+ \sqrt{2c}

Б. Кайрат (Казахстан), А. Храбров

1

Three trapezoids with inscribed circle

BC

CA

AB

ABC

K

L

M

are chosen, respectively, and a point

P

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.

1

Weighing problem

Dima has 100 rocks with pairwise distinct weights. He also has a strange pan scales: one should put exactly 10 rocks on each side. Call a pair of rocks {\it clear} if Dima can find out which of these two rocks is heavier. Find the least possible number of clear pairs.

1

Equal sums of powers of 2

15 boxes are given. They all are initially empty. By one move it is allowed to choose some boxes and to put in them numbers of apricots which are pairwise distinct powers of 2. Find the least positive integer

k

such that it is possible to have equal numbers of apricots in all the boxes after

k

1

On existence of five consecutive positive integers with perfect square LCM

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

1

CMO 2019, senior, P1

Pasha placed numbers from

1

100

in the cells of the square

10

10

, each number exactly once. After that, Dima considered all sorts of squares, with the sides going along the grid lines, consisting of more than one cell, and painted in green the largest number in each such square (one number could be colored many times). Is it possible that all two-digit numbers are painted green?
Bragin Vladimir

1

RMM 2019 Problem 1

Amy and Bob play the game. At the beginning, Amy writes down a positive integer on the board. Then the players take moves in turn, Bob moves first. On any move of his, Bob replaces the number

n

on the blackboard with a number of the form

n-a^2

a

is a positive integer. On any move of hers, Amy replaces the number

n

on the blackboard with a number of the form

n^k

k

is a positive integer. Bob wins if the number on the board becomes zero. Can Amy prevent Bob’s win?
Maxim Didin, Russia

1

RMM 2019 Problem 3

Given any positive real number

\varepsilon

, prove that, for all but finitely many positive integers

v

v

vertices with at least

(1+\varepsilon)v

edges has two distinct simple cycles of equal lengths. (Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.)
Fedor Petrov, Russia

1

Isotomic points on line joining incenters

N,K,L

be points on the sides

\overline{AB}, \overline{BC}, \overline{CA}

respectively. Suppose

AL=BK

\overline{CN}

is the internal bisector of angle

ACB

P

be the intersection of lines

\overline{AK}

\overline{BL}

I,J

be the incenters of triangles

APL

BPK

respectively. Let

Q

be the intersection of lines

\overline{IJ}

\overline{CN}

IP=JQ