MathDB

1

Planar Graph Crossings

G(V,E)

on

n

points is drawn in the plane. For an edge

e

of the graph, let

\chi(e)

denote the number of edges that cross over edge

e

. Prove that

\sum_{e\in E}\frac{1}{\chi(e)+1}\leq 3n-6.

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

A. 773

1

Cryptic Problem

Let

b\geq 3

be a positive integer and let

\sigma

be a nonidentity permutation of the set

\{0,1,\ldots,b-1\}

such that

\sigma(0)=0.

The substitution cipher

C_\sigma

encrypts every positive integer

n

by replacing each digit

a

in the representation of

n

in base

b

with

\sigma(a).

Let

d

be any positive integer such that

b

does not divide

d.

We say that

C_\sigma

complies with

d

if

C_\sigma

maps every multiple of

d

onto a multiple of

d,

and we say that

d

is cryptic if there exists some

C_\sigma

such that

C_\sigma

complies with

d.

Let

k

be any positive integer, and let

p=2^k+1.

a) Find the greatest power of

2

that is cryptic in base

2p,

and prove that there is only one substitution cipher complying with it.
b) Find the greatest power of

p

that is cryptic in base

2p,

and prove that there is only one substitution cipher complying with it.
c) Suppose, furthermore, that

p

is a prime number. Find the greatest cryptic positive integer in base

2p

and prove that there is only one substitution cipher that complies with it.
Proposed by Nikolai Beluhov, Bulgaria

A. 771

1

Nice Configuration

Let

\omega

denote the incircle of triangle

ABC,

which is tangent to side

BC

at point

D.

Let

G

denote the second intersection of line

AD

and circle

\omega.

The tangent to

\omega

at point

G

intersects sides

AB

and

AC

at points

E

and

F

respectively. The circumscribed circle of

DEF

intersects

\omega

at points

D

and

M.

The circumscribed circle of

BCG

intersects

\omega

at points

G

and

N.

Prove that lines

AD

and

MN

are parallel.
Proposed by Ágoston Győrffy, Remeteszőlős

A. 770

1

Fibonacci Product

Find all positive integers

n

such that

n!

can be written as the product of two Fibonacci numbers.

A. 767

1

Moving Array

In an

n\times n

array all the fields are colored with a different color. In one move one can choose a row, move all the fields one place to the right, and move the last field (from the right) to the leftmost field of the row; or one can choose a column, move all the fields one place downwards, and move the field at the bottom of the column to the top field of the same column. For what values of

n

is it possible to reach any arrangement of the

n^2

fields using these kinds of steps?
Proposed by Ádám Schweitzer

A. 758

1

Feuerbach Circle

In a quadrilateral

ABCD,

AB=BC=DA/\sqrt{2},

and

\angle ABC

is a right angle. The midpoint of

BC

is

E,

the orthogonal projection of

C

on

AD

is

F,

and the orthogonal projection of

B

on

CD

is

G.

The second intersection point of circle

(BCF)

(with center

H

) and line

BG

is

K,

and the second intersection point of circle

(BCF)

and line

HK

is

L.

The intersection of lines

BL

and

CF

is

M.

The center of the Feurbach circle of triangle

BFM

is

N.

Prove that

\angle BNE

is a right angle.
Proposed by Zsombor Fehér, Cambridge

A. 765

1

So Many Terms

Find all functions

f:\mathbb{R}\to\mathbb{R}

which satisfy the following equality for all

x,y\in\mathbb{R}

f(x)f(y)-f(x-1)-f(y+1)=f(xy)+2x-2y-4.

Proposed by Dániel Dobák, Budapest

A. 764

1

How Many Nice Diagonals

We call a diagonal of a polygon nice, if it is entirely inside the polygon or entirely outside the polygon. Let

P

be an

n

–gon with no three of its vertices being on the same line. Prove that

P

has at least

3(n-3)/2

nice diagonals.
Proposed by Bálint Hujter, Budapest and Gábor Szűcs, Szikszó

A. 763

1

Finding Weights With Errors

Let

k\geq 2

be an integer. We want to determine the weight of

n

balls. One try consists of choosing two balls, and we are given the sum of the weights of the two chosen balls. We know that at most

k

of the answers can be wrong. Let

f_k(n)

denote the smallest number for which it is true that we can always find the weights of the balls with

f_k(n)

