MathDB

1

Some x_i so 1/2 < P(x_i)/P(x_j) < 2 is d-th power

P(x)

of odd degree

d

and with integer coefficients satisfying the following property: for each positive integer

n

, there exists

n

positive integers

x_1, x_2, \ldots, x_n

such that

\frac12 < \frac{P(x_i)}{P(x_j)} < 2

and

\frac{P(x_i)}{P(x_j)}

is the

d

-th power of a rational number for every pair of indices

i

and

j

with

1 \leq i, j \leq n

.

N4

1

n^k + mn^l + 1 divides n^(k+1) - 1

Let

n, m, k

and

l

be positive integers with

n \neq 1

such that

n^k + mn^l + 1

divides

n^{k+l} - 1

. Prove that
[*]

m = 1

and

l = 2k

; or [*]

l|k

and

m = \frac{n^{k-l}-1}{n^l-1}

.

A7

1

Strange FE with max

Find all functions

f:\mathbb{R}\rightarrow\mathbb{R}

such that

f(0)\neq 0

and for all

x,y\in\mathbb{R}

,

f(x+y)^2 = 2f(x)f(y) + \max \left\{ f(x^2+y^2), f(x^2)+f(y^2) \right\}.

A5

1

Fraction between sqrt(n) and sqrt(n+1)

Consider fractions

\frac{a}{b}

where

a

and

b

are positive integers. (a) Prove that for every positive integer

n

, there exists such a fraction

\frac{a}{b}

such that

\sqrt{n} \le \frac{a}{b} \le \sqrt{n+1}

and

b \le \sqrt{n}+1

. (b) Show that there are infinitely many positive integers

n

such that no such fraction

\frac{a}{b}

satisfies

\sqrt{n} \le \frac{a}{b} \le \sqrt{n+1}

and

b \le \sqrt{n}

.

N2

1

Integral ratio of divisors to divisors 1 mod 3 of 10n

Let

\tau(n)

be the number of positive divisors of

n

. Let

\tau_1(n)

be the number of positive divisors of

n

which have remainders

1

when divided by

3

. Find all positive integral values of the fraction

\frac{\tau(10n)}{\tau_1(10n)}

.

N1

1

Integer polynomial commutes with sum of digits

For any positive integer

k

, denote the sum of digits of

k

in its decimal representation by

S(k)

. Find all polynomials

P(x)

with integer coefficients such that for any positive integer

n \geq 2016

, the integer

P(n)

is positive and

S(P(n)) = P(S(n)).

Proposed by Warut Suksompong, Thailand

G8

1

Orthocenter of intriangle farther than incenter

Let

A_1, B_1

and

C_1

be points on sides

BC

,

CA

and

AB

of an acute triangle

ABC

respectively, such that

AA_1

,

BB_1

and

CC_1

are the internal angle bisectors of triangle

ABC

. Let

I

be the incentre of triangle

ABC

, and

H

be the orthocentre of triangle

A_1B_1C_1

. Show that

AH + BH + CH \geq AI + BI + CI.

A4

1

Functional equation on (0,infinity)

Find all functions

f:(0,\infty)\rightarrow (0,\infty)

such that for any

x,y\in (0,\infty)

,

xf(x^2)f(f(y)) + f(yf(x)) = f(xy) \left(f(f(x^2)) + f(f(y^2))\right).

G7

1

Reflections of lines through reflections of excenters

Let

I

be the incentre of a non-equilateral triangle

ABC

,

I_A

be the

A

-excentre,

I'_A

be the reflection of

I_A

in

BC

, and

l_A

be the reflection of line

AI'_A

in

AI

. Define points

I_B

,

I'_B

and line

l_B

analogously. Let

P

be the intersection point of

l_A

and

l_B

.
[*] Prove that

P

lies on line

OI

where

O

is the circumcentre of triangle

ABC

. [*] Let one of the tangents from

P

to the incircle of triangle

ABC

meet the circumcircle at points

X

and

Y

. Show that

\angle XIY = 120^{\circ}

.

G6

1

Perpendicular to quadrilateral diagonal

Let

ABCD

be a convex quadrilateral with

\angle ABC = \angle ADC < 90^{\circ}

. The internal angle bisectors of

\angle ABC

and

\angle ADC

meet

AC

at

E

and

F

respectively, and meet each other at point

P

. Let

M

be the midpoint of

AC

and let

\omega

be the circumcircle of triangle

BPD

. Segments

BM

and

DM

intersect

\omega

again at

X

and

Y

respectively. Denote by

Q

the intersection point of lines

XE

and

YF

. Prove that

PQ \perp AC

.

G5

1

Foot from vertex to Euler line

Let

D

