MathDB

1

Functional inequality about very large prime divisors

n

with prime factorization

n = \prod_{i = 1}^{k} p_i^{\alpha_i}

, define

\mho(n) = \sum_{i: \; p_i > 10^{100}} \alpha_i.

That is,

\mho(n)

is the number of prime factors of

n

greater than

10^{100}

, counted with multiplicity.
Find all strictly increasing functions

f: \mathbb{Z} \to \mathbb{Z}

such that \mho(f(a) - f(b)) \le \mho(a - b) \text{for all integers } a \text{ and } b \text{ with } a > b.
Proposed by Rodrigo Sanches Angelo, Brazil

N7

1

gcd(f(m) + n, f(n) + m) bounded for m != n

Let

\mathbb{Z}_{>0}

denote the set of positive integers. For any positive integer

k

, a function

f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}

is called

k

-good if

\gcd(f(m) + n, f(n) + m) \le k

for all

m \neq n

. Find all

k

such that there exists a

k

-good function.
Proposed by James Rickards, Canada

N6

1

f(n) - n is periodic

Let

\mathbb{Z}_{>0}

denote the set of positive integers. Consider a function

f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}

. For any

m, n \in \mathbb{Z}_{>0}

we write

f^n(m) = \underbrace{f(f(\ldots f}_{n}(m)\ldots))

. Suppose that

f

has the following two properties:
(i) if

m, n \in \mathbb{Z}_{>0}

, then

\frac{f^n(m) - m}{n} \in \mathbb{Z}_{>0}

; (ii) The set

\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}

is finite.
Prove that the sequence

f(1) - 1, f(2) - 2, f(3) - 3, \ldots

is periodic.
Proposed by Ang Jie Jun, Singapore

G8

1

Equal-area triangulations

A triangulation of a convex polygon

\Pi

is a partitioning of

\Pi

into triangles by diagonals having no common points other than the vertices of the polygon. We say that a triangulation is a Thaiangulation if all triangles in it have the same area.
Prove that any two different Thaiangulations of a convex polygon

\Pi

differ by exactly two triangles. (In other words, prove that it is possible to replace one pair of triangles in the first Thaiangulation with a different pair of triangles so as to obtain the second Thaiangulation.)
Proposed by Bulgaria

G5

1

Two lengths are equal

Let

ABC

be a triangle with

CA \neq CB

. Let

D

,

F

, and

G

be the midpoints of the sides

AB

,

AC

, and

BC

respectively. A circle

\Gamma

passing through

C

and tangent to

AB

at

D

meets the segments

AF

and

BG

at

H

and

I

, respectively. The points

H'

and

I'

are symmetric to

H

and

I

about

F

and

G

, respectively. The line

H'I'

meets

CD

and

FG

at

Q

and

M

, respectively. The line

CM

meets

\Gamma

again at

P

. Prove that

CQ = QP

.
Proposed by El Salvador

C7

1

Low unsociable sets implies low chromatic number

In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least

3

, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most

2015

unsociable groups, prove that it is possible to partition the company into

11

parts so that no two enemies are in the same part.
Proposed by Russia

C4

1

Two-player game on [n]

Let

n

be a positive integer. Two players

A

and

B

play a game in which they take turns choosing positive integers

k \le n

