MathDB

1

Convergence of series of polynomials over different intervals

J\subsetneq I\subseteq \mathbb R

be non-empty open intervals, and let

f_1, f_2,\ldots

be real polynomials satisfying the following conditions:
[*]

f_i(x)\ge 0

for all

i\ge 1

and

x\in I

, [*]

\sum\limits_{i=1}^\infty f_i(x)

is finite for all

x\in I

, [*]

\sum\limits_{i=1}^\infty f_i(x)=1

for all

x\in J

.
Do these conditions imply that

\sum\limits_{i=1}^\infty f_i(x)=1

also for all

x\in I

?
Proposed by András Imolay, Budapest

A. 882

1

sum of gcd over sets is more then sum of gcd over union

Let

H_1, H_2,\ldots, H_m

be non-empty subsets of the positive integers, and let

S

denote their union. Prove that

\sum_{i=1}^m \sum_{(a,b)\in H_i^2}\gcd(a,b)\ge\frac1m \sum_{(a,b)\in S^2}\gcd(a,b).

Proposed by Dávid Matolcsi, Berkeley

A. 881

1

min change of colours in hamiltonian path of king

We visit all squares exactly once on a

n\times n

chessboard (colored in the usual way) with a king. Find the smallest number of times we had to switch colors during our walk.
Proposed by Dömötör Pálvölgyi, Budapest

A. 880

1

Function with weighted sum always negative

Find all triples

(a,b,c)

of real numbers for which there exists a function

f:\mathbb{Z}^{+}\rightarrow\mathbb{Z}^{+}

satisfying

af(n)+bf(n+1)+cf(n+2)<0

for every

n\in\mathbb{Z}^{+}

(

\mathbb{Z}^{+}

denotes the set of positive integers).
Proposed by András Imolay, Budapest

A. 878

1

Lots of circles

Let point

A

be one of the intersections of circles

c

and

k

. Let

X_1

and

X_2

be arbitrary points on circle

c

. Let

Y_i

denote the intersection of line

AX_i

and circle

k

for

i=1,2

. Let

P_1

,

P_2

and

P_3

be arbitrary points on circle

k

, and let

O

denote the center of circle

k

. Let

K_{ij}

denote the center of circle

(X_iY_iP_j)

for

i=1,2

and

j=1,2,3

. Let

L_j

denote the center of circle

(OK_{1j}K_{2j})

for

j=1,2,3

. Prove that points

L_1

,

L_2

and

L_3

are collinear.
Proposed by Vilmos Molnár-Szabó, Budapest

A. 875

1

Nice combi game

a)

Two players play a cooperative game. They can discuss a strategy prior to the game, however, they cannot communicate and have no information about the other player during the game. The game master chooses one of the players in each round. The player on turn has to guess the number of the current round. Players keep note of the number of rounds they were chosen, however, they have no information about the other player's rounds. If the player's guess is correct, the players are awarded a point. Player's are not notified whether they've scored or not. The players win the game upon collecting 100 points. Does there exist a strategy with which they can surely win the game in a finite number of rounds?

b)

How does this game change, if in each round the player on turn has two guesses instead of one, and they are awarded a point if one of the guesses is correct (while keeping all the other rules of the game the same)?
Proposed by Gábor Szűcs, Budapest

A. 877

1

Nice Nikolai Geometry

A convex quadrilateral

ABCD

is circumscribed about circle

\omega

. A tangent to

\omega

parallel to

AC

intersects

BD

at a point

P

outside of

\omega

. The second tangent from

P

to

\omega

touches

\omega

at a point

T

. Prove that

\omega

and circumcircle of

ATC

are tangent.
Proposed by Nikolai Beluhov, Bulgaria

A. 876

1

Exponential Diaphantine

Find all non negative integers

a{}

and

b{}

satisfying

5^a+6=31^b

Proposed by Erik Füredi, Budapest

A. 874

1

Lies and randomness the island

Nyihaha and Bruhaha are two neighbouring islands, both having

n

inhabitants. On island Nyihaha every inhabitant is either a Knight or a Knave. Knights always tell the truth and Knaves always lie. The inhabitants of island Bruhaha are normal people, who can choose to tell the truth or lie. When a visitor arrives on any of the two islands, the following ritual is performed: every inhabitant points randomly to another inhabitant (indepently from each other with uniform distribution), and tells "He is a Knight" or "He is a Knave'". On sland Nyihaha, Knights have to tell the truth and Knaves have to lie. On island Bruhaha every inhabitant tells the truth with probability

1/2

independently from each other. Sinbad arrives on island Bruhaha, but he does not know whether he is on island Nyihaha or island Bruhaha. Let

p_n

denote the probability that after observing the ritual he can rule out being on island Nyihaha. Is it true that

p_n\to 1

if

n\to\infty

?
Proposed by Dávid Matolcsi, Berkeley

A. 873

1

Harmonic quadrilateral(s) and a bit of nine-point circle

Let

ABCD

be a convex cyclic quadrilateral satisfying

AB\cdot CD=AD\cdot BC

. Let the inscribed circle

\omega

of triangle

ABC

be tangent to sides

