2021-IMOC

Part of IMOC Shortlist

Subcontests

(44)

1

100x100 grid, spider walking and eating bugs

100

100

grid, there is a spider and

100

bugs. Each time, the spider can walk up, down, left or right, and the spider aims to visit all the squares with bugs to eat them all. The spider begins from the top-left corner. Show that no matter where the bugs are, the spider can always eat them all within

2000

1

find sets with three conditions, closed under gcd and *

S

of positive integers that satisfy all of the following.

1.

a,b

are two not necessarily distinct elements in

S

\gcd(a,b)

ab

S

2.

m,n

are two positive integers with

n\nmid m

, then there exists an element

s

S

m^2\mid s

n^2\nmid s

3.

For any odd prime

p

, the set formed by moduloing all elements in

S

p

has size exactly

\frac{p+1}2

1

sequence with greatest prime factor

Define the function

f:\mathbb N_{>1}\to\mathbb N_{>1}

f(x)

is the greatest prime factor of

x

. A sequence of positive integers

\{a_n\}

a_1=M>1

a_{n+1}=\begin{cases}a_n-f(a_n)&\text{if }a_n\text{ is composite.}\\a_n+k&\text{otherwise.}\end{cases}

Show that for any positive integers

M,k

\{a_n\}

is bounded.
(TAN768092100853)

1

IMOC 2021 N1

This problem consists of four parts.
1. Show that for any nonzero integers

m,n,

p

v_p(mn)=v_p(m)+v_p(n).

2. Show that if an off prime

p

, a positive integer

k

a,b

p \nmid ~^\text{'}~p|a-b

p\nmid k

v_p(a^k-b^k)=v_p(a-b).

3. Show that if

p

is an off prime with

p|a-b

p\nmid a,b

v_p(a^p-b^p)=v_p(a-b)+1)

.
4. Show that if an odd prime

p

, a positive integer

k

a,b

p\nmid a,b ~^\text{'}~ p|a-b

v_p(a^k-b^k)=v_p(a-b)

.
Proposed by LTE.

1

Attacking Squirrels

Given a positive integer

N

. There are three squirrels that each have an integer. It is known that the largest integer and the least one differ by exactly

N

. Each time, the squirrel with the second largest integer looks at the squirrel with the largest integer. If the integers they have are different, then the squirrel with the second largest integer would be unhappy and attack the squirrel with the largest one, making its integer decrease by two times the difference between the two integers. If the second largest integer is the same as the least integer, only of the squirrels would attack the squirrel with the largest integer. The attack continues until the largest integer becomes the same as the second largest integer. What is the maximum total number of attacks these squirrels make?
Proposed by USJL, ST.

1

IMOC 2021 A5

M

be an arbitrary positive real number greater than

1

a_1,a_2,...

be an infinite sequence of real numbers with

a_n\in [1,M]

n\in \mathbb{N}

. Show that for any

\epsilon\ge 0

, there exists a positive integer

n

\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_{n+2}}+\cdots+\frac{a_{n+t-1}}{a_{n+t}}\ge t-\epsilon

holds for any positive integer

t

1

IMOC 2021 A2

For any positive integers

n

n

-tuples of complex numbers

(a_1,..., a_n)

(x+a_1)(x+a_2)\cdots (x+a_n)=x^n+\binom{n}{1}a_1 x^{n-1}+\binom{n}{2}a_2^2 x^{n-2}+\cdots +\binom{n}{n-1} a_{n-1}^{n-1}+\binom{n}{n}a_n^n.

Proposed by USJL.

1

Order is inverted with inverses

p

be an arbitrary odd prime and

\sigma(n)

1 \le n \le p-1

denote the inverse of

n \pmod p

. Show that the number of pairs

(a,b) \in \{1,2,\cdots,p-1\}^2

a<b

\sigma(a) > \sigma(b)

\left \lfloor \left(\frac{p-1}{4}\right)^2 \right \rfloor

usjl
Note: Partial credits may be awarded if the

4

in the statement is replaced with some larger constant

1

IMOC 2021 N10

