MathDB

1

Nice Geometry

P

be a point inside the acute triangle

ABC,

and let

Q

be the isogonal conjugate of

P.

Let

L,M

and

N

be the midpoints of the shorter arcs

BC,CA

and

AB

of the circumcircle of

ABC,

respectively. Let

X_A

be the intersection of ray

LQ

and circle

(PBC),

let

X_B

be the intersection of ray

MQ

and circle

PCA,

and let

X_C

be the intersection of ray

NQ

and circle

(PAB).

Prove that

P,X_A,X_B

and

X_C

are concyclic or coincide.
Proposed by Gustavo Cruz (São Paulo)

A. 750

1

So Many Circles

Let

k_1,k_2,\ldots,k_5

be five circles in the lane such that

k_1

and

k_2

are externally tangent to each other at point

T,

k_3

and

k_4

are exetrnally tangent to both

k_1

and

k_2,

k_5

is externally tangent to

k_3

and

k_4

at points

U

and

V,

respectively, and

k_5

intersects

k_1

at

P

and

Q,

like shown in the figure. Prove that

\frac{PU}{QU}\cdot\frac{PV}{QV}=\frac{PT^2}{QT^2}.

A. 749

1

Polyomino Tilings

Given are two polyominos, the first one is an L-shape consisting of three squares, the other one contains at least two squares. Prove that if

n

and

m

are coprime then at most one of the

n\times n

and

m\times m

boards can be tiled by translated copies of the two polyominos.
Proposed by: András Imolay, Dávid Matolcsi, Ádám Schweitzer and Kristóf Szabó, Budapest

A. 746

1

How Many Solutions

Let

p

be a prime number. How many solutions does the congruence

x^2+y^2+z^2+1\equiv 0\pmod{p}

have among the modulo

p

remainder classes?
Proposed by: Zoltán Gyenes, Budapest

A. 745

1

Polyhedron Clock

A clock hand is attached to every face of a convex polyhedron. Each hand always points towards a neighboring face and every minute, exactly one of the hands turns clockwise to point at the next face. Suppose that the hands on neighboring faces never point towards one another. Show that one of the hands makes only finitely many turns.

A. 744

1

Vectors With Special Properties

Show that for every odd integer

N>5

there exist vectors

\bf u,v,w

in (three-dimensional) space which are pairwise perpendicular, not parallel with any of the coordinate axes, have integer coordinates, and satisfy

N\bf =|u|=|v|=|w|.

Based on problem 2 of the 2018 Kürschák contest

A. 743

1

Concurrency In Tangential Quadrilateral

The incircle of tangential quadrilateral

ABCD

intersects diagonal

BD

at

P

and

Q

(BP<BQ).

Let

UV

be the diameter of the incircle perpendicular to

AC

(BU<BV).

Show that the lines

AC,PV,

and

QU

pass through one point.
Based on problem 2 of IOM 2018, Moscow

A. 753

1

Prime divisors of x^3 + x^2 - 4x + 1 are cubic residues modulo 13

Let

p

be a prime divisor of

x^3 + x^2 - 4x + 1

. Prove that

p

is a cubic residue modulo

13

.

A. 747

1

Every set of $k$ vertices has an odd number of common neighbours

In a simple graph on

n

vertices, every set of

k

vertices has an odd number of common neighbours. Prove that

n+k

must be odd.

A.748

1

Find the locus of Miquel point

The circles

\Omega

and

\omega

in its interior are fixed. The distinct points

A,B,C,D,E

move on

\Omega

in such a way that the line segments

AB,BC,CD,DE

are tangents to

\omega

.The lines

AB

and

CD

meet at point

P

, the lines

BC

and

DE

meet at

Q

. Let

R

be the second intersection of the circles

BCP

and

CDQ

, other than

C

. Show that

R

moves either on a circle or on a line.

A. 751

1

Powers are integers

Let

c>0

be a real number, and suppose that for every positive integer

n

, at least one percent of the numbers

1^c, 2^c, \cdots , n^c

are integers. Prove that

c

is an integer.

A.752

1

Finding the least k-sparse integer

Let

k

and

s

be positive integers such that

