MathDB

1

max min in a graph

G

be a simple graph on

n

vertices with at least one edge, and let us consider those

S:V(G)\to\mathbb R^{\ge 0}

weighings of the vertices of the graph for which

\sum_{v\in V(G)} S(v)=1

. Furthermore define

f(G)=\max_S\min_{(v,w)\in E(G)}S(v)S(w),

where

S

runs through all possible weighings.
Prove that

f(G)=\frac1{n^2}

if and only if the vertices of

G

can be covered with a disjoint union of edges and odd cycles.
(

V(G)

denotes the vertices of graph

G

,

E(G)

denotes the edges of graph

G

.)

A. 828

1

Orthocenter of triangle formed by polars is Nagel point

Triangle

ABC

has incenter

I

and excircles

\Omega_A

,

\Omega_B

, and

\Omega_C

. Let

\ell_A

be the line through the feet of the tangents from

I

to

\Omega_A

, and define lines

\ell_B

and

\ell_C

\ell_A

,

\ell_B

, and

\ell_C

coincides with the Nagel point of triangle

ABC

.
(The Nagel point of triangle

ABC

is the intersection of segments

AT_A

,

BT_B

, and

CT_C

, where

T_A

is the tangency point of

\Omega_A

with side

BC

, and points

T_B

and

T_C

A. 827

1

Cards at a round table

Let

n>1

be a given integer. In a deck of cards the cards are of

n

different suites and

n

different values, and for each pair of a suite and a value there is exactly one such card. We shuffle the deck and distribute the cards among

n

players giving each player

n

cards. The players' goal is to choose a way to sit down around a round table so that they will be able to do the following: the first player puts down an arbitrary card, and then each consecutive player puts down a card that has a different suite and different value compared to the previous card that was put down on the table. For which

n

is it possible that the cards were distributed in such a way that the players cannot achieve their goal? (The players work together, and they can see each other's cards.)
Proposed by Anett Kocsis, Budapest

A. 826

1

Numbers joined by an antelope

An antelope is a chess piece which moves similarly to the knight: two cells

(x_1,y_1)

and

(x_2,y_2)

are joined by an antelope move if and only if

\{|x_1-x_2|,|y_1-y_2|\}=\{3,4\}.

The numbers from

1

to

10^{12}

are placed in the cells of a

10^6\times 10^6

grid. Let

D

be the set of all absolute differences of the form

|a-b|

, where

a

and

b

are joined by an antelope move in the arrangement. How many arrangements are there such that

D

contains exactly four elements?
Proposed by Nikolai Beluhov, Bulgaria

A. 825

1

Functional equation with lim f(n+1)/f(n)=1

Find all functions

f:\mathbb Z^+\to\mathbb R^+

that satisfy

f(nk^2)=f(n)f^2(k)

for all positive integers

n

and

k

, furthermore

\lim\limits_{n\to\infty}\dfrac{f(n+1)}{f(n)}=1

.

A. 824

1

Thick sets

An infinite set

S

of positive numbers is called thick, if in every interval of the form

\left [1/(n+1),1/n\right]

(where

n

is an arbitrary positive integer) there is a number which is the difference of two elements from

S

. Does there exist a thick set such that the sum of its elements is finite?
Proposed by Gábor Szűcs, Szikszó

A. 823

1

n\sqrt{n} lattice points

For positive integers

n

consider the lattice points

S_n=\{(x,y,z):1\le x\le n, 1\le y\le n, 1\le z\le n, x,y,z\in \mathbb N\}.

Is it possible to find a positive integer

n

for which it is possible to choose more than

n\sqrt{n}

lattice points from

S_n

such that for any two chosen lattice points at least two of the coordinates of one is strictly greater than the corresponding coordinates of the other?
[I]Proposed by Endre Csóka, Budapest

A. 822

1

Rational numbers with sum 0 and product 1

Is it possible to find

p,q,r\in\mathbb Q

such that

p+q+r=0

and

pqr=1

?
Proposed by Máté Weisz, Cambridge

A. 821

1

Is it possibile to find a function $f:\mathbb N^2\to\mathbb N$

a) Is it possible to find a function

f:\mathbb N^2\to\mathbb N

such that for every function

g:\mathbb N\to\mathbb N

and positive integer

M

there exists

n\in\mathbb N

such that set

\left\{k\in \mathbb N : f(n,k)=g(k)\right\}

has at least

M

elements? b) Is it possible to find a function

f:\mathbb N^2\to\mathbb N

such that for every function

g:\mathbb N\to\mathbb N

there exists

n\in \mathbb N

such that set

\left\{k\in\mathbb N : f(n,k)=g(k)\right\}

has an infinite number of elements?

A. 820

1

Many Concurrencies

Let

ABC

be an arbitrary triangle. Let the excircle tangent to side

a

be tangent to lines

AB,BC

and

CA

at points

C_a,A_a,

and

B_a,

respectively. Similarly, let the excircle tangent to side

b

be tangent to lines

AB,BC,

and

CA

at points

C_b,A_b,

and

B_b,

respectively. Finally, let the excircle tangent to side