A prime is called perfect if there is a permutation

a_1, a_2, \cdots, a_{\frac{p-1}{2}}, b_1, b_2, \cdots, b_{\frac{p-1}{2}}

1, 2, \cdots, p-1

b_i \equiv a_i + \frac{1}{a_i} \pmod p

1 \le i \le \frac{p-1}{2}

. Show that there are infinitely many primes that are not perfect.
Proposed By - CSJL

1

Cool problem based on smallest prime factor

Show that for any two distinct odd primes

p, q

, there exists a positive integer

n

\{d(n), d(n + 2) \} = \{p, q\}

d(n)

is the smallest prime factor of

n

.
Proposed By - ltf0501

1

Functional Equation using number of divisors of n

Find all integer-valued polynomials

f, g : \mathbb{N} \rightarrow \mathbb{N} \text{ such that} \; \forall \; x \in \mathbb{N}, \tau (f(x)) = g(x)

holds for all positive integer

x

\tau (x)

is the number of positive factors of

x

Proposed By - ckliao914

1

Partition into sets with equal sum of powers in F_p

p

be a given odd prime. Find the largest integer

k'

such that it is possible to partition

\{1,2,\cdots,p-1\}

X,Y

such that for any

k

0 \le k \le k'

,

\sum_{a \in X}a^k \equiv \sum_{b \in Y}b^k \pmod p

1

Finite set ensures every number written as sum of powers

Find all pairs of positive integers

(a,b)

such that there exists a finite set

S

satisfying that any positive integer can be written in the form

n = x^a + y^b + s

x,y

are nonnegative integers and

s \in S

1

Integers dividing sum of its neighbours.

m \geq 3

positive integers, not necessarily distinct, that are arranged in a circle so that any positive integer divides the sum of its neighbours. Show that if there is exactly one

1

, then for any positive integer

n

, there are at most

\phi(n)

n

.
Proposed By- (usjl, adapted from 2014 Taiwan TST)

1

Cool exponential diaphontine has no solutions

Show that there do not exist positive integers

x,y,z

x^x + y^y = 9^z

1

Bushy and Jumpy return with 2021 walnuts!

Two squirrels, Bushy and Jumpy, have collected

2021

walnuts for the winter. Jumpy numbers the walnuts from 1 through

2021

2021

little holes in a circular pattern in the ground around their favourite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts, and Bushy decides to interfere with Jumpy. The two take turns to reorder the walnuts. Each time, Bushy chooses

1232

walnuts and reorders them and then Jumpy chooses

n

walnuts to reorder. Find the least positive integer

n

such that whatever Bushy does, Jumpy can ensure that the

i

th hole from the left has the

i

th walnut
Ift0501

1

Finding best possible values of grids

m \times n

grid, each square is either filled or not filled. For each square, its value is defined as

0

if it is filled and is defined as the number of neighbouring filled cells if it is not filled. Here, two squares are neighbouring if they share a common vertex or side. Let

f(m,n)

be the largest total value of squares in the grid. Determine the minimal real constant

C

\frac{f(m,n)}{mn} \le C

holds for any positive integers

m,n

1

Maximum good numbers in a circle

1,2,\cdots,2021

are arranged in a circle. For any

1 \le i \le 2021

i,i+1,i+2

are three consecutive numbers in some order such that

i+1

is not in the middle, then

i

is said to be a good number. Indices are taken mod

2021

. What is the maximum possible number of good numbers?
CSJL

1

Minimum vertices in a graph with 100 shortest paths

In a simple graph, there exist two vertices

A,B

such that there are exactly

100

shortest paths from

A

B

. Find the minimum number of edges in the graph.
CSJL

1

Tiling grid with pentominoes

Find all positive integers

m,n

m \times n

grid can be tiled with figures formed by deleting one of the corners of a

2 \times 3

1

Tiling the plane with (n)guns

Given a positive integer

n

n

2n

-mino that is formed by putting a

1 \times n

n \times 1

grid side by side so that one of the corner unit squares of the first grid is next to one of the corner unit squares of the second grid. Find the minimum possible