s<(2k + 1)^2

. Initially, one cell out of an

n \times n

grid is coloured green. On each turn, we pick some green cell

c

and colour green some

s

out of the

(2k + 1)^2

cells in the

(2k + 1) \times (2k + 1)

square centred at

c

. No cell may be coloured green twice. We say that

s

is

k-sparse

if there exists some positive number

C

such that, for every positive integer

n

, the total number of green cells after any number of turns is always going to be at most

Cn

. Find, in terms of

k

, the least

k

-sparse integer

s

.
[I]Proposed by Nikolai Beluhov.

A. 742

1

Collinearity in a twist on cyclic quad + incenters diagram

Convex quadrilateral

ABCD

is inscribed in circle

\Omega

. Its sides

AD

and

BC

intersect at point

E

. Let

M

and

N

be the midpoints of the circle arcs

AB

and

CD

not containing the other vertices, and let

I

,

J

,

K

,

L

denote the incenters of triangles

ABD

,

ABC

,

BCD

,

CDA

, respectively. Suppose

\Omega

intersects circles

IJM

and

KLN

for the second time at points

U \neq M

and

V \neq N

. Show that the points

E

,

U

, and

V

are collinear.

A. 741

1

Existence of real sequence with specific properties

Let

f

be a function defined on the positive integers with

f(n) \ge 0

and

f(n) \le f(n+1)

for all

n

. Prove that if

\sum_{n = 1}^{\infty} \frac{f(n)}{n^2}

diverges, there exists a sequence

a_1, a_2, \dots

such that the sequence

\tfrac{a_n}{n}

hits every natural number, while

a_{n+m} \le a_n + a_m + f(n+m)

holds for every pair

n

,

m

.

A. 740

1

Placing 1, ..., m in empty array; row/column sums equal

A

k \times k

array contains each of the numbers

1, 2, \dots, m

exactly once, with the remaining entries all zero. Suppose that all the row sums and column sums are equal. What is the smallest possible value of

m

if

k = 3^n

(

n \in \mathbb{N}^+

)?
Attila Sztranyák and Péter Erben

A. 738

1

Sequence defined by quadratic recursion is integral

Consider the following sequence:

a_1 = 1

,

a_2 = 2

,

a_3 = 3

, and

a_{n+3} = \frac{a_{n+1}^2 + a_{n+2}^2 - 2}{a_n}

for all integers

n \ge 1

. Prove that every term of the sequence is a positive integer.

A. 739

1

Limit of a_{n_i+n_j}

Let

a_1,a_2,\dotsc

be a sequence of real numbers from the interval

[0,1]

. Prove that there is a sequence

1\leqslant n_1<n_2<\dotsc

of positive integers such that

A=\lim_{\substack{i,j\to \infty \\ i\neq j}} a_{n_i+n_j}

exists, i.e., for every real number

\epsilon >0

, there is a constant

N_{\epsilon}

that

|a_{n_i+n_j}-A|<\epsilon

is satisfied for any pair of distinct indices

i,j>N_{\epsilon}

.

A. 737

1

Five-vertex convex polyhedra

100

points are given in space such that no four of them lie in the same plane. Consider those convex polyhedra with five vertices that have all vertices from the given set. Prove that the number of such polyhedra is even.

A. 736

1

Three circles having common radical axis

Let

P

be a point in the plane of triangle

ABC

. Denote the reflections of

A,B,C

over

P

by

A',B'

and

C'

, respectively. Let

A'',B'',C''

be the reflection of

A',B',C'

over

BC,CA

and

AB

, respectively. Let the line

A''B''

intersects

AC

at

A_b

and let

A''C''

intersects

AB

at

A_c

. Denote by

\omega_A

the circle through the points

A,A_b,A_c

. The circles

\omega_B,\omega_C

are defined similarly. Prove that

\omega_A ,\omega_B ,\omega_C

are coaxial, i.e., they share a common radical axis.
Proposed by Navneel Singhal, Delhi and K. V. Sudharshan, Chennai, India

A. 735

1

Piecewise linear function

For any function

f:[0,1]\to [0,1]

, let

P_n (f)