BC

,

CA

and

AB

at points

A', B'

and

C'

, respectively. Let point

K

be the intersection of line

ID

and the nine-point circle of triangle

A'B'C'

that is inside line segment

ID

. Let

S

denote the centroid of triangle

A'B'C'

. Prove that lines

SK

and

BB'

intersect each other on circle

\omega

.
Proposed by Áron Bán-Szabó, Budapest

A. 872

1

Repeated difference sequences cover the positive integers

For every positive integer

k

let

a_{k,1},a_{k,2},\ldots

be a sequence of positive integers. For every positive integer

k

let sequence

\{a_{k+1,i}\}

be the difference sequence of

\{a_{k,i}\}

, i.e. for all positive integers

k

and

i

the following holds:

a_{k,i+1}-a_{k,i}=a_{k+1,i}

. Is it possible that every positive integer appears exactly once among numbers

a_{k,i}

?
Proposed by Dávid Matolcsi, Berkeley

A. 871

1

X lies on circumcircle of triangle formed by polars of X

Let

ABC

be an obtuse triangle, and let

H

denote its orthocenter. Let

\omega_A

denote the circle with center

A

and radius

AH

. Let

\omega_B

and

\omega_C

be defined in a similar way. For all points

X

in the plane of triangle

ABC

let circle

\Omega(X)

be defined in the following way (if possible): take the polars of point

X

with respect to circles

\omega_A

,

\omega_B

and

\omega_C

, and let

\Omega(X)

be the circumcircle of the triangle defined by these three lines. With a possible exception of finitely many points find the locus of points

X

for which point

X

lies on circle

\Omega(X)

.
Proposed by Vilmos Molnár-Szabó, Budapest

A. 870

1

Largest sum of differences of degrees for graph

We label every edge of a simple graph with the difference of the degrees of its endpoints. If the number of vertices is

N

, what can be the largest value of the sum of the labels on the edges?
Proposed by Dániel Lenger and Gábor Szűcs, Budapest

A. 869

1

Maximum distance of points on solids in R^n

Let

A

and

B

be given real numbers. Let the sum of real numbers

0\le x_1\le x_2\le\ldots \le x_n

be

A

, and let the sum of real numbers

0\le y_1\le y_2\le \ldots\le y_n

be

B

. Find the largest possible value of

\sum_{i=1}^n (x_i-y_i)^2.

Proposed by Péter Csikvári, Budapest

A. 868

1

Collineation destroying ratios?

A set of points in the plane is called disharmonic, if the ratio of any two distances between the points is between

100/101

and

101/100

, or at least

100

or at most

1/100

. Is it true that for any distinct points

A_1,A_2,\ldots,A_n

in the plane it is always possible to find distinct points

A_1',A_2',\ldots, A_n'

that form a disharmonic set of points, and moreover

A_i, A_j

and

A_k

are collinear in this order if and only if

A_i', A_j'

and

A_k'

