MathDB

1

Easy... just a long sum of tiny numbers

\sum_{k=0}^n\frac{2^{2^k}\cdot 2^{k+1}}{2^{2^k}+3^{2^k}}<4

holds for all positive integers

n

.
Submitted by Béla Kovács, Szatmárnémeti

A. 855

1

IO lines in two triangles intersect on circumcircle

In scalene triangle

ABC

the shortest side is

BC

. Let points

M

and

N

be chosen on sides

AB

and

AC

, respectively, such that

BM=CN=BC

. Let

I

and

O

denote the incenter and circumcentre of triangle

ABC

, and let

D

and

E

denote the incenter and circumcenter of triangle

AMN

. Prove that lines

IO

and

DE

intersect each other on the circumcircle of triangle

ABC

.
Submitted by Luu Dong, Vietnam

A. 856

1

Though rock-paper-scissors problem

In a rock-paper-scissors round robin tournament any two contestants play against each other ten times in a row. Each contestant has a favourite strategy, which is a fixed sequence of ten hands (for example, RRSPPRSPPS), which they play against all other contestants. At the end of the tournament it turned out that every player won at least one hand (out of the ten) against any other player. Prove that at most

1024

contestants participated in the tournament.
Submitted by Dávid Matolcsi, Budapest

A. 853

1

Brutal problem with equilateral hyperbola and Simson lines

Let points

A, B, C, A', B', C'

be chosen in the plane such that no three of them are collinear, and let lines

AA'

,

BB'

and

CC'

be tangent to a given equilateral hyperbola at points

A

,

B

and

C

, respectively. Assume that the circumcircle of

A'B'C'

is the same as the nine-point circle of triangle

ABC

. Let

