Kvant 2023

Part of Kvant Problems

Subcontests

(47)

1

Combinatorial geometry gem

A convex polygon

\mathcal{P}

with a center of symmetry

O{}

is drawn in the plane. Prove that it is possible to place a rhombus in

\mathcal{P}

whose image following a homothety of factor two centered at

O

\mathcal{P}

.
Proposed by I. Bogdanov, S. Gerdzhikov and N. Nikolov

1

Ilya has his priorities straight

n{}

currencies in a country, numbered from 1 to

n{}.

In each currency, only non-negative integers are possible amounts of money. A person can have only one currency at any time.
A person can exchange all the money he has from currency

i{}

j{}

\alpha_{ij}

which is a positive real number. If he had

d{}

units of currency

i{}

he instead receives

\alpha_{ij}d

units of currency

j{}

while this number is rounded to the nearest integer; a number of the form

t-1/2

t{}

for any integer

t{}.

It is known that

\alpha_{ij}\alpha_{jk}=\alpha_{ik}

\alpha_{ii}=1

i,j,k.

Can there be a person who can get rich indefinitely?
Proposed by I. Bogdanov

1

Cutting numbers out of sequence of digits

Is there an infinite periodic sequence of digits for which the following condition condition is fulfilled: for any natural number

n{}

a natural number divisible by

2^n{}

can be cut from this sequence of digits (as a word)?
Proposed by P. Kozhevnikov

1

Coloring of a board without monochromatic dominoes

50\times 50

checkered square, each cell is colored in one of the 100 given colors so that all colors are used and there does not exist a monochromatic domino. Galia wants to repaint all the cells of one of the colors in a different color (from the given 100 colors) so that a monochromatic domino still won't exist. Is it true that Galia will surely be able to do this
Proposed by G. Sharafutdinova

1

Variable chord tangent to a circle

\omega

lies inside the circle

\Omega

and touches it internally at

T.

XY{}

be a variable chord of the circle

\Omega

\omega.

X'

Y'

the midpoints of the arcs

TY{}

TX{}

which do not contain

X{}

Y{}

respectively. Prove that all possible lines

X'Y'

pass through a fixed point.
Proposed by F. Petrov

1

Vietnamese geometry in Kvant

The incircle of the triangle

ABC

touches the sides

BC, CA

AB{}

D,E

F{}

respectively. Let the circle

\omega

touch the segments

CA{}

AB{}

Q{}

R{}

respectively, and the points

M{}

N{}

are selected on the segments

AB{}

AC{}

respectively, so that the segments

CM{}

BN{}

\omega

. The bisectors of

\angle NBC

\angle MCB

intersect the segments

DE{}

DF{}

K{}

L{}

respectively. Prove that the lines

RK{}

QL{}

\omega

.
Proposed by Tran Quang Hung

1

Polynomial-ish divisibility problem

n{}

be a natural number. The pairwise distinct nonzero integers

a_1,a_2,\ldots,a_n

have the property that the number

(k+a_1)(k+a_2)\cdots(k+a_n)

is divisible by

a_1a_2\cdots a_n

for any integer

k{}.

Find the largest possible value of

a_n.

Proposed by F. Petrov and K. Sukhov

1

Sum of radii of incircle and excircles

It is easy to prove that in a right triangle the sum of the radii of the incircle and three excircles is equal to the perimeter. Prove that the opposite statement is also true.
Proposed by I. Weinstein

1

Master Sudoku

n{}

be a natural number. The playing field for a "Master Sudoku" is composed of the

n(n+1)/2

cells located on or below the main diagonal of an

n\times n

square. A teacher secretly selects

n{}

cells of the playing field and tells his student
[*]the number of selected cells on each row, and [*]that there is one selected cell on each column. The teacher's selected cells form a Master Sudoku if his student can determine them with the given information. How many Master Sudokus are there?
Proposed by T. Amdeberkhan, M. Ruby and F. Petrov

1

And another hard weighting problem

We have 101 coins and a two-pan scale. In one weighing, we can compare the weights of two coins. What is the smallest number of weighings required in order to decide whether there exist 51 coins which all have the same weight?

1

Concurrency geometry

BE{}

CF

be heights in the acute-angled triangle

ABC{}

O{}

be its circumcenter. The points

M{}

N{}

are selected on the side

BC{}

BM=CN.{}

BE{}

intersects the circle

(MBF)

a second time at

P{}

CF{}

intersects the circle

(NCE)

a second time at

Q.{}

Prove that the lines

PF, QE

AO{}

intersect at the same point.
Proposed by Luu Dong

1

Certain integers give all residues modulo k

k\geqslant 2

be a natural number. Prove that the natural numbers with an even sum of digits give all the possible residues when divided by

k{}

.
Proposed by P. Kozlov and I. Bogdanov

1

Lengths of diagonals of regular polygon

Is it possible to fit a regular polygon into a circle of radius one so that among the lengths of its diagonals there are 2023 different values whose product is equal to one?
Proposed by A. Kuznetsov

1

The plane is split into dominoes

The checkered plane is divided into dominoes. What is the maximum

k{}

for which it is always possible to choose a