tries (the tries don't have to be decided in advance). Prove that there exist numbers

a_k

and

b_k

for which

|f_k(n)-a_kn|\leq b_k

holds.
Proposed by Surányi László, Budapest and Bálint Virág, Toronto

A. 762

1

Photos Of Trees

In a forest, there are

n

different trees (considered as points), no three of which lie on the same line. John takes photographs of the forest such that all trees are visible (and no two trees are behind each other). What is the largest number of orders of in which the trees that can appear on the photos?
Proposed by Gábor Mészáros, Sunnyvale, Kalifornia

A. 759

1

Increasing Subsequence Length

We choose a random permutation of

1,2,\ldots,n

with uniform distribution. Prove that the expected value of the length of the longest increasing subsequence in the permutation is at least

\sqrt{n}.

A.756

1

RMM-Like FE

Find all functions

f:\mathbb{R}\to\mathbb{R}

which satisfy the following conditions:

f(x+1)=f(x)+1

and

f(x^2)=f(x)^2.

Based on a problem of Romanian Masters of Mathematics

A. 778

1

Number theory

Find all square-free integers

d

for which there exist positive integers

x, y

and

n

satisfying

x^2+dy^2=2^n

Submitted by Kada Williams, Cambridge

A. 775

1

Set dense

Let

H\subseteq\mathbb{R}^3

such that if we reflect any point in

H

across another point of

H

, the resulting point is also in

H

. Prove that either

H

is dense in

{R}^3

or one can find equidistant parallel planes which cover

H

A. 772

1

Problem of probability

Each of

N

people chooses a random integer number between

1

and

19

(including

1

and

19

, and not necessarily with the same distribution). The random numbers chosen by the people are independent from each other, and it is true that each person chooses each of the

19

numbers with probability at most

99\%

. They add up the

N

chosen numbers, and take the remainder of the sum divided by

19

. Prove that the distribution of the result tends to the uniform distribution exponentially, i.e. there exists a number

0<c<1

such that the mod

19

remainder of the sum of the

N

chosen numbers equals each of the mod

19

remainders with probability between

\frac{1}{19}-c^{N}

and

\frac{1}{19}+c^{N}

.

A. 768

1

Squares in plane

Let

S

be a shape in the plane which is obtained as a union of finitely many unit squares. Prove that the ratio of the perimeter and the area of

S

is at most

8

.

A. 761

1

Good set

Let

n\ge3

be a positive integer. We say that a set

S

of positive integers is good if

|S|=n

, no element of S is a multiple of n, and the sum of all elements of

S

is not a multiple of

n

either. Find, in terms of

n

, the least positive integer

d

for which there exists a good set

S

such that there are exactly d nonempty subsets of

S

the sum of whose elements is a multiple of

n

.
Proposed by Aleksandar Makelov, Burgas, Bulgaria and Nikolai Beluhov, Stara Zagora, Bulgaria

A. 769

1

Problem of Number Theory

Find all triples

(a,b,c)

of distinct positive integers so that there exists a subset

S

of the positive integers for which for all positive integers

n

exactly one element of the triple

(an,bn,cn)

is in

S

.
Proposed by Carl Schildkraut, MIT

A. 779

1

P is a point moving on Ω.

Two circles are given in the plane,

\Omega

and inside it

\omega

. The center of

\omega

is

I

.

P

is a point moving on

\Omega

. The second intersection of the tangents from

P

to

\omega

and circle

\Omega

are

Q

and

R.

The second intersection of circle

IQR

and lines

PI

,

PQ

and

PR

are

J

,

S

and

T,

respectively. The reflection of point

J

across line

ST

is

K.

Prove that lines

PK

are concurrent.

A. 776

1

Recursive problem

Let

k > 1

be a fixed odd number, and for non-negative integers

n

let

f_n=\sum_{\substack{0\leq i\leq n\\ k\mid n-2i}}\binom{n}{i}.

Prove that

f_n

satisfy the following recursion:

f_{n}^2=\sum_{i=0}^{n} \binom{n}{i}f_{i}f_{n-i}.

A. 774

1

Circumcenter, incentre and Simson-Wallace line

Let

O

be the circumcenter of triangle

ABC,

and

D

be an arbitrary point on the circumcircle of

ABC.

Let points

X, Y

and

Z

be the orthogonal projections of point

D

onto lines

OA, OB

and

OC,

respectively. Prove that the incenter of triangle

XYZ

is on the Simson-Wallace line of triangle

ABC

corresponding to point

D.

A. 760

1

The magic trick

An illusionist and his assistant are about to perform the following magic trick.
Let

k

be a positive integer. A spectator is given

n=k!+k-1

balls numbered

1,2,…,n

. Unseen by the illusionist, the spectator arranges the balls into a sequence as he sees fit. The assistant studies the sequence, chooses some block of

k

consecutive balls, and covers them under her scarf. Then the illusionist looks at the newly obscured sequence and guesses the precise order of the

k

balls he does not see.
Devise a strategy for the illusionist and the assistant to follow so that the trick always works.
(The strategy needs to be constructed explicitly. For instance, it should be possible to implement the strategy, as described by the solver, in the form of a computer program that takes

k

and the obscured sequence as input and then runs in time polynomial in

n

. A mere proof that an appropriate strategy exists does not qualify as a complete solution.)

A. 766

1

Everything is integer

Let

T

be any triangle such that its side-lengths

a, b

and

c

and its circumradius

R

are positive integers. Show that: a) the inradius