denote the number of fixed points of the function

\underbrace{f(f(\dotsc f}_{n} (x)\dotsc )

, i.e., the number of points

x\in [0,1]

satisfying

\underbrace{f(f(\dotsc f}_{n} (x)\dotsc )=x

. Construct a piecewise linear, continuous, surjective function

f:[0,1] \to [0,1]

such that for a suitable

2<A<3

, the sequence

\frac{P_n(f)}{A^n}

converges.
Based on the 8th problem of the Miklós Schweitzer competition, 2018

A. 734

1

No. of cycles of the map x to 3x

For an arbitrary positive integer

m

, not divisible by

3

, consider the permutation

x \mapsto 3x \pmod{m}

on the set

\{ 1,2,\dotsc ,m-1\}

. This permutation can be decomposed into disjointed cycles; for instance, for

m=10

the cycles are

(1\mapsto 3\to 9,\mapsto 7,\mapsto 1)

,

(2\mapsto 6\mapsto 8\mapsto 4\mapsto 2)

and

(5\mapsto 5)

. For which integers

m

is the number of cycles odd?

A. 733

1

Tangents from a point varied on a circle

Circle

\omega

lies in the interior of circle

\Omega

, on which a point

X

moves. The tangents from

X

to

\omega

intersect

\Omega

for the second time at points

A\neq X

and

B\neq X

. Prove that the lines

AB

are either all tangent to a fixed circle, or they all pass through a point.

A. 732

1

Bound but not periodic recursion

Does there exist an infinite sequence

a_1,a_2,\dotsc

of real numbers which is bounded, not periodic, and satisfies the recursion

a_{n+1}=a_na_{n-1}+1

?

A. 731

1

Embed a graph on given points

Let

G=(V,E)

be a tree graph with

n

vertices, and let

P

be a set of

n

points in the plane with no three points collinear. Is it true that for any choice of graph

G

and set

P

, we can embed

G

in

P

, i.e., we can find a bijection

f:V\to P

such that when we draw line segment

[f(x),f(y)]

for all

(x,y)\in E

, no two such segments intersect each other?

A. 730

1

Fibonacci

Let

F_n

be the

n

th Fibonacci number (

F_1=F_2=1

and

F_{n+1}=F_n+F_{n-1}

). Construct infinitely many positive integers

n

such that

n

divides

F_{F_n}

but

n

does not divide

F_n

.

A. 729

1

Another cyclic quad

In a cyclic quadrilateral

ABCD

, the diagonals meet at point

E

, the midpoint of side

AB

is

F

, and the feet of perpendiculars from

E

to the lines

DA,AB

and

BC

are

P,Q

and

R

, respectively. Prove that the points

P,Q,R

and

F

are concyclic.

A. 728

1

Floyd the flea

Floyd the flea makes jumps on the positive integers. On the first day he can jump to any positive integer. From then on, every day he jumps to another number that is not more than twice his previous day's place.
[*]Show that Floyd can make infinitely many jumps in such a way that he never arrives at any number with the same sum of decimal digits as at a previous place.[/*] [*]Can the flea jump this way if we consider the sum of binary digits instead of decimal digits?[/*]

KoMaL A Problems 2018/2019

Subcontests

Nice Geometry

So Many Circles

Polyomino Tilings

How Many Solutions

Polyhedron Clock

Vectors With Special Properties

Concurrency In Tangential Quadrilateral

Prime divisors of x^3 + x^2 - 4x + 1 are cubic residues modulo 13

Every set of $k$ vertices has an odd number of common neighbours

Find the locus of Miquel point

Powers are integers

Finding the least k-sparse integer

Collinearity in a twist on cyclic quad + incenters diagram

Existence of real sequence with specific properties

Placing 1, ..., m in empty array; row/column sums equal

Sequence defined by quadratic recursion is integral

Limit of a_{n_i+n_j}

Five-vertex convex polyhedra

Three circles having common radical axis

Piecewise linear function

No. of cycles of the map x to 3x

Tangents from a point varied on a circle

Bound but not periodic recursion

Embed a graph on given points

Fibonacci

Another cyclic quad

Floyd the flea