MathDB

1

Kingdom of Anisotropy

n

cities. For every two cities there exists exactly one direct one-way road between them. We say that a path from

X

to

Y

is a sequence of roads such that one can move from

X

to

Y

along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection.
Let

A

and

B

be two distinct cities in Anisotropy. Let

N_{AB}

denote the maximal number of paths in a diverse collection of paths from

A

to

B

. Similarly, let

N_{BA}

denote the maximal number of paths in a diverse collection of paths from

B

to

A

. Prove that the equality

N_{AB} = N_{BA}

holds if and only if the number of roads going out from

A

is the same as the number of roads going out from

B

.
Proposed by Warut Suksompong, Thailand

N1

1

cubefree divisibility

Find all positive integers

n\geq1

such that there exists a pair

(a,b)

of positive integers, such that

a^2+b+3

is not divisible by the cube of any prime, and

n=\frac{ab+3b+8}{a^2+b+3}.

C7

1

The frog must be blocked

Consider a checkered

3m\times 3m

square, where

m

is an integer greater than

1.

A frog sits on the lower left corner cell

S

and wants to get to the upper right corner cell

F.

The frog can hop from any cell to either the next cell to the right or the next cell upwards.
Some cells can be sticky, and the frog gets trapped once it hops on such a cell. A set

X

of cells is called blocking if the frog cannot reach

F

from

S

when all the cells of

X

are sticky. A blocking set is minimal if it does not contain a smaller blocking set.[*]Prove that there exists a minimal blocking set containing at least

3m^2-3m

cells. [*]Prove that every minimal blocking set containing at most

3m^2

cells.

A7

1

Weird exponent, but ok

Let

n\geqslant 1

be an integer, and let

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

be

n+2

non-negative real numbers that satisfy

x_ix_{i+1}-x_{i-1}^2\geqslant 1

for all

i=1,2,\ldots,n.

Show that

x_0+x_1+\cdots+x_n+x_{n+1}>\bigg(\frac{2n}{3}\bigg)^{3/2}.

Pakawut Jiradilok and Wijit Yangjit, Thailand

C6

1

The hunter and the rabbit are at it again

A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share an edge). The hunter wins if after some finite time either:[*]the rabbit cannot move; or [*]the hunter can determine the cell in which the rabbit started.Decide whether there exists a winning strategy for the hunter.
Proposed by Aron Thomas

A1

1

set with c+2a>3b

Let

n

be a positive integer. Given is a subset

A

of

\{0,1,...,5^n\}

with

4n+2

elements. Prove that there exist three elements

a<b<c

from

A

such that

c+2a>3b

.
Proposed by Dominik Burek and Tomasz Ciesla, Poland

A2

1

Floor double summation

Which positive integers

n

make the equation

\sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{ij}{n+1} \right\rfloor=\frac{n^2(n-1)}{4}

true?

N3

1

Prefix sums of divisors are perfect squares

Find all positive integers

n

with the following property: the

k

positive divisors of

n

have a permutation

(d_1,d_2,\ldots,d_k)

such that for

i=1,2,\ldots,k

, the number

d_1+d_2+\cdots+d_i

is a perfect square.

N4

1

Bead solitaire

Let

r>1

be a rational number. Alice plays a solitaire game on a number line. Initially there is a red bead at

0

and a blue bead at

1

. In a move, Alice chooses one of the beads and an integer

k \in \mathbb{Z}

. If the chosen bead is at

x

, and the other bead is at

y

, then the bead at

x

is moved to the point

x'

satisfying

x'-y=r^k(x-y)

.
Find all

r

for which Alice can move the red bead to

1

in at most

2021

moves.

C8

1

Table of Permutations

Determine the largest integer

N

for which there exists a table

T

of integers with

N

rows and

100

columns that has the following properties:

\text{(i)}

Every row contains the numbers

1

,

2

,

\ldots

,

100

in some order.

\text{(ii)}

For any two distinct rows

r

and

s

, there is a column

c

such that

|T(r,c) - T(s, c)|\geq 2

. (Here

T(r,c)

is the entry in row

r

and column

c

.)

G5

1

Circumcenters are collinear under parallel condition

Let

ABCD