r

of

T

is a positive integer; b) the perimeter

P

of

T

is a multiple of

4

; and c) all three of

a, b

and

c

are even.

A. 757

1

Game on [2^n-1] and [2^{n+1}-1]

For every

n

non-negative integer let

S(n)

denote a subset of the positive integers, for which

i

is an element of

S(n)

if and only if the

i

-th digit (from the right) in the base two representation of

n

is a digit

1

.
Two players,

A

and

B

play the following game: first,

A

chooses a positive integer

k

, then

B

chooses a positive integer

n

for which

2^n\geqslant k

. Let

X

denote the set of integers

\{ 0,1,\dotsc ,2^n-1\}

, let

Y

denote the set of integers

\{ 0,1,\dotsc ,2^{n+1}-1\}

. The game consists of

k

rounds, and in each round player

A

chooses an element of set

X

or

Y

, then player

B

chooses an element from the other set. For

1\leqslant i\leqslant k

let

x_i

denote the element chosen from set

X

, let

y_i

denote the element chosen from set

Y

.
Player

B

wins the game, if for every

1\leqslant i\leqslant k

and

1\leqslant j\leqslant k

,

x_i<x_j

if and only if

y_i<y_j

and

S(x_i)\subset S(x_j)

if and only if

S(y_i)\subset S(y_j)

. Which player has a winning strategy?
Proposed by Levente Bodnár, Cambridge

A. 755

1

Symmetric Polygon into a Square

Prove that every polygon that has a center of symmetry can be dissected into a square such that it is divided into finitely many polygonal pieces, and all the pieces can only be translated. (In other words, the original polygon can be divided into polygons

A_1,A_2,\dotsc ,A_n

, a square can be divided into polygons a

B_1,B_2,\dotsc ,B_n

such that for

1\leqslant i\leqslant n

polygon

B_i

is a translated copy of polygon

A_i

.)

KoMaL A Problems 2019/2020

Subcontests

Planar Graph Crossings

Cryptic Problem

Nice Configuration

Fibonacci Product

Moving Array

Feuerbach Circle

So Many Terms

How Many Nice Diagonals

Finding Weights With Errors

Photos Of Trees

Increasing Subsequence Length

RMM-Like FE

Number theory

Set dense

Problem of probability

Squares in plane

Good set

Problem of Number Theory

P is a point moving on Ω.

Recursive problem

Circumcenter, incentre and Simson-Wallace line

The magic trick

Everything is integer

Game on [2^n-1] and [2^{n+1}-1]

Symmetric Polygon into a Square

KoMaL A Problems 2019/2020

Subcontests

Planar Graph Crossings

Cryptic Problem

Nice Configuration

Fibonacci Product

Moving Array

Feuerbach Circle

So Many Terms

How Many Nice Diagonals

Finding Weights With Errors

Photos Of Trees

Increasing Subsequence Length

RMM-Like FE

Number theory

Set dense

Problem of probability

Squares in plane

Good set

Problem of Number Theory

P is a point moving on &Omega;.

Recursive problem

Circumcenter, incentre and Simson-Wallace line

The magic trick

Everything is integer

Game on [2^n-1] and [2^{n+1}-1]

Symmetric Polygon into a Square

P is a point moving on Ω.