k

such that it is possible to color the infinite planar grid with

k

colors such that any

n

-gun cannot cover two different squares with the same color.
Itf0501

1

Two players try to keep graph disconnected

Two people play a game on a graph with

2022

points. Initially, there are no edges in the graph. They take turns and connect two non-neighbouring vertices with an edge. Whoever makes the graph connected loses. Which player has a winning strategy?
ST, danny2915

1

Drunken man is expected to walk integer number of steps

A drunken person walks randomly on a tree. Each time, he chooses uniformly at random a neighbouring node and walks there. Show that wherever his starting point and goal are, the expected number of steps the person takes to reach the goal is always an integer.
houkai

1

A House graph with equal degrees

There is a city with many houses, where the houses are connected by some two-way roads. It is known that for any two houses

A,B

, there is exactly one house

C

A,B

are connected to

C

. Show that for any two houses not connected directly by a road, they have the same number of roads adjacent to them.
ST

1

Find all real numbers

Find all real numbers x that satisfies

\sqrt{\sqrt{x-\frac{1}{x}}+\sqrt{1-\frac{1}{x}}-\frac{1}{\sqrt{x-\frac{1}{x}}+\sqrt{1-\frac{1}{x}}}}+\sqrt{1-\frac{1}{\sqrt{x-\frac{1}{x}}+\sqrt{1-\frac{1}{x}}}}=x.