be a cyclic quadrilateral whose sides have pairwise different lengths. Let

O

be the circumcenter of

ABCD

. The internal angle bisectors of

\angle ABC

and

\angle ADC

meet

AC

at

B_1

and

D_1

, respectively. Let

O_B

be the center of the circle which passes through

B

and is tangent to

\overline{AC}

at

D_1

. Similarly, let

O_D

be the center of the circle which passes through

D

and is tangent to

\overline{AC}

at

B_1

.
Assume that

\overline{BD_1} \parallel \overline{DB_1}

. Prove that

O

lies on the line

\overline{O_BO_D}

.

N6

1

Divisibility rearrangement

Determine all integers

n\geqslant 2

with the following property: every

n

pairwise distinct integers whose sum is not divisible by

n

can be arranged in some order

a_1,a_2,\ldots, a_n

so that

n

divides

1\cdot a_1+2\cdot a_2+\cdots+n\cdot a_n.

Arsenii Nikolaiev, Anton Trygub, Oleksii Masalitin, and Fedir Yudin

G8

1

Circumcircle excircle chaos

Let

ABC

be a triangle with circumcircle

\omega

and let

\Omega_A

be the

A

-excircle. Let

X

and

Y

be the intersection points of

\omega

and

\Omega_A

. Let

P

and

Q

be the projections of

A

onto the tangent lines to

\Omega_A

at

X

and

Y

respectively. The tangent line at

P

to the circumcircle of the triangle

APX

intersects the tangent line at

Q

to the circumcircle of the triangle

AQY

at a point

R

. Prove that

\overline{AR} \perp \overline{BC}

.

G3

1

Maximize Sum of Areas in Lattice Grid

Consider a

100\times 100

square unit lattice

<span class='latex-bold'>L</span>

(hence

<span class='latex-bold'>L</span>

has

10000

points). Suppose

\mathcal{F}

is a set of polygons such that all vertices of polygons in

\mathcal{F}

lie in

<span class='latex-bold'>L</span>

and every point in

<span class='latex-bold'>L</span>

is the vertex of exactly one polygon in

\mathcal{F}.

Find the maximum possible sum of the areas of the polygons in

\mathcal{F}.

Michael Ren and Ankan Bhattacharya, USA

N7

1

Sequence eventually repeats itself

Let

a_1,a_2,a_3,\ldots

be an infinite sequence of positive integers such that

a_{n+2m}

divides

a_{n}+a_{n+m}

for all positive integers

n

and

m.

Prove that this sequence is eventually periodic, i.e. there exist positive integers

N

and

d

such that

a_n=a_{n+d}

for all

n>N.

C1

1

GCD and COMB

Let

S

be an infinite set of positive integers, such that there exist four pairwise distinct

a,b,c,d \in S

with

\gcd(a,b) \neq \gcd(c,d)

. Prove that there exist three pairwise distinct

x,y,z \in S

such that

\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)

.

A5

1

Riemann Sums

Let

n\geq 2

be an integer and let

a_1, a_2, \ldots, a_n

be positive real numbers with sum

1

. Prove that

\sum_{k=1}^n \frac{a_k}{1-a_k}(a_1+a_2+\cdots+a_{k-1})^2 < \frac{1}{3}.

G1

1

Concurrency in Parallelogram

Let

ABCD

be a parallelogram with

AC=BC.

A point

P

is chosen on the extension of ray

AB

past

B.

The circumcircle of

ACD

meets the segment

PD

again at

Q.

The circumcircle of triangle

APQ

meets the segment

PC

at

R.

Prove that lines

CD,AQ,BR

are concurrent.

A3

1

Minimize Expression Over Permutation

For each integer

n\ge 1,

compute the smallest possible value of

\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor

over all permutations

(a_1,\dots,a_n)

of

\{1,\dots,n\}.

Proposed by Shahjalal Shohag, Bangladesh

C2

1

Painting Beads on Necklace

Let

n\ge 3

be a fixed integer. There are

m\ge n+1

beads on a circular necklace. You wish to paint the beads using

n

colors, such that among any

n+1

consecutive beads every color appears at least once. Find the largest value of

m

for which this task is \emph{not} possible.
Carl Schildkraut, USA

G4

