MathDB
Problems
Contests
International Contests
KoMaL A Problems
KoMaL A Problems 2020/2021
KoMaL A Problems 2020/2021
Part of
KoMaL A Problems
Subcontests
(23)
A. 801
1
Hide problems
Composition Of Polynomials
For which values of positive integer
m
m
m
is it possible to find polynomials
P
,
Q
∈
C
[
x
]
P, Q\in\mathbb{C} [x]
P
,
Q
∈
C
[
x
]
, with degrees at least two, such that
x
(
x
+
1
)
⋯
(
x
+
m
−
1
)
=
P
(
Q
(
x
)
)
.
x(x+1)\cdots(x+m-1)=P(Q(x)).
x
(
x
+
1
)
⋯
(
x
+
m
−
1
)
=
P
(
Q
(
x
))
.
Proposed by Navid Safaei, Tehran
A. 802
1
Hide problems
Perimeter/Area Ratio
Let
P
P
P
be a given regular
100
100
100
-gon. Prove that if we take the union of two polygons that are congruent to
P
,
P,
P
,
the ratio of the perimeter and area of the resulting shape cannot be more than the ratio of the perimeter and area of
P
.
P.
P
.
A. 799
1
Hide problems
Phenomenal Construction
For a given quadrilateral
A
1
A
2
B
1
B
2
,
A_1A_2B_1B_2,
A
1
A
2
B
1
B
2
,
a point
P
P
P
is called phenomenal, if line segments
A
1
A
2
A_1A_2
A
1
A
2
and
B
1
B
2
B_1B_2
B
1
B
2
subtend the same angle at point
P
P
P
(i.e. triangles
P
A
1
A
2
PA_1A_2
P
A
1
A
2
and
P
B
1
B
2
PB_1B_2
P
B
1
B
2
which can be also also degenerate have equal inner angles at point
P
P
P
disregarding orientation).Three non-collinear points,
A
1
,
A
2
,
A_1,A_2,
A
1
,
A
2
,
and
B
1
B_1
B
1
are given in the plane. Prove that it is possible to find a disc in the plane such that for every point
B
2
B_2
B
2
on the disc, the quadrilateral
A
1
A
2
B
1
B
2
A_1A_2B_1B_2
A
1
A
2
B
1
B
2
is convex and it is possible to construct seven distinct phenomenal points (with respect to
A
1
A
2
B
1
B
2
A_1A_2B_1B_2
A
1
A
2
B
1
B
2
) only using a right ruler.With a right ruler the following two operations are allowed:[*]Given two points it is possible to draw the straight line connecting them; [*]Given a point and a straight line, it is possible to draw the straight line passing through the given point which is perpendicular to the given line.Proposed by Á. Bán-Szabó, Budapest
A. 798
1
Hide problems
Expected Value Bounding
Let
0
<
p
<
1
0<p<1
0
<
p
<
1
be given. Initially, we have
n
n
n
coins, all of which have probability
p
p
p
of landing on heads, and probability
1
−
p
1-p
1
−
p
of landing on tails (the results of the tosses are independent of each other). In each round, we toss our coins and remove those that result in heads. We keep repeating this until all our coins are removed. Let
k
n
k_n
k
n
denote the expected number of rounds that are needed to get rid of all the coins. Prove that there exists
c
>
0
c>0
c
>
0
for which the following inequality holds for all
n
>
0
n>0
n
>
0
c
(
1
+
1
2
+
⋯
+
1
n
)
<
k
n
<
1
+
c
(
1
+
1
2
+
⋯
+
1
n
)
.
c\bigg(1+\frac{1}{2}+\cdots+\frac{1}{n}\bigg)<k_n<1+c\bigg(1+\frac{1}{2}+\cdots+\frac{1}{n}\bigg).
c
(
1
+
2
1
+
⋯
+
n
1
)
<
k
n
<
1
+
c
(
1
+
2
1
+
⋯
+
n
1
)
.
A. 797
1
Hide problems
Entwined Sets
We call a system of non-empty sets
H
H
H
entwined, if for every disjoint pair of sets
A
A
A
and
B
B
B
in
H
H
H
there exists
b
∈
B
b\in B
b
∈
B
such that
A
∪
{
b
}
A\cup\{b\}
A
∪
{
b
}
is in
H
H
H
or there exists
a
∈
A
a\in A
a
∈
A
such that
B
∪
{
a
}
B\cup\{a\}
B
∪
{
a
}
is in
H
.
H.
H
.
Let
H
H
H
be an entwined system of sets containing all of
{
1
}
,
{
2
}
,
…
,
{
n
}
.
\{1\},\{2\},\ldots,\{n\}.
{
1
}
,
{
2
}
,
…
,
{
n
}
.
Prove that if
n
>
k
(
k
+
1
)
/
2
,
n>k(k+1)/2,
n
>
k
(
k
+
1
)
/2
,
then
H
H
H
contains a set with at least
k
+
1
k+1
k
+
1
elements, and this is sharp for every
k
,
k,
k
,
i.e. if
n
=
k
(
k
+
1
)
,
n=k(k+1),
n
=
k
(
k
+
1
)
,
it is possible that every set in
H
H
H
has at most
k
k
k
elements.
A. 796
1
Hide problems
Nice Geometry
Let
A
B
C
D
ABCD
A
BC
D
be a cyclic quadrilateral. Let lines
A
B
AB
A
B
and
C
D
CD
C
D
intersect in
P
,
P,
P
,
and lines
B
C
BC
BC
and
D
A
DA
D
A
intersect in
Q
.
Q.
Q
.
The feet of the perpendiculars from
P
P
P
to
B
C
BC
BC
and
D
A
DA
D
A
are
K
K
K
and
L
,
L,
L
,
and the feet of the perpendiculars from
Q
Q
Q
to
A
B
AB
A
B
and
C
D
CD
C
D
are
M
M
M
and
N
.
N.
N
.
The midpoint of diagonal
A
C
AC
A
C
is
F
.
F.
F
.
Prove that the circumcircles of triangles
F
K
N
FKN
F
K
N
and
F
L
M
,
FLM,
F
L
M
,
and the line
P
Q
PQ
PQ
are concurrent.Based on a problem by Ádám Péter Balogh, Szeged
A. 795
1
Hide problems
Game With Hats
The following game is played with a group of
n
n
n
people and
n
+
1
n+1
n
+
1
hats are numbered from
1
1
1
to
n
+
1.
n+1.
n
+
1.
The people are blindfolded and each of them puts one of the
n
+
1
n+1
n
+
1
hats on his head (the remaining hat is hidden). Now, a line is formed with the
n
n
n
people, and their eyes are uncovered: each of them can see the numbers on the hats of the people standing in front of him. Now, starting from the last person (who can see all the other players) the players take turns to guess the number of the hat on their head, but no two players can guess the same number (each player hears all the guesses from the other players).What is the highest number of guaranteed correct guesses, if the
n
n
n
people can discuss a common strategy?Proposed by Viktor Kiss, Budapest
A. 792
1
Hide problems
All The Possible Remainders
Let
p
≥
3
p\geq 3
p
≥
3
be a prime number and
0
≤
r
≤
p
−
3.
0\leq r\leq p-3.
0
≤
r
≤
p
−
3.
Let
x
1
,
x
2
,
…
,
x
p
−
1
+
r
x_1,x_2,\ldots,x_{p-1+r}
x
1
,
x
2
,
…
,
x
p
−
1
+
r
be integers satisfying
∑
i
=
1
p
−
1
+
r
x
i
k
≡
r
m
o
d
p
\sum_{i=1}^{p-1+r}x_i^k\equiv r \bmod{p}
i
=
1
∑
p
−
1
+
r
x
i
k
≡
r
mod
p
for all
1
≤
k
≤
p
−
2.
1\leq k\leq p-2.
1
≤
k
≤
p
−
2.
What are the possible remainders of numbers
x
2
,
x
2
,
…
,
x
p
−
1
+
r
x_2,x_2,\ldots,x_{p-1+r}
x
2
,
x
2
,
…
,
x
p
−
1
+
r
modulo
p
?
p?
p
?
Proposed by Dávid Matolcsi, Budapest
A. 791
1
Hide problems
Colorful Lightbulb
A lightbulb is given that emits red, green or blue light and an infinite set
S
S
S
of switches, each with three positions labeled red, green and blue. We know the following:[*]For every combination of the switches the lighbulb emits a given color. [*]If all switches are in a position with a given color, the lightbulb emits the same color. [*]If there are two combinations of the switches where each switch is in a different position, the lightbulb emits a different color for the two combinations.We create the following set
U
U
U
containing some of the subsets of
S
S
S
: for each combination of the switches let us observe the color of the lightbulb, and put the set of those switches in
U
U
U
which are in the same position as the color of the lightbulb.Prove that
U
U
U
is an ultrafilter on
S
S
S
. In other words, prove that
U
U
U
satisfies the following conditions:[*]The empty set is not in
U
.
U.
U
.
[*]If two sets are in
U
,
U,
U
,
their intersection is also in
U
.
U.
U
.
[*]If a set is in
U
,
U,
U
,
every subset of
S
S
S
containing it is also in
U
.
U.
U
.
[*]Considering a set and its complement in
S
,
S,
S
,
exactly one of these sets is contained in
U
.
U.
U
.
A. 790
1
Hide problems
Pebble Game
Andrew and Barry play the following game: there are two heaps with
a
a
a
and
b
b
b
pebbles, respectively. In the first round Barry chooses a positive integer
k
,
k,
k
,
and Andrew takes away
k
k
k
pebbles from one of the two heaps (if
k
k
k
is bigger than the number of pebbles in the heap, he takes away the complete heap). In the second round, the roles are reversed: Andrew chooses a positive integer and Barry takes away the pebbles from one of the two heaps. This goes on, in each round the two players are reversing the roles. The player that takes the last pebble loses the game.Which player has a winning strategy?Submitted by András Imolay, Budapest
A. 784
1
Hide problems
Good Intersections
Let
n
,
s
,
n,s,
n
,
s
,
and
t
t
t
be positive integers and
0
<
λ
<
1.
0<\lambda<1.
0
<
λ
<
1.
A simple graph on
n
n
n
vertices with at least
λ
n
2
\lambda n^2
λ
n
2
edges is given. We say that
(
x
1
,
…
,
x
s
,
y
1
,
…
,
y
t
)
(x_1,\ldots,x_s,y_1,\ldots,y_t)
(
x
1
,
…
,
x
s
,
y
1
,
…
,
y
t
)
is a good intersection if letters
x
i
x_i
x
i
and
y
j
y_j
y
j
denote not necessarily distinct vertices and every
x
i
y
j
x_iy_j
x
i
y
j
is an edge of the graph
(
1
≤
i
≤
s
,
(1\leq i\leq s,
(
1
≤
i
≤
s
,
1
≤
j
≤
t
)
.
1\leq j\leq t).
1
≤
j
≤
t
)
.
Prove that the number of good insertions is at least
λ
s
t
n
s
+
t
.
\lambda^{st}n^{s+t}.
λ
s
t
n
s
+
t
.
Proposed by Kada Williams, Cambridge
A. 782
1
Hide problems
Orienting Planar Graph
Prove that the edges of a simple planar graph can always be oriented such that the outdegree of all vertices is at most three.UK Competition Problem
A. 781
1
Hide problems
A Compass And A Straightedge
We want to construct an isosceles triangle using a compass and a straightedge. We are given two of the following four data: the length of the base of the triangle
(
a
)
,
(a),
(
a
)
,
the length of the leg of the triangle
(
b
)
,
(b),
(
b
)
,
the radius of the inscribed circle
(
r
)
,
(r),
(
r
)
,
and the radius of the circumscribed circle
(
R
)
.
(R).
(
R
)
.
In which of the six possible cases will we definitely be able to construct the triangle?Proposed by György Rubóczky, Budapest
A. 780
1
Hide problems
Colorful Square Lattice
We colored the
n
2
n^2
n
2
unit squares of an
n
×
n
n\times n
n
×
n
square lattice such that in each
2
×
2
2\times 2
2
×
2
square, at least two of the four unit squares have the same color. What is the largest number of colors we could have used?Based on a problem of the Dürer Competition
A. 800
1
Hide problems
Probability in connected graph
In a finite, simple, connected graph
G
G
G
we play the following game: initially we color all the vertices with a different color. In each step we choose a vertex randomly (with uniform distribution), and then choose one of its neighbors randomly (also with uniform distribution), and color it to the the same color as the originally chosen vertex (if the two chosen vertices already have the same color, we do nothing). The game ends when all the vertices have the same color.Knowing graph
G
G
G
find the probability for each vertex that the game ends with all vertices having the same color as the chosen vertex.
A. 789
1
Hide problems
About polynomial
Let
p
(
x
)
=
a
21
x
21
+
a
20
x
20
+
⋯
+
a
1
x
+
1
p(x) = a_{21} x^{21} + a_{20} x^{20} + \dots + a_1 x + 1
p
(
x
)
=
a
21
x
21
+
a
20
x
20
+
⋯
+
a
1
x
+
1
be a polynomial with integer coefficients and real roots such that the absolute value of all of its roots are less than
1
/
3
1/3
1/3
, and all the coefficients of
p
(
x
)
p(x)
p
(
x
)
are lying in the interval
[
−
2019
a
,
2019
a
]
[-2019a,2019a]
[
−
2019
a
,
2019
a
]
for some positive integer
a
a
a
. Prove that if this polynomial is reducible in
Z
[
x
]
\mathbb{Z}[x]
Z
[
x
]
, then the coefficients of one of its factors are less than
a
a
a
.Submitted by Navid Safaei, Tehran, Iran
A. 793
1
Hide problems
Euclidean space and convex hull
In the
43
43
43
dimension Euclidean space the convex hull of finite set
S
S
S
contains polyhedron
P
P
P
. We know that
P
P
P
has
47
47
47
vertices. Prove that it is possible to choose at most
2021
2021
2021
points in
S
S
S
such that the convex hull of these points also contain
P
P
P
, and this is sharp.
A. 786
1
Hide problems
Convex set and area
In a convex set
S
S
S
that contains the origin it is possible to draw
n
n
n
disjoint unit circles such that viewing from the origin non of the unit circles blocks out a part of another (or a complete) unit circle. Prove that the area of
S
S
S
is at least
n
2
100
\frac{n^2}{100}
100
n
2
.
A. 785
1
Hide problems
Kömal probability
Let
k
≥
t
≥
2
k\ge t\ge 2
k
≥
t
≥
2
positive integers. For integers
n
≥
k
n\ge k
n
≥
k
let
p
n
p_n
p
n
be the probability that if we choose
k
k
k
from the first
n
n
n
positive integers randomly, any
t
t
t
of the
k
k
k
chosen integers have greatest common divisor
1
1
1
. Let qn be the probability that if we choose
k
−
t
+
1
k-t+1
k
−
t
+
1
from the first
n
n
n
positive integers the product is not divisible by a perfect
t
t
h
t^{th}
t
t
h
power that is greater then
1
1
1
.Prove that sequences
p
n
p_n
p
n
and
q
n
q_n
q
n
converge to the same value.
A. 783
1
Hide problems
Polyomino and Coloring
A polyomino is a figure which consists of unit squares joined together by their sides. (A polyomino may contain holes.) Let
n
≥
3
n\ge3
n
≥
3
be a positive integer. Consider a grid of unit square cells which extends to infinity in all directions. Find, in terms of
n
n
n
, the greatest positive integer
C
C
C
which satisfies the following condition: For every colouring of the cells of the grid in
n
n
n
colours, there is some polyomino within the grid which contains at most
n
−
1
n-1
n
−
1
colours and whose area is at least
C
C
C
.Proposed by Nikolai Beluhov, Stara Zagora, Bulgaria and Stefan Gerdjikov, Sofia, Bulgaria
A. 794
1
Hide problems
Polyomino Caterpillar
A polyomino
P
P
P
occupies
n
n
n
cells of an infinite grid of unit squares. In each move, we lift
P
P
P
off the grid and then we place it back into a new position, possibly rotated and reflected, so that the preceding and the new position have
n
−
1
n-1
n
−
1
cells in common. We say that
P
P
P
is a caterpillar of area
n
n
n
if, by means of a series of moves, we can free up all cells initially occupied by
P
P
P
.How many caterpillars of area
n
=
1
0
6
+
1
n=10^{6}+1
n
=
1
0
6
+
1
are there?Proposed by Nikolai Beluhov, Bulgaria
A. 788
1
Hide problems
System of equations
Solve the following system of equations: x+\frac{1}{x^3}=2y, y+\frac{1}{y^3}=2z, z+\frac{1}{z^3}=2w, w+\frac{1}{w^3}=2x.
A. 787
1
Hide problems
Messing with Binomial Coefficients
Let
p
n
p_n
p
n
denote the
n
th
n^{\text{th}}
n
th
prime number and define
a
n
=
⌊
p
n
ν
⌋
a_n=\lfloor p_n\nu\rfloor
a
n
=
⌊
p
n
ν
⌋
for all positive integers
n
n
n
where
ν
\nu
ν
is a positive irrational number. Is it possible that there exist only finitely many
k
k
k
such that
(
2
a
k
a
k
)
\binom{2a_k}{a_k}
(
a
k
2
a
k
)
is divisible by
p
i
10
p_i^{10}
p
i
10
for all
i
=
1
,
2
,
…
,
2020
?
i=1,2,\ldots,2020?
i
=
1
,
2
,
…
,
2020
?
Proposed by Superguy and ayan.nmath