c

be tangent to lines

AB,BC,

and

CA

at points

C_c,A_c,

and

B_c,

respectively. Let

A'

be the intersection of lines

A_bC_b

and

A_cB_c.

Similarly, let

B'

be the intersection of lines

B_aC_a

and

A_cB_c,

and let

C

be the intersection of lines

B_aC_a

and

A_bC_b.

Finally, let the incircle be tangent to sides

a,b,

and

c

at points

T_a,T_b,

and

T_c,

respectively.
a) Prove that lines

A'A_a,B'B_b,

and

C'C_c

are concurrent.
b) Prove that lines

A'T_a, B'T_b,

and

C'T_c

are also concurrent, and their point of intersection is on the line defined by the orthocentre and the incentre of triangle

ABC.

Proposed by Viktor Csaplár, Bátorkeszi and Dániel Hegedűs, Gyöngyös

A. 819

1

Graph Labelling

Let

G

be an arbitrarily chosen finite simple graph. We write non-negative integers on the vertices of the graph such that for each vertex

v

in

G,

the number written on

v

is equal to the number of vertices adjacent to

v

where an even number is written. Prove that the number of ways to achieve this is a power of

2

.

A. 817

1

Mixtilinear Geometry

Let

ABC

be a triangle. Let

T

be the point of tangency of the circumcircle of triangle

ABC

and the

A

-mixtilinear incircle. The incircle of triangle

ABC

has center

I

and touches sides

BC,CA

and

AB

at points

D,E

and

F,

respectively. Let

N

be the midpoint of line segment

DF.

Prove that the circumcircle of triangle

BTN,

line

TI

and the perpendicular from

D

to

EF

are concurrent.
Proposed by Diaconescu Tashi, Romania

A. 816

1

Magnetic Cars

Peter has

2022

pieces of magnetic railroad cars, which are of two types: some have the front with north and the rear with south magnetic polarity, and some have the rear with north and the rear with south magnetic polarity (on these railroad cars the front and the rear can be distinguished). Peter wants to decide whether there is the same number of both types of cars. He can try to fit together two cars in one try. What is the least number of tries needed?
Proposed by Dömötör Pálvölgyi, Budapest

A. 813

1

Polynomials With Special Properties

Let

p

be a prime number and

k

be a positive integer. Let

t=\sum_{i=0}^\infty\bigg\lfloor\frac{k}{p^i}\bigg\rfloor.

a) Let

f(x)

be a polynomial of degree

k

with integer coefficients such that its leading coefficient is

1

and its constant is divisible by

p.

prove that there exists

n\in\mathbb{N}

for which

p\mid f(n),

but

p^{t+1}\nmid f(n).

b) Prove that the statement above is sharp, i.e. there exists a polynomial

g(x)

of degree

k,

integer coefficients, leading coefficient

1

and constant divisible by

p

such that if

p\mid g(n)

is true for a certain

n\in\mathbb{N},

then

p^t\mid g(n)

also holds.
Proposed by Kristóf Szabó, Budapest

A. 812

1

Token Game

Two players play the following game: there are two heaps of tokens, and they take turns to pick some tokens from them. The winner of the game is the player who takes away the last token. If the number of tokens in the two heaps are

A

and

B

at a given moment, the player whose turn it is can take away a number of tokens that is a multiple of

A

or a multiple of

B

from one of the heaps.
Find those pair of integers

(k,n)

for which the second player has a winning strategy, if the initial number of tokens is

k

in the first heap and

n

in the second heap.
Proposed by Dömötör Pálvölgyi, Budapest

A. 811

1

Distinct Intersections

Let

A

be a given set with

n

elements. Let

k<n

be a given positive integer. Find the maximum value of

m

for which it is possible to choose sets

B_i

and

C_i

for

i=1,2,\ldots,m

satisfying the following conditions:
[*]

B_i\subset A,

|B_i|=k,

[*]

C_i\subset B_i

(there is no additional condition for the number of elements in

C_i

), and [*]

B_i\cap C_j\neq B_j\cap C_i

for all

i\neq j.

A. 810

1

Infinite Sum Is Zero

For all positive integers

n,

let

r_n

be defined as

r_n=\sum_{i=0}^n(-1)^i\binom{n}{i}\frac{1}{(i+1)!}.

Prove that

\sum_{r=1}^\infty r_i=0.

A. 809

1

Geometrical Inequality

Let the lengths of the sides of triangle

ABC

be denoted by

a,b,

and

c,

using the standard notations. Let

G

denote the centroid of triangle

ABC.

Prove that for an arbitrary point

P

in the plane of the triangle the following inequality is true:

a\cdot PA^3+b\cdot PB^3+c\cdot PC^3\geq 3abc\cdot PG.

Proposed by János Schultz, Szeged

A. 806

1

Points And Lines

Four distinct lines are given in the plane, which are not concurrent and no three of which are parallel. Prove that it is possible to find four points in the plane,

A,B,C,

and

D

with the following properties:
[*]

A,B,C,

and

D

are collinear in this order; [*]

AB=BC=CD

; [*]with an appropriate order of the four given lines,