be the foot of perpendicular from

A

to the Euler line (the line passing through the circumcentre and the orthocentre) of an acute scalene triangle

ABC

. A circle

\omega

with centre

S

passes through

A

and

D

, and it intersects sides

AB

and

AC

at

X

and

Y

respectively. Let

P

be the foot of altitude from

A

to

BC

, and let

M

be the midpoint of

BC

. Prove that the circumcentre of triangle

XSY

is equidistant from

P

and

M

.

A3

1

Vectors in a tilted square

Find all positive integers

n

such that the following statement holds: Suppose real numbers

a_1

,

a_2

,

\dots

,

a_n

,

b_1

,

b_2

,

\dots

,

b_n

satisfy

|a_k|+|b_k|=1

for all

k=1,\dots,n

. Then there exists

\varepsilon_1

,

\varepsilon_2

,

\dots

,

\varepsilon_n

, each of which is either

-1

or

1

, such that

\left| \sum_{i=1}^n \varepsilon_i a_i \right| + \left| \sum_{i=1}^n \varepsilon_i b_i \right| \le 1.

G4

1

Reflect incenter through side of isosceles triangle

Let

ABC

be a triangle with

AB = AC \neq BC

and let

I

be its incentre. The line

BI

meets

AC

at

D

, and the line through

D

perpendicular to

AC

meets

AI

at

E

. Prove that the reflection of

I

in

AC

lies on the circumcircle of triangle

BDE

.

G3

1

Inversion

Let

B = (-1, 0)

and

C = (1, 0)

be fixed points on the coordinate plane. A nonempty, bounded subset

S

of the plane is said to be nice if

\text{(i)}

there is a point

T

in

S

such that for every point

Q

in

S

, the segment

TQ

lies entirely in

S

; and

\text{(ii)}

for any triangle

P_1P_2P_3

, there exists a unique point

A

in

S

and a permutation

\sigma

of the indices

\{1, 2, 3\}

for which triangles

ABC

and

P_{\sigma(1)}P_{\sigma(2)}P_{\sigma(3)}

S

and

S'

of the set

\{(x, y) : x \geq 0, y \geq 0\}

such that if

A \in S

and

A' \in S'

are the unique choices of points in

\text{(ii)}

, then the product

BA \cdot BA'

is a constant independent of the triangle

P_1P_2P_3

.

N5

1

Finding Solutions

Let

a

be a positive integer which is not a perfect square, and consider the equation

k = \frac{x^2-a}{x^2-y^2}.

Let

A

be the set of positive integers

k

for which the equation admits a solution in

\mathbb Z^2

with

x>\sqrt{a}

, and let

B

be the set of positive integers for which the equation admits a solution in

\mathbb Z^2

with

0\leq x<\sqrt{a}

. Show that

A=B

.

A2

1

|a_i/a_j - a_k/a_l| <= C

Find the smallest constant

C > 0

for which the following statement holds: among any five positive real numbers

a_1,a_2,a_3,a_4,a_5

(not necessarily distinct), one can always choose distinct subscripts

i,j,k,l

such that

\left| \frac{a_i}{a_j} - \frac {a_k}{a_l} \right| \le C.

C8

1

Place dominoes on a marked board uniquely!

Let

n

be a positive integer. Determine the smallest positive integer

k

with the following property: it is possible to mark

k

cells on a

2n \times 2n

board so that there exists a unique partition of the board into

1 \times 2

and

2 \times 1

dominoes, none of which contain two marked cells.

C6

1

Prove some universal island exists!

There are

n \geq 3

islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route.
After each year, the ferry company will close a ferry route between some two islands

X

and

Y

. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected to a ferry route to exactly one of

X

and

Y

, a new route between this island and the other of

X

and

Y

is added.
Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.

G2

1

Show that XD and AM meet on Gamma

Let

ABC

be a triangle with circumcircle

\Gamma

and incenter

I

and let

M

be the midpoint of

\overline{BC}

. The points

D

,

E

,

F

are selected on sides

\overline{BC}

,

\overline{CA}

,

\overline{AB}

such that

\overline{ID} \perp \overline{BC}

,

\overline{IE}\perp \overline{AI}

, and

\overline{IF}\perp \overline{AI}

. Suppose that the circumcircle of

\triangle AEF

intersects

\Gamma

at a point

X

other than

A

. Prove that lines

XD

and

AM

meet on

\Gamma

.
Proposed by Evan Chen, Taiwan

C5

1

Maximize non-intersecting/perpendicular diagonals!

Let

n \geq 3

be a positive integer. Find the maximum number of diagonals in a regular

n

-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

C3

1

Find polychromatic isosceles triangle in 3-colored n-gon!

Let