. The rules of the game are:
(i) A player cannot choose a number that has been chosen by either player on any previous turn. (ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn. (iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.
The player

A

takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.
Proposed by Finland

A6

1

Block-similar polynomials

Let

n

be a fixed integer with

n \ge 2

. We say that two polynomials

P

and

Q

with real coefficients are block-similar if for each

i \in \{1, 2, \ldots, n\}

the sequences
\begin{eqnarray*} P(2015i), P(2015i - 1), \ldots, P(2015i - 2014) & \text{and}\\ Q(2015i), Q(2015i - 1), \ldots, Q(2015i - 2014) \end{eqnarray*}
are permutations of each other.
(a) Prove that there exist distinct block-similar polynomials of degree

n + 1

. (b) Prove that there do not exist distinct block-similar polynomials of degree

n

.
Proposed by David Arthur, Canada

N3

1

x_1x_2...x_(n+1)-1 is divisible by an odd prime

Let

m

and

n

be positive integers such that

m>n

. Define

x_k=\frac{m+k}{n+k}

for

k=1,2,\ldots,n+1

. Prove that if all the numbers

x_1,x_2,\ldots,x_{n+1}

are integers, then

x_1x_2\ldots x_{n+1}-1

is divisible by an odd prime.

C1

1

BULLDOZERS

In Lineland there are

n\geq1

towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the

2n

bulldozers are distinct. Every time when a left and right bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear-end of another one, the first one pushes the second one off the road, regardless of their sizes.
Let

A

and

B

be two towns, with

B

to the right of

A

. We say that town

A

can sweep town

B

away if the right bulldozer of

A

can move over to

B

pushing off all bulldozers it meets. Similarly town

B

can sweep town

A

away if the left bulldozer of

B

can move over to

A

pushing off all bulldozers of all towns on its way.
Prove that there is exactly one town that cannot be swept away by any other one.

N1

1

Floor sequence

Determine all positive integers

M

such that the sequence

a_0, a_1, a_2, \cdots

defined by a_0 = M + \frac{1}{2} \qquad \textrm{and} \qquad a_{k+1} = a_k\lfloor a_k \rfloor \textrm{for} \, k = 0, 1, 2, \cdots contains at least one integer term.

C3

1

Good Partitions

For a finite set

A

of positive integers, a partition of

A

into two disjoint nonempty subsets

A_1

and

A_2

is

<span class='latex-italic'>good</span>

if the least common multiple of the elements in

A_1

is equal to the greatest common divisor of the elements in

A_2

. Determine the minimum value of

n

such that there exists a set of

n

positive integers with exactly

2015

good partitions.

N2

1

Factorials divide

Let

a

and

b

be positive integers such that

a! + b!

divides

a!b!

. Prove that

3a \ge 2b + 2

.

G3

1

Two lines meet on semicircle

Let

ABC

be a triangle with

\angle{C} = 90^{\circ}

, and let

H

be the foot of the altitude from

C

. A point

D

is chosen inside the triangle

CBH

so that

CH

bisects

AD

. Let

P

be the intersection point of the lines

BD

and

CH

. Let

\omega

be the semicircle with diameter

BD

that meets the segment

CB

at an interior point. A line through

P

is tangent to

\omega

at

Q

. Prove that the lines

CQ

and

AD

meet on

\omega

.

A5

1

Integer to odds functional equation

Let

2\mathbb{Z} + 1

denote the set of odd integers. Find all functions

f:\mathbb{Z} \mapsto 2\mathbb{Z} + 1

satisfying

f(x + f(x) + y) + f(x - f(x) - y) = f(x+y) + f(x-y)

for every

x, y \in \mathbb{Z}

.

N4

1

lcm/gcd sequence

Suppose that

a_0, a_1, \cdots

and

b_0, b_1, \cdots

are two sequences of positive integers such that

a_0, b_0 \ge 2

and

a_{n+1} = \gcd{(a_n, b_n)} + 1, \qquad b_{n+1} = \operatorname{lcm}{(a_n, b_n)} - 1.

Show that the sequence

a_n

is eventually periodic; in other words, there exist integers

N \ge 0

and

t > 0

such that

a_{n+t} = a_n

for all

n \ge N

.

G4

1

Find all possible values of BT/BM

Let

ABC

be an acute triangle and let

M

be the midpoint of

AC

. A circle

\omega

passing through

B

and

M

meets the sides

AB

and

BC

at points

P

and

Q

respectively. Let

T

be the point such that

BPTQ

is a parallelogram. Suppose that

T

lies on the circumcircle of

ABC

. Determine all possible values of

\frac{BT}{BM}

.

A3

1

Maximize multilinear sum

Let

n

be a fixed positive integer. Find the maximum possible value of

\sum_{1 \le r < s \le 2n} (s-r-n)x_rx_s,

where

-1 \le x_i \le 1

for all

i = 1, \cdots , 2n

.

G7

1

four incircles

Let

ABCD

be a convex quadrilateral, and let

P

,

Q

,

R

, and

S

be points on the sides

AB

,

BC

,

CD

, and

DA

, respectively. Let the line segment

PR

and

QS

meet at

O

. Suppose that each of the quadrilaterals

APOS

,

BQOP

,

CROQ

, and

DSOR

has an incircle. Prove that the lines

AC

,

PQ

, and

RS

are either concurrent or parallel to each other.

A2

1

integer functional equation

Determine all functions

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

with the property that

f(x-f(y))=f(f(x))-f(y)-1

holds for all

x,y\in\mathbb{Z}

.

C6

1

not all sufficiently large integers are clean

Let

S

be a nonempty set of positive integers. We say that a positive integer

n

is clean if it has a unique representation as a sum of an odd number of distinct elements from

S

. Prove that there exist infinitely many positive integers that are not clean.

A1

1

n-variable inequality

Suppose that a sequence

a_1,a_2,\ldots

of positive real numbers satisfies

a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}

for every positive integer

k

. Prove that

a_1+a_2+\ldots+a_n\geq n

for every

n\geq2

.

G1

1

SL 2015 G1: Prove that IJ=AH

Let

ABC

be an acute triangle with orthocenter

H

. Let

G

be the point such that the quadrilateral

ABGH

is a parallelogram. Let

I

be the point on the line

GH

such that

AC

bisects

HI

. Suppose that the line

AC

intersects the circumcircle of the triangle

GCI

at

C

and

J

. Prove that

IJ = AH

.

2015 IMO Shortlist

Subcontests

Functional inequality about very large prime divisors

gcd(f(m) + n, f(n) + m) bounded for m != n

f(n) - n is periodic

Equal-area triangulations

Two lengths are equal

Low unsociable sets implies low chromatic number

Two-player game on [n]

Block-similar polynomials

x_1x_2...x_(n+1)-1 is divisible by an odd prime

BULLDOZERS

Floor sequence

Good Partitions

Factorials divide

Two lines meet on semicircle

Integer to odds functional equation

lcm/gcd sequence

Find all possible values of BT/BM

Maximize multilinear sum

four incircles

integer functional equation

not all sufficiently large integers are clean

n-variable inequality

SL 2015 G1: Prove that IJ=AH