A

is on the first,

B

is on the second,

C

is on the third and

D

is on the fourth line.
Proposed by Kada Williams, Cambridge

A. 805

1

KöMaL Geometry

In acute triangle

ABC,

the feet of the altitudes are

A_1,B_1,

and

C_1

(with the usual notations on sides

BC,CA,

and

AB

respectively). The circumcircles of triangles

AB_1C_1

and

BC_1A_1

intersect at the circumcircle of triangle

ABC

ar points

P\neq A

and

Q\neq B,

respectively. Prove that lines

AQ, BP

and the Euler line of triangle

ABC

are either concurrent or parallel to each other.
Proposed by Géza Kós, Budapest

A. 804

1

Not Another Virus!

There is a city with

n

citizens. The city wants to buy sceptervirus tests with which it is possible to analyze the samples of several people at the same time. The result of a test can be the following:
[*]Virus positive: there is at least one currently infected person among the people whose samples were analyzed, and none of them were healed from an earlier infection. [*]Antibody positive: there is at least one person who was healed from an earlier infection among the people whose samples were analyzed, and none of them are infected now. [*]Neutral: either all of the people whose samples were analyzed are not infected, or there is at least one currently infected person and one person who was healed from an earlier infection. (Viruses and antibodies in samples completely neutralize each other.)
What is the smallest number of tests to buy if we would like to know if the sceptervirus is present now or it has been present earlier? (The samples are taken from the people at the same time. The people are either infected now, have been infected earlier, or haven't contacted the virus yet.)
Proposed by Csongor Beke, Cambridge

A. 803

1

Number Of Primitive Subsets

Let

\pi(n)

denote the number of primes less than or equal to

n

. A subset of

S=\{1,2,\ldots, n\}

is called primitive if there are no two elements in it with one of them dividing the other. Prove that for

n\geq 5

and

1\leq k\leq \pi(n)/2,

the number of primitive subsets of

S

with

k+1

elements is greater or equal to the number of primitive subsets of

S

with

k

elements.
Proposed by Cs. Sándor, Budapest

A. 815

1

Polynomial equiv factorial modulo prime

Let

q

be a monic polynomial with integer coefficients. Prove that there exists a constant

C

depending only on polynomial

q

such that for an arbitrary prime number

p

and an arbitrary positive integer

N \leq p

the congruence

n! \equiv q(n) \pmod p

has at most

CN^\frac {2}{3}

solutions among any

N

consecutive integers.

A. 818

1

Nice divisibility involving powers of 3

Find all pairs of positive integers

m, n

such that

9^{|m-n|}+3^{|m-n|}+1

is divisible by

m

and

n

simultaneously.

A. 814

1

Covering points with lines

We are given

666

points on the plane such that they cannot be covered by

10

lines. Show that we can choose

66

out of these points such that they can not be covered by

10

lines.

A. 807

1

Each edge is at most n cycles implies chromatic number bound

Let

n>1

be a given integer. Let

G

be a finite simple graph with the property that each of its edges is contained in at most

n

cycles. Prove that the chromatic number of the graph is at most

n+1

.

A. 808

1

Number Theory equation

Find all triples of positive integers

a, b, c

such that they are pairwise relatively prime and

a^2+3b^2c^2=7^c

.

KoMaL A Problems 2021/2022

Subcontests

max min in a graph

Orthocenter of triangle formed by polars is Nagel point

Cards at a round table

Numbers joined by an antelope

Functional equation with lim f(n+1)/f(n)=1

Thick sets

n\sqrt{n} lattice points

Rational numbers with sum 0 and product 1

Is it possibile to find a function $f:\mathbb N^2\to\mathbb N$

Many Concurrencies

Graph Labelling

Mixtilinear Geometry

Magnetic Cars

Polynomials With Special Properties

Token Game

Distinct Intersections

Infinite Sum Is Zero

Geometrical Inequality

Points And Lines

KöMaL Geometry

Not Another Virus!

Number Of Primitive Subsets

Polynomial equiv factorial modulo prime

Nice divisibility involving powers of 3

Covering points with lines

Each edge is at most n cycles implies chromatic number bound

Number Theory equation

KoMaL A Problems 2021/2022

Subcontests

max min in a graph

Orthocenter of triangle formed by polars is Nagel point

Cards at a round table

Numbers joined by an antelope

Functional equation with lim f(n+1)/f(n)=1

Thick sets

n\sqrt{n} lattice points

Rational numbers with sum 0 and product 1

Is it possibile to find a function $f:\mathbb N^2\to\mathbb N$

Many Concurrencies

Graph Labelling

Mixtilinear Geometry

Magnetic Cars

Polynomials With Special Properties

Token Game

Distinct Intersections

Infinite Sum Is Zero

Geometrical Inequality

Points And Lines

K&ouml;MaL Geometry

Not Another Virus!

Number Of Primitive Subsets

Polynomial equiv factorial modulo prime

Nice divisibility involving powers of 3

Covering points with lines

Each edge is at most n cycles implies chromatic number bound

Number Theory equation

KöMaL Geometry