[url=https://artofproblemsolving.com/community/c6h2645263p22889979]2021 IMOC Problems

1

A inequality

For any real numbers

x, y, z

xyz + x + y + z = 4,

(yz + 6)^2 + (zx + 6)^2 + (xy + 6)^2 \geq 8 (xyz + 5).

1

Inequality with some sums

n

be some positive integer and

a_1 , a_2 , \dots , a_n

be real numbers. Denote

S_0 = \sum_{i=1}^{n} a_i^2 , \hspace{1cm} S_1 = \sum_{i=1}^{n} a_ia_{i+1} , \hspace{1cm} S_2 = \sum_{i=1}^{n} a_ia_{i+2},

a_{n+1} = a_1

a_{n+2} = a_2.

S_0 - S_1 \geq 0

3

is the minimum value of

C

such that for any

n

a_1 , a_2 , \dots , a_n,

C(S_0 - S_1) \geq S_1 - S_2

1

A nice sum

For a given positive integer

n,

\sum_{k=0}^{n} \left(\frac{\binom{n}{k} \cdot (-1)^k}{(n+1-k)^2} - \frac{(-1)^n}{(k+1)(n+1)}\right).

1

Hard Inequality with reals

n \geq 2

x_1 , x_2 , \dots , x_n.

\prod_{1\leq i < j \leq n} (x_i - x_j)^2 \leq \prod_{i=0}^{n-1} \left(\sum_{j=1}^{n} x_j^{2i}\right)

and find all the

(x_1 , x_2 , \dots , x_n)

where the equality holds.

1

Nice natural FE with an inequality

Find all functions

f : \mathbb{N} \to \mathbb{N}

f(x) + yf(f(x)) < x(1 + f(y)) + 2021

holds for all positive integers

x,y.

1

Another Inequality

For any positive reals

a,b,c,d

a^2 + b^2 + c^2 + d^2 = 4,

\frac{a^3}{a+b} + \frac{b^3}{b+c} + \frac{c^3}{c+d} + \frac{d^3}{d+a} + 4abcd \leq 6.

1

A hard ineq, given that xyz + xy + yz + zx = 4

For any positive reals

x

y

z

xyz + xy + yz + zx = 4

\sqrt{\frac{xy+x+y}{z}}+\sqrt{\frac{yz+y+z}{x}}+\sqrt{\frac{zx+z+x}{y}}\geq 3\sqrt{\frac{3(x+2)(y+2)(z+2)}{(2x + 1)(2y + 1)(2z + 1). }}

1

A tringle formed by 3 lines is tangent to the incircle

The incircle of

\triangle ABC

BC

CA

AB

D

E

F

, respectively. The projections of

B

C

AD

U

V

, respectively; the projections of

C

A

BE

W

X

, respectively; and the projections of

A

B

CF

Y

Z

, respectively. Show that the circumcircle of the triangle formed by

UX

VY

WZ

is tangent to the incircle of

\triangle ABC

1

Show that (IDP) and (IHX) are tangent to each other

O

I

be the circumcenter and the incenter of triangle

ABC

, respectively, and let the incircle tangents

BC

D

. Furthermore, suppose that

H

is the orthocenter of triangle

BIC

N

is the midpoint of the arc

BAC

X

is the intersection of

OI

NH

P

is the reflection of

A

with respect to

OI

\odot(IDP)

\odot(IHX)

are tangent to each other.

1

Prove that AY is tangent to (AEF)

P

be an arbitrary interior point of

\triangle ABC

AP

BP

CP

BC

CA

AB

D

E

F

, respectively. Suppose that

M

be the midpoint of

BC

\odot(AEF)

\odot(ABC)

S

SD

\odot(ABC)

X

XM

\odot(ABC)

Y

AY

\odot(AEF)

1

Incenter, excenter problem show that two circles are tangent

Let the incenter and the

A

\triangle ABC

I

I_A

, respectively. Let

BI

AC

E

CI

AB

F

. Suppose that the reflections of

I

with respect to

EF

FI_A

EI_A

X

Y

Z

, respectively. Show that

\odot(XYZ)

\odot(ABC)

are tangent to each other.

1

Incircle related collinearity

The incircle of triangle

ABC

BC

CA

AB

D

E

F

, respectively. Let the tangents of

E

F

with respect to

\odot(AEF)

P

X

BC

EF

DP

AX

are concurrent. Define

Q

Y

R

Z

similarly. Show that

X

Y

Z

1

Show that AB, CM, PQ are concurrent

\Omega

be the circumcircle of triangle

ABC

X

is a point on the segment

AB

XB=XC

, and the angle bisector of

\angle BAC

BC

\Omega

D

M

, respectively. If

P

BC

AP

\Omega

Q

DX

CQ

\Omega

AB

CM

PQ

are concurrent.

1

Radical axis perpendicular to OI

The incircle of a cyclic quadrilateral

ABCD

tangents the four sides at

E

F

G

H

in counterclockwise order. Let

I

be the incenter and

O

be the circumcenter of

ABCD

. Show that the line connecting the centers of

\odot(OEG)

\odot(OFH)

is perpendicular to

OI

1

Prove that XY passes through a fixed point

D

be a point on the side

AC

ABC

. Suppose that the incircle of triangle

BCD

BD

CD

X

Y

, respectively. Show that

XY

passes through a fixed point when

D

is moving on the side

AC

1

Incenter geo, prove that AR is parallel to BC

I

be the incenter of the acute triangle

\triangle ABC

BI

CI

intersect the altitude of

\triangle ABC

A

U

V

, respectively. The circle with

AI

as a diameter intersects

\odot(ABC)

T

\odot(TUV)

intersects the segment

BC

\odot(ABC)

P

Q

, respectively. Let

R

be another intersection of

PQ

\odot(ABC)

AR\parallel BC

1

Midline and tangent related geo, equal angles wanted

Let the midline of

\triangle ABC

BC

intersect the circumcircle

\Gamma

\triangle ABC

P

Q

, and the tangent of

\Gamma

A

BC

T

\measuredangle BTQ = \measuredangle PTA

1

Prove that three lines intersect at a point

\overline{BE}

\overline{CF}

be altitudes of triangle

ABC

D

be the antipodal point of

A

on the circumcircle of

ABC

\overleftrightarrow{DE}

\overleftrightarrow{DF}

\odot(ABC)

Y

Z

, respectively. Show that

\overleftrightarrow{YZ}

\overleftrightarrow{EF}

\overleftrightarrow{BC}

intersect at a point.

1

Function over reals

Find all functions f : R-->R such that f (f (x) + y^2) = x −1 + (y + 1)f (y) holds for all real numbers x, y