s(A')

be the Simson line of point

A'

with respect to the orthic triangle of

ABC

. Let

A^*

be the intersection of line

B'C'

and the perpendicular on

s(A')

from the point

A

. Points

B^*

and

C^*

are defined in a similar manner. Prove that points

A^*

,

B^*

and

C^*

are collinear.
Submitted by Áron Bán-Szabó, Budapest

A. 852

1

Sharp inequality with strange condition

Let

(a_i,b_i)

be pairwise distinct pairs of positive integers for

1\le i\le n

. Prove that

(a_1+a_2+\ldots+a_n)(b_1+b_2+\ldots+b_n)>\frac29 n^3,

and show that the statement is sharp, i.e. for an arbitrary

c>\frac29

it is possible that

(a_1+a_2+\ldots+a_n)(b_1+b_2+\ldots+b_n)<cn^3.

Submitted by Péter Pál Pach, Budapest, based on an OKTV problem

A. 851

1

No. ways of partitioning hexagon into rhombi is polynomial

Let

k

,

\ell

and

m

be positive integers. Let

ABCDEF

be a hexagon that has a center of symmetry whose angles are all

120^\circ

and let its sidelengths be

AB=k

,

BC=\ell

and

CD=m

. Let

f(k,\ell,m)

denote the number of ways we can partition hexagon

ABCDEF

into rhombi with unit sides and an angle of

120^\circ

. Prove that by fixing

\ell

and

m

, there exists polynomial

g_{\ell,m}

such that

f(k,\ell,m)=g_{\ell,m}(k)

for every positive integer

k

, and find the degree of

g_{\ell,m}

in terms of

\ell

and

m

. Submitted by Zoltán Gyenes, Budapest

A. 850

1

Covering the perimeter of rectangle with unit disks

Prove that there exists a positive real number

N

such that for arbitrary real numbers

a,b>N

it is possible to cover the perimeter of a rectangle with side lengths

a

and

b

using non-overlapping unit disks (the unit disks can be tangent to each other).
Submitted by Benedek Váli, Budapest

A. 849

1

Equations with the closest integer function

For real number

r

let

f(r)

denote the integer that is the closest to

r

(if the fractional part of

r

is

1/2

, let

f(r)

be

r-1/2

). Let

a>b>c

rational numbers such that for all integers

n

the following is true:

f(na)+f(nb)+f(nc)=n

. What can be the values of

a

,

b

and

c

?
Submitted by Gábor Damásdi, Budapest

A. 848

1

Assigning vertices to faces in planar graph

Let

G

be a planar graph, which is also bipartite. Is it always possible to assign a vertex to each face of the graph such that no two faces have the same vertex assigned to them?
Submitted by Dávid Matolcsi, Budapest

A. 845

1

Circles through vertices tangent to the incircle

The incircle of triangle

ABC

is tangent to sides

BC

,

AC

, and

AB

at points

D

,

E

and

F

, respectively. Let

A'

denote the point of the incircle for which circle

(A'BC)

is tangent to the incircle. Define points

B'

and

C'

similarly. Prove that lines

A'D

,

BE'

, and

CF'

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

A. 846

1

Flea moves with probability 1/2

Let

n

be a positive integer and let vectors

v_1

,

v_2

,

\ldots

,

v_n

be given in the plain. A flea originally sitting in the origin moves according to the following rule: in the

i

th minute (for

i=1,2,\ldots,n

) it will stay where it is with probability

1/2

, moves with vector

v_i

with probability

1/4

, and moves with vector

-v_i

with probability

1/4

. Prove that after the

n

th minute there exists no point which is occupied by the flea with greater probability than the origin.
Proposed by Péter Pál Pach, Budapest

A. 847

1

Combinatorial inequality with sets

Let

A

be a given finite set with some of its subsets called pretty. Let a subset be called small, if it's a subset of a pretty set. Let a subset be called big, if it has a pretty subset. (A set can be small and big simultaneously, and a set can be neither small nor big.) Let

a

denote the number of elements of

A

, and let

p

,

s

and

b

denote the number of pretty, small and big sets, respectively. Prove that

2^a\cdot p\le s\cdot b

.
Proposed by András Imolay, Budapest

A. 844

1

Property of circumcenter of triangle determined by reflections

The inscribed circle of triangle

ABC

is tangent to sides

BC

,

AC

and

AB

at points

D

,

E

and

F

, respectively. Let

E'

be the reflection of point

E

across line

DF

, and

F'

be the reflection of point

F

across line

DE

. Let line

EF

intersect the circumcircle of triangle

AE'F'

at points

X

and

Y

. Prove that

DX=DY

.
Proposed by Márton Lovas, Budapest

A. 843

1

n divides k^k-1 implies n divides k-1

Let

N

be the set of those positive integers

n

for which

n\mid k^k-1

implies

n\mid k-1

for every positive integer

k

. Prove that if

n_1,n_2\in N

, then their greatest common divisor is also in

N

.

A. 842

1

People in clubs

n

people live in a town, and they are members of some clubs (residents can be members of more than one club). No matter how we choose some (but at least one) clubs, there is a resident of the town who is the member of an odd number of the chosen clubs. Prove that the number of clubs is at most

n

.
Proposed by Dömötör Pálvölgyi, Budapest

A. 841

1

Hard diophantine eq with n^{p-1}

Find all non-negative integer solutions of the equation

2^a+p^b=n^{p-1}

, where

p

is a prime number.
Proposed by Máté Weisz, Cambridge

A. 840

1

Classic incenter configurations again

The incircle of triangle

ABC

touches the sides in

X

,

Y

and

Z

. In triangle

XYZ

the feet of the altitude from

X

and

Y

are

X'

and

Y'

, respectively. Let line

X'Y'

intersect the circumcircle of triangle

ABC

at

P

and

Q

. Prove that points

X

,

Y

,

P

and

Q

are concyclic.
Proposed by László Simon, Budapest

A. 839

1

Numbers on the edges and on the vertices of a graph

We are given a finite, simple, non-directed graph. Ann writes positive real numbers on each edge of the graph such that for all vertices the following is true: the sum of the numbers written on the edges incident to a given vertex is less than one. Bob wants to write non-negative real numbers on the vertices in the following way: if the number written at vertex

v

is

v_0

, and Ann's numbers on the edges incident to

v

are

e_1,e_2,\ldots,e_k

, and the numbers on the other endpoints of these edges are

v_1,v_2,\ldots,v_k

, then

v_0=\sum_{i=1}^k e_iv_i+2022

. Prove that Bob can always number the vertices in this way regardless of the graph and the numbers chosen by Ann.
Proposed by Boldizsár Varga, Verőce

A.838

1

Comradely sets

Sets

X\subset \mathbb{Z}^{+}

and

Y\subset \mathbb{Z}^{+}

are called comradely, if every positive integer

n

can be written as

n=xy

for some

x\in X

and

y\in Y

. Let

X(n)

and

Y(n)

denote the number of elements of

X

and

Y

, respectively, among the first

n

positive integers.
Let

f\colon \mathbb{Z}^{+}\to \mathbb{R}^{+}

be an arbitrary function that goes to infinity. Prove that one can find comradely sets

X

and

Y

such that

\dfrac{X(n)}{n}

and

\dfrac{Y(n)}{n}

goes to

0

, and for all

\varepsilon>0

exists

n \in \mathbb{Z}^+

such that

\frac{\min\big\{X(n), Y(n)\big\}}{f(n)}<\varepsilon.

A.837

1

Inequality in Crelle tetrahedron

Let all the edges of tetrahedron

A_1A_2A_3A_4

be tangent to sphere

S

. Let

\displaystyle a_i

denote the length of the tangent from

A_i

to

S

. Prove that

\bigg(\sum_{i=1}^4 \frac 1{a_i}\bigg)^{\!\!2}> 2\bigg(\sum_{i=1}^4 \frac1{a_i^2}\bigg).

Submitted by Viktor Vígh, Szeged

A.836

1

Compactness property with partitions of N

For every

i \in \mathbb{N}

let

A_i

,

B_i

and

C_i

be three finite and pairwise disjoint subsets of

\mathbb{N}

. Suppose that for every pairwise disjoint sets

A

,

B

and

C

with union

\mathbb N

there exists

i\in \mathbb{N}

such that

A_i \subset A

,

B_i \subset B

and

C_i \subset C

. Prove that there also exists a finite

S\subset \mathbb{N}

such that for every pairwise disjoint sets

A

,

B

and

C

with union

\mathbb N

there exists

i\in S

such that

A_i \subset A

,

B_i \subset B

and

C_i \subset C

.
Submitted by András Imolay, Budapest

A. 835

1

f^(n) (n) = p(n)

Let

f^{(n)}(x)

denote the

n^{\text{th}}

iterate of function

f

, i.e

f^{(1)}(x)=f(x)

,

f^{(n+1)}(x)=f(f^{(n)}(x))

. Let

p(n)

be a given polynomial with integer coefficients, which maps the positive integers into the positive integers. Is it possible that the functional equation

f^{(n)}(n)=p(n)

has exactly one solution

f

that maps the positive integers into the positive integers?
Submitted by Dávid Matolcsi and Kristóf Szabó, Budapest

A. 834

1

Octagon inscribed in a conic

Let

A_1A_2\ldots A_8

be a convex cyclic octagon, and for

i=1,2\ldots,8

let

B_i=A_iA_{i+3}\cap A_{i+1}A_{i+4}

(indices are meant modulo 8). Prove that points

B_1,\ldots, B_8

lie on the same conic section.

A. 833

1

Finitely universal colorings

Some lattice points in the Cartesian coordinate system are colored red, the rest of the lattice points are colored blue. Such a coloring is called finitely universal, if for any finite, non-empty

A\subset \mathbb Z

there exists

k\in\mathbb Z

such that the point

(x,k)

is colored red if and only if

x\in A

.

a)

Does there exist a finitely universal coloring such that each row has finitely many lattice points colored red, each row is colored differently, and the set of lattice points colored red is connected?

b)

Does there exist a finitely universal coloring such that each row has a finite number of lattice points colored red, and both the set of lattice points colored red and the set of lattice points colored blue are connected?
A set

H

of lattice points is called connected if, for any

x,y\in H

, there exists a path along the grid lines that passes only through lattice points in

H

and connects

x

to

y

.
Submitted by Anett Kocsis, Budapest

A. 832

1

Going Extinct :(

Assume that the number of offspring for every man can be

0,1,\ldots, n

with with probabilities

p_0,p_1,\ldots,p_n

independently from each other, where

p_0+p_1+\cdots+p_n=1

and

p_n\neq 0

. (This is the so-called Galton-Watson process.) Which positive integer

n

and probabilities

p_0,p_1,\ldots,p_n

will maximize the probability that the offspring of a given man go extinct in exactly the tenth generation?

A. 831

1

Nice Collinearity

In triangle

ABC

let

F

denote the midpoint of side

BC

. Let the circle passing through point

A

and tangent to side

BC

at point

F

intersect sides

AB

and

AC

at points

M

and

N

, respectively. Let the line segments

CM

and

BN

intersect in point

X

. Let

P

be the second point of intersection of the circumcircles of triangles

BMX

and

CNX

. Prove that points

A, F

and

P

are collinear.
Proposed by Imolay András, Budapest

A. 830

1

Even Number Of Representations

For

H\subset \mathbb Z

and

n\in\mathbb Z

let

h_n

denote the number of finite subsets of

H

in which the sum of the elements is

n

. Determine whether there exists

H\subset \mathbb Z

for which

0\notin H

and

h_n

is a finite even number for every

n\in\mathbb{Z}

. (The sum of the elements of the empty set is

0

.)
Proposed by Csongor Beke, Cambridge

KoMaL A Problems 2022/2023

Subcontests

Easy... just a long sum of tiny numbers

IO lines in two triangles intersect on circumcircle

Though rock-paper-scissors problem

Brutal problem with equilateral hyperbola and Simson lines

Sharp inequality with strange condition

No. ways of partitioning hexagon into rhombi is polynomial

Covering the perimeter of rectangle with unit disks

Equations with the closest integer function

Assigning vertices to faces in planar graph

Circles through vertices tangent to the incircle

Flea moves with probability 1/2

Combinatorial inequality with sets

Property of circumcenter of triangle determined by reflections

n divides k^k-1 implies n divides k-1

People in clubs

Hard diophantine eq with n^{p-1}

Classic incenter configurations again

Numbers on the edges and on the vertices of a graph

Comradely sets

Inequality in Crelle tetrahedron

Compactness property with partitions of N

f^(n) (n) = p(n)

Octagon inscribed in a conic

Finitely universal colorings

Going Extinct :(

Nice Collinearity

Even Number Of Representations