100\times 100

checkered square containing at least

k{}

whole dominoes?
Proposed by S. Berlov

1

Quadrilateral is rhombus

AC{}

BD

of the trapezoid

ABCD

E{}.

The bisector of the angle

BEC

intersects the bases

BC

AD

X{}

Z{}

. The perpendicular bisector of the segment

XZ

intersects the sides

AB

CD

Y{}

T{}

XYZT{}

is a rhombus.
Proposed by M. Didin, I. Kukharchuk and P. Puchkov

1

Operations on powers of two

2,4,\ldots,2^{100}

are written on a board. At a move, one may erase the numbers

a,b

from the board and replace them with

ab/(a+b).

Prove that the last numer on the board will be greater than 1.
From the folklore

1

Hard NT with modular transformations

p{}

be a prime number. There are

p{}

a_0,\ldots,a_{p-1}

around a circle. In one move, it is allowed to select some integer

k{}

and replace the existing numbers via the operation

a_i\mapsto a_i-a_{i+k}

where indices are taken modulo

p{}.

Find all pairs of natural numbers

(m, n)

n>1

such that for any initial set of

p{}

numbers, after performing any

m{}

moves, the resulting

p{}

numbers will all be divisible by

n{}.

Proposed by P. Kozhevnikov

1

Two triangles have equal areas

D, E

F{}

be the midpoints of the sides

BC, CA

AB{}

of the acute-angled triangle

ABC

H_a, H_b

H_c{}

be the orthocenters of the triangles

ABD, BCE

CAF{}

respectively. Prove that the triangles

H_aH_bH_c

DEF

have equal areas.
Proposed by Tran Quang Hung

1

Yet another hard weighting problem

n{}

coins, one of which is fake, which differs in weight from the real ones and a two-pan scale which works correctly if the weights on the pans are different, but can show any outcome if the weights on the pans are equal. For what

n{}

can we determine which coin is fake and whether it is lighter or heavier than the real coins, in at most

k{}

weightings?
Proposed by A. Zaslavsky

1

Blue and red cells on a board

44\times 44

board, some of the cells are blue, and the rest are red. No blue cells borders another blue cell on the side. The red cells, on the other hand, form a connected component (one may get from any red cell to any other red cell only by traversing edge-adjacent red cells). Prove that less than one third of the cells on the board are blue.
Proposed by B. Frenkin

1

Tetrahedron problem

In the tetrahedron

ABCD,

on the continuation of the edges

AB, AC

AD

, three points were marked for point

A{},

A{}

at a distance equal to the semi-perimeter of the triangle

BCD.

Similarly, we marked three points corresponding to vertices

B, C

D.

Prove that if there is a sphere touching all the edges of the tetrahedron

ABCD

, then the marked 12 points lie on the same sphere.
Proposed by V. Alexandrov

1

Transforming binary sequences

Two 100-digit binary sequences are given. In one operation, one may insert (possibly at the beggining or end) or remove one or more identical digits from a sequence. What is the smallest

k{}

for which we can transform the first sequence into the second one in no more than

k{}

operations?
Proposed by V. Novikov

1

Roots of some cubics

The real numbers

a_1,a_2,a_3

b{}

are given. The equation

(x-a_1)(x-a_2)(x-a_3)=b

has three distinct real roots,

c_1,c_2,c_3.

Determine the roots of the equation

(x+c_1)(x+c_2)(x+c_3)=b.

Proposed by A. Antropov and K. Sukhov

1

chess bishops on a $100 \times 100$ chess board.

7. There are 100 chess bishops on white squares of a

100 \times 100

chess board. Some of them are white and some of them are black. They can move in any order and capture the bishops of opposing color. What number of moves is sufficient for sure to retain only one bishop on the chess board?

1

A triangle-shaped hole in a unit square paper

2. A unit square paper has a triangle-shaped hole (vertices of the hole are not on the border of the paper). Prove that a triangle with area of

1 / 6

can be cut from the remaining paper. Alexandr Yuran

1

decimal digits

For which maximal

N

there exists an

N

-digit number with the following property: among any sequence of its consecutive decimal digits some digit is present once only? Alexey Glebov

1

Determine if there exists a convex hexagon $ABCDEF$ with

a) Determine if there exists a convex hexagon

ABCDEF

\angle ABD + \angle AED > 180^{\circ},

\angle BCE + \angle BFE > 180^{\circ},

\angle CDF + \angle CAF > 180^{\circ}.

b) The same question, with additional condition, that diagonals

AD, BE,

CF

are concurrent.

1

Pasha and Vova play the game crossing out the cells of the $3\times 101$ board

Pasha and Vova play the game crossing out the cells of the

3\times 101

board by turns. At the start, the central cell is crossed out. By one move the player chooses the diagonal (there can be

1, 2

3

cells in the diagonal) and crosses out cells of this diagonal which are still uncrossed. At least one new cell must be crossed out by any player's move. Pasha begins, the one who can not make any move loses. Who has a winning strategy?

1

Grid combo with tilings

100 \times 100

is tiled in two ways - only with dominoes and only with squares

2 \times 2

. What is the least number of dominoes that are entirely inside some square