are collinear in this order (for all distinct

1 \le i,j,k\le n

?
Submitted by Dömötör Pálvölgyi and Balázs Keszegh, Budapest

A. 867

1

Sum of absoulte values of polynomial at roots of the other

Let

p(x)

be a monic integer polynomial of degree

n

that has

n

real roots,

\alpha_1,\alpha_2,\ldots, \alpha_n

. Let

q(x)

be an arbitrary integer polynomial that is relatively prime to polynomial

p(x)

. Prove that

\sum_{i=1}^n \left|q(\alpha_i)\right|\ge n.

Submitted by Dávid Matolcsi, Berkeley

A. 866

1

2-connected infinite graph has infinite trail

Is it true that in any

2

-connected graph with a countably infinite number of vertices it's always possible to find a trail that is infinite in one direction?
Submitted by Balázs Bursics and Anett Kocsis, Budapest

A. 865

1

Another impossible Beluhov problem: words upper bound in crossword

A crossword is a grid of black and white cells such that every white cell belongs to some

2\times 2

square of white cells. A word in the crossword is a contiguous sequence of two or more white cells in the same row or column, delimited on each side by either a black cell or the boundary of the grid. Show that the total number of words in an

n\times n

crossword cannot exceed

(n+1)^2/2

.
Proposed by Nikolai Beluhov, Bulgaria

A. 864

1

Smoothie of incircle configurations from KoMaL

Let

ABC

be a triangle and

O

be its circumcenter. Let

D

,

E

and

F

be the respective tangent points of the incircle of

\triangle ABC

, and sides

BC

,

CA

and

AB

. Let

M

and

N

be the respective midpoints of sides

AB

and

AC

. Let

M'

and

N'

be the respective reflections of points

M

and

N

across lines

DE

and

DF

. Let lines

CM'

and

BN'

intersect lines

DE

and

DF

at points

H

and

J

, respectively. Prove that the points

H

,

J

and

O

are collinear.
Proposed by Luu Dong, Vietnam

A. 863

1

Infinitely many N-tuples of n-free numbers

Let

n\ge 2

be a given integer. Find the greatest value of

N

, for which the following is true: there are infinitely many ways to find

N

consecutive integers such that none of them has a divisor greater than

1

that is a perfect

n^{\mathrm{th}}

power.
Proposed by Péter Pál Pach, Budapest

A. 862

1

Quadrilateral geo with incircles

Let

ABCD

be a cyclic quadrilateral inscribed in circle

\omega

. Let

F_A, F_B, F_C

and

F_D

be the midpoints of arcs

AB, BC, CD

and

DA

of

\omega

. Let

I_A, I_B, I_C

and

I_D

be the incenters of triangles

DAB, ABC, BCD

and

CDA

, respectively.
Let

\omega_A

denote the circle that is tangent to

\omega

at

F_A

and also tangent to line segment

CD

. Similarly, let

\omega_C

denote the circle that is tangent to

\omega

at

F_C

and tangent to line segment

AB

.
Finally, let

T_B

denote the second intersection of

\omega

and circle

F_BI_BI_C

different from

F_B

, and let

T_D

denote the second intersection of

\omega

and circle

F_DI_DI_A

.
Prove that the radical axis of circles

\omega_A

and

\omega_C

passes through points

T_B

and

T_D

.

A. 861

1

Iteration of x^2-2

Let

f(x)=x^2-2

and let

f^{(n)}(x)

denote the

n

-th iteration of

f

. Let

H=\{x:f^{(100)}(x)\leq -1\}

. Find the length of

H

(the sum of the lengths of the intervals of

H

).

A.860

1

Guessing game on a binary string

A 0-1 sequence of length

2^k

is given. Alice can pick a member from the sequence, and reveal it (its place and its value) to Bob. Find the largest number

s

for which Bob can always pick

s

members of the sequence, and guess all their values correctly.
Alice and Bob can discuss a strategy before the game with the aim of maximizing the number of correct guesses of Bob. The only information Bob has is the length of the sequence and the member of the sequence picked by Alice.

A. 858

1

5 variables, 2 equations, 1 solution

Prove that the only integer solution of the following system of equations is

u=v=x=y=z=0

:

uv=x^2-5y^2, (u+v)(u+2v)=x^2-5z^2

A. 859

1

Game on a graph

Path graph

U

is given, and a blindfolded player is standing on one of its vertices. The vertices of

U

are labeled with positive integers between 1 and

n

, not necessarily in the natural order. In each step of the game, the game master tells the player whether he is in a vertex with degree 1 or with degree 2. If he is in a vertex with degree 1, he has to move to its only neighbour, if he is in a vertex with degree 2, he can decide whether he wants to move to the adjacent vertex with the lower or with the higher number. All the information the player has during the game after

k

steps are the

k

degrees of the vertices he visited and his choice for each step. Is there a strategy for the player with which he can decide in finitely many steps how many vertices the path has?

A. 857

1

Configuration with midpoints and altitudes

Let

ABC

be a given acute triangle, in which

BC

is the longest side. Let

H

be the orthocenter of the triangle, and let

D

and

E

be the feet of the altitudes from

B

and

C

, respectively. Let

F

and

G

be the midpoints of sides

AB

and

AC

, respectively.

X

is the point of intersection of lines

DF

and

EG

. Let

O_1

and

O_2

be the circumcenters of triangles

EFX

and

DGX

, respectively. Finally,

M

is the midpoint of line segment

O_1O_2

. Prove that points

X, H

and

M

are collinear.

A. 879

1

IMO Shortlist 2013, Number Theory #5

Fix an integer

k>2

. Two players, called Ana and Banana, play the following game of numbers. Initially, some integer

n \ge k

gets written on the blackboard. Then they take moves in turn, with Ana beginning. A player making a move erases the number

m

just written on the blackboard and replaces it by some number

m'

with

k \le m' < m

that is coprime to

m

. The first player who cannot move anymore loses.
An integer

n \ge k

is called good if Banana has a winning strategy when the initial number is

n

, and bad otherwise.
Consider two integers

n,n' \ge k

with the property that each prime number

p \le k

divides

n

if and only if it divides

n'

. Prove that either both

n

and

n'

are good or both are bad.

KoMaL A Problems 2023/2024

Subcontests

Convergence of series of polynomials over different intervals

sum of gcd over sets is more then sum of gcd over union

min change of colours in hamiltonian path of king

Function with weighted sum always negative

Lots of circles

Nice combi game

Nice Nikolai Geometry

Exponential Diaphantine

Lies and randomness the island

Harmonic quadrilateral(s) and a bit of nine-point circle

Repeated difference sequences cover the positive integers

X lies on circumcircle of triangle formed by polars of X

Largest sum of differences of degrees for graph

Maximum distance of points on solids in R^n

Collineation destroying ratios?

Sum of absoulte values of polynomial at roots of the other

2-connected infinite graph has infinite trail

Another impossible Beluhov problem: words upper bound in crossword

Smoothie of incircle configurations from KoMaL

Infinitely many N-tuples of n-free numbers

Quadrilateral geo with incircles

Iteration of x^2-2

Guessing game on a binary string

5 variables, 2 equations, 1 solution

Game on a graph

Configuration with midpoints and altitudes

IMO Shortlist 2013, Number Theory #5