1

Nice Quadrilateral Geo

Let

ABCD

be a quadrilateral inscribed in a circle

\Omega.

Let the tangent to

\Omega

at

D

meet rays

BA

and

BC

at

E

and

F,

respectively. A point

T

is chosen inside

\triangle ABC

so that

\overline{TE}\parallel\overline{CD}

and

\overline{TF}\parallel\overline{AD}.

Let

K\ne D

be a point on segment

DF

satisfying

TD=TK.

Prove that lines

AC,DT,

and

BK

are concurrent.

N5

1

Classic Diophantine Equation

Show that

n!=a^{n-1}+b^{n-1}+c^{n-1}

has only finitely many solutions in positive integers.
Proposed by Dorlir Ahmeti, Albania

G6

1

Fitting an Equilateral Triangle in an Equilateral n-gon

Find all integers

n\geq 3

for which every convex equilateral

n

-gon of side length

1

contains an equilateral triangle of side length

1

. (Here, polygons contain their boundaries.)

N8

1

Iterated Integer Polynomial modulo n

Find all positive integers

n

for which there exists a polynomial

P(x) \in \mathbb{Z}[x]

such that for every positive integer

m\geq 1

, the numbers

P^m(1), \ldots, P^m(n)

leave exactly

\lceil n/2^m\rceil

distinct remainders when divided by

n

. (Here,

P^m

means

P

applied

m

times.)
Proposed by Carl Schildkraut, USA

C5

1

Raney Raney Go Away, Come Again Another Day

Let

n

and

k

be two integers with

n>k\geqslant 1

. There are

2n+1

students standing in a circle. Each student

S

has

2k

neighbors - namely, the

k

students closest to

S

on the left, and the

k

students closest to

S

on the right.
Suppose that

n+1

of the students are girls, and the other

n

are boys. Prove that there is a girl with at least

k

girls among her neighbors.
Proposed by Gurgen Asatryan, Armenia

A8

1

Clean and Memorable Functional Equation with a Conceptual Solution

Determine all functions

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

that satisfy

(f(a)-f(b))(f(b)-f(c))(f(c)-f(a)) = f(ab^2+bc^2+ca^2) - f(a^2b+b^2c+c^2a)

for all real numbers

a

,

b

,

c

.
Proposed by Ankan Bhattacharya, USA

2021 IMO Shortlist

Subcontests

Kingdom of Anisotropy

cubefree divisibility

The frog must be blocked

Weird exponent, but ok

The hunter and the rabbit are at it again

set with c+2a>3b

Floor double summation

Prefix sums of divisors are perfect squares

Bead solitaire

Table of Permutations

Circumcenters are collinear under parallel condition

Divisibility rearrangement

Circumcircle excircle chaos

Maximize Sum of Areas in Lattice Grid

Sequence eventually repeats itself

GCD and COMB

Riemann Sums

Concurrency in Parallelogram

Minimize Expression Over Permutation

Painting Beads on Necklace

Nice Quadrilateral Geo

Classic Diophantine Equation

Fitting an Equilateral Triangle in an Equilateral n-gon

Iterated Integer Polynomial modulo n

Raney Raney Go Away, Come Again Another Day

Clean and Memorable Functional Equation with a Conceptual Solution

2021 IMO Shortlist

Subcontests

Kingdom of Anisotropy

cubefree divisibility

The frog must be blocked

Weird exponent, but ok

The hunter and the rabbit are at it again

set with c+2a&gt;3b

Floor double summation

Prefix sums of divisors are perfect squares

Bead solitaire

Table of Permutations

Circumcenters are collinear under parallel condition

Divisibility rearrangement

Circumcircle excircle chaos

Maximize Sum of Areas in Lattice Grid

Sequence eventually repeats itself

GCD and COMB

Riemann Sums

Concurrency in Parallelogram

Minimize Expression Over Permutation

Painting Beads on Necklace

Nice Quadrilateral Geo

Classic Diophantine Equation

Fitting an Equilateral Triangle in an Equilateral n-gon

Iterated Integer Polynomial modulo n

Raney Raney Go Away, Come Again Another Day

Clean and Memorable Functional Equation with a Conceptual Solution

set with c+2a>3b