n

be a positive integer relatively prime to

6

. We paint the vertices of a regular

n

-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours.

A8

1

nonstandard inequality

Find the largest real constant

a

such that for all

n \geq 1

and for all real numbers

x_0, x_1, ... , x_n

satisfying

0 = x_0 < x_1 < x_2 < \cdots < x_n

we have

\frac{1}{x_1-x_0} + \frac{1}{x_2-x_1} + \dots + \frac{1}{x_n-x_{n-1}} \geq a \left( \frac{2}{x_1} + \frac{3}{x_2} + \dots + \frac{n+1}{x_n} \right)

C2

1

Arrange positive divisors of n in rectangular table!

Find all positive integers

n

for which all positive divisors of

n

can be put into the cells of a rectangular table under the following constraints:
[*]each cell contains a distinct divisor; [*]the sums of all rows are equal; and [*]the sums of all columns are equal.

N6

1

IMO 2016 Shortlist, N6

Denote by

\mathbb{N}

the set of all positive integers. Find all functions

f:\mathbb{N}\rightarrow \mathbb{N}

such that for all positive integers

m

and

n

, the integer

f(m)+f(n)-mn

is nonzero and divides

mf(m)+nf(n)

.
Proposed by Dorlir Ahmeti, Albania

A1

1

3-variable inequality with min(ab,bc,ca)>=1

Let

a

,

b

,

c

be positive real numbers such that

\min(ab,bc,ca) \ge 1

. Prove that

\sqrt[3]{(a^2+1)(b^2+1)(c^2+1)} \le \left(\frac{a+b+c}{3}\right)^2 + 1.

Proposed by Tigran Margaryan, Armenia

C1

1

Guess the leader's binary string!

The leader of an IMO team chooses positive integers

n

and

k

with

n > k

, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an

n

-digit binary string, and the deputy leader writes down all

n

-digit binary strings which differ from the leader’s in exactly

k

positions. (For example, if

n = 3

and

k = 1

, and if the leader chooses

101

, the deputy leader would write down

001, 111

and

100

.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of

n

and

k

) needed to guarantee the correct answer?

2016 IMO Shortlist

Subcontests

Some x_i so 1/2 < P(x_i)/P(x_j) < 2 is d-th power

n^k + mn^l + 1 divides n^(k+1) - 1

Strange FE with max

Fraction between sqrt(n) and sqrt(n+1)

Integral ratio of divisors to divisors 1 mod 3 of 10n

Integer polynomial commutes with sum of digits

Orthocenter of intriangle farther than incenter

Functional equation on (0,infinity)

Reflections of lines through reflections of excenters

Perpendicular to quadrilateral diagonal

Foot from vertex to Euler line

Vectors in a tilted square

Reflect incenter through side of isosceles triangle

Inversion

Finding Solutions

|a_i/a_j - a_k/a_l| <= C

Place dominoes on a marked board uniquely!

Prove some universal island exists!

Show that XD and AM meet on Gamma

Maximize non-intersecting/perpendicular diagonals!

Find polychromatic isosceles triangle in 3-colored n-gon!

nonstandard inequality

Arrange positive divisors of n in rectangular table!

IMO 2016 Shortlist, N6

3-variable inequality with min(ab,bc,ca)>=1

Guess the leader's binary string!

2016 IMO Shortlist

Subcontests

Some x_i so 1/2 &lt; P(x_i)/P(x_j) &lt; 2 is d-th power

n^k + mn^l + 1 divides n^(k+1) - 1

Strange FE with max

Fraction between sqrt(n) and sqrt(n+1)

Integral ratio of divisors to divisors 1 mod 3 of 10n

Integer polynomial commutes with sum of digits

Orthocenter of intriangle farther than incenter

Functional equation on (0,infinity)

Reflections of lines through reflections of excenters

Perpendicular to quadrilateral diagonal

Foot from vertex to Euler line

Vectors in a tilted square

Reflect incenter through side of isosceles triangle

Inversion

Finding Solutions

|a_i/a_j - a_k/a_l| &lt;= C

Place dominoes on a marked board uniquely!

Prove some universal island exists!

Show that XD and AM meet on Gamma

Maximize non-intersecting/perpendicular diagonals!

Find polychromatic isosceles triangle in 3-colored n-gon!

nonstandard inequality

Arrange positive divisors of n in rectangular table!

IMO 2016 Shortlist, N6

3-variable inequality with min(ab,bc,ca)&gt;=1

Guess the leader's binary string!

Some x_i so 1/2 < P(x_i)/P(x_j) < 2 is d-th power

|a_i/a_j - a_k/a_l| <= C

3-variable inequality with min(ab,bc,ca)>=1