2 \times 2

1

Find the number of equivalency classes under a weird operation on permutations

In every row of a grid

100 \times n

is written a permutation of the numbers

1,2 \ldots, 100

. In one move you can choose a row and swap two non-adjacent numbers with difference

1

. Find the largest possible

n

, such that at any moment, no matter the operations made, no two rows may have the same permutations.

1

Coloring of the positive integers

Every positive integer greater than

1000

is colored in red or blue, such that the product of any two distinct red numbers is blue. Is it possible to happen that no two blue numbers have difference

1

1

Game with divisors, gcd and lcm

All the divisors of a)

8\cdot 10^6

360^{10}

are written on a board. At a move, we can take two numbers, neither of which is divisible by the other, and replace them with their greatest common divisor and lowest common multiple. At some point, we will no longer be able to perform new operations. How many different numbers will be on the board at this moment?
Proposed by V. Bragin

1

NT with binomial coefficient

Find the remainder of

\binom{3^n}{2^n}

3^{n+1}

.
Proposed by V. Rastorguev

1

Easy geo with circle

AB

be a diameter of the circle

\Omega

O{}

C, D, X

Y{}

\Omega

so that the segments

CX

DX

intersect the segment

AB

at points symmetric with respect to

O{}

XY\parallel AB

. Let the lines

AB{}

CD{}

intersect at the point

E

. Prove that the tangent to

\Omega

Y{}

E{}

1

Real numbers on vertices of polygon

Real numbers are placed at the vertices of an

n{}

-gon. On each side, we write the sum of the numbers on its endpoints. For which

n{}

is it possible that the numbers on the sides form a permutation of

1, 2, 3,\ldots , n

?
From the folklore

1

Avoid losing the game

Turbo the snail sits on a point on a circle with circumference

1

. Given an infinite sequence of positive real numbers

c_1, c_2, c_3, \dots

, Turbo successively crawls distances

c_1, c_2, c_3, \dots

around the circle, each time choosing to crawl either clockwise or counterclockwise. Determine the largest constant

C > 0

with the following property: for every sequence of positive real numbers

c_1, c_2, c_3, \dots

c_i < C

i

, Turbo can (after studying the sequence) ensure that there is some point on the circle that it will never visit or crawl across.

1

Interesting fractions

Given an integer

h > 1

. Let's call a positive common fraction (not necessarily irreducible) good if the sum of its numerator and denominator is equal to

h

. Let's say that a number

h

is remarkable if every positive common fraction whose denominator is less than

h

can be expressed in terms of good fractions (not necessarily various) using the operations of addition and subtraction. Prove that

h

is remarkable if and only if it is prime. (Recall that an common fraction has an integer numerator and a natural denominator.)

1

Cutting 100-gon

100

-gon was cut into several parallelograms and two triangles. Prove that these triangles are congruent.

1

Geometry with circles and triangle

Perimeter of triangle

ABC

1

\omega

BC

, continuation of side

AB

P

and continuation of side

AC

Q

. Line through midpoints

AB

AC

intersects circumcircle of

APQ

X

Y

. Find length of

XY

1

Russian algebra with two polynomials

Given are reals

a, b

. Prove that at least one of the equations

x^4-2b^3x+a^4=0

x^4-2a^3x+b^4=0

has a real root.
Proposed by N. Agakhanov

1

Red points inside polygon

A convex 51-gon is given. For each of its vertices and each diagonal that does not contain this vertex, we mark in red a point symmetrical to the vertex relative to the middle of the diagonal. Prove that strictly inside the polygon there are no more than 20400 red dots.
Proposed by P. Kozhevnikov

1

Circumcenter becomes orthocenter

O{}

be the circumcenter of the triangle

ABC

AC

BC

consider the points

C_a

C_b

respectively, such that

AC_a

BC_b

are equal in length to

AB

O_c{}

be the circumcenter of the triangle

CC_aC_b

. Define the points

O_a{}

O_b{}

similarly. Prove that

O{}

is the orthocenter of the triangle

O_aO_bO_c

.
Proposed by A. Zaslavsky

1

Perfect squares in weird sequence

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?
Based on the British Mathematical Olympiad

1

Counterfeit coins

On each cell of a

3\times 6

the board lies one coin. It is known that some two coins lying on adjacent cells are fake. They have the same weigh, but are lighter than the real ones. All the other coins are real. How can one find both counterfeit coins in three weightings on a double-pan balance, without using weights?
Proposed by K. Knop

1

distances between monochromatic points on a line

Given is a positive integer

k

n

points chosen on a line, such the distance between any two adjacent points is the same. The points are colored in

k

colors. For each pair of monochromatic points such that there are no points of the same color between them, we record the distance between these two points. If all distances are distinct, find the largest possible

n

1

AMPK is circumscribed

In an acute triangle

ABC

M

N

be the midpoints of

AB

AC

BH

be its altitude from

B

. Its incircle touches

AC

K

and the line through

K

MH

MN

P

AMPK

has an incircle.

1

Easy divisibility

a, b, c

be positive integers such that no number divides some other number. If

ab-b+1 \mid abc+1

c \geq b