MathDB

1

2022-tuple operations

s

integer-valued

2022

-tuples on a blackboard. After doing that, she can take any two (not necessarily distinct) tuples

\mathbf{v}=(v_1,\ldots,v_{2022})

and

\mathbf{w}=(w_1,\ldots,w_{2022})

that she has already written, and apply one of the following operations to obtain a new tuple: \begin{align*} \mathbf{v}+\mathbf{w}&=(v_1+w_1,\ldots,v_{2022}+w_{2022}) \\ \mathbf{v} \lor \mathbf{w}&=(\max(v_1,w_1),\ldots,\max(v_{2022},w_{2022})) \end{align*} and then write this tuple on the blackboard.
It turns out that, in this way, Lucy can write any integer-valued

2022

-tuple on the blackboard after finitely many steps. What is the smallest possible number

s

of tuples that she initially wrote?

C5

1

Number of functions satisfying sum inequality

Let

m,n \geqslant 2

be integers, let

X

be a set with

n

elements, and let

X_1,X_2,\ldots,X_m

be pairwise distinct non-empty, not necessary disjoint subset of

X

. A function

f \colon X \to \{1,2,\ldots,n+1\}

is called nice if there exists an index

k

such that \sum_{x \in X_k} f(x)>\sum_{x \in X_i} f(x) \text{for all } i \ne k. Prove that the number of nice functions is at least

n^n

.

N6

1

Prime factorization functions have even sum

Let

Q

be a set of prime numbers, not necessarily finite. For a positive integer

n

consider its prime factorization: define

p(n)

to be the sum of all the exponents and

q(n)

to be the sum of the exponents corresponding only to primes in

Q

. A positive integer

n

is called special if

p(n)+p(n+1)

and

q(n)+q(n+1)

are both even integers. Prove that there is a constant

c>0

independent of the set

Q

such that for any positive integer

N>100

, the number of special integers in

[1,N]

is at least

cN

.
(For example, if

Q=\{3,7\}

, then

p(42)=3

,

q(42)=2

,

p(63)=3

,

q(63)=3

,

p(2022)=3

,

q(2022)=1

.)

A4

1

Inequality on pairs of variables in [0,1]

Let

n \geqslant 3

be an integer, and let

x_1,x_2,\ldots,x_n

be real numbers in the interval

[0,1]

. Let

s=x_1+x_2+\ldots+x_n

, and assume that

s \geqslant 3

. Prove that there exist integers

i

and

j

with

1 \leqslant i<j \leqslant n

such that

2^{j-i}x_ix_j>2^{s-3}.

A5

1

Pairwise differences form geometric sequence

Find all positive integers

n \geqslant 2

for which there exist

n

real numbers

a_1<\cdots<a_n

and a real number

r>0

such that the

\tfrac{1}{2}n(n-1)

differences

a_j-a_i

for

1 \leqslant i<j \leqslant n

are equal, in some order, to the numbers

r^1,r^2,\ldots,r^{\frac{1}{2}n(n-1)}

.

A8

1

Exponential number of n-sequences

For a positive integer

n

, an

n

-sequence is a sequence

(a_0,\ldots,a_n)

of non-negative integers satisfying the following condition: if

i

and

j

are non-negative integers with

i+j \leqslant n

, then

a_i+a_j \leqslant n

and

a_{a_i+a_j}=a_{i+j}

.
Let

f(n)

be the number of

n

-sequences. Prove that there exist positive real numbers

c_1

,

c_2

, and

\lambda

such that

c_1\lambda^n<f(n)<c_2\lambda^n

for all positive integers

n

.

N2

1

Factorial Divisibility

Find all positive integers

n>2

such that

n! \mid \prod_{ p<q\le n, p,q \, \text{primes}} (p+q)

G7

1

Triangles with same orthocenter and circumcircle

Two triangles

ABC, A’B’C’

have the same orthocenter

H

and the same circumcircle with center

O

. Letting

PQR

be the triangle formed by

AA’, BB’, CC’

, prove that the circumcenter of

PQR

lies on

OH

.

G8

1

Cyclic hexagon with incircles

Let

AA'BCC'B'

be a convex cyclic hexagon such that

AC

is tangent to the incircle of the triangle

A'B'C'

, and

A'C'

is tangent to the incircle of the triangle

ABC

. Let the lines

AB

and

A'B'

meet at

X

and let the lines

BC

and

B'C'

meet at

Y

.
Prove that if

XBYB'

is a convex quadrilateral, then it has an incircle.

G5

1

What happened to geometry

Let

ABC

be a triangle and

\ell_1,\ell_2

be two parallel lines. Let

\ell_i

intersects line

BC,CA,AB

at

X_i,Y_i,Z_i

, respectively. Let

\Delta_i

be the triangle formed by the line passed through

X_i

and perpendicular to

BC

, the line passed through

Y_i

and perpendicular to

CA

, and the line passed through

Z_i

and perpendicular to

AB

. Prove that the circumcircles of

\Delta_1

and

\Delta_2

are tangent.

A2

1

Element sum of k others

Let

k\ge2

be an integer. Find the smallest integer

n \ge k+1

with the property that there exists a set of

n

distinct real numbers such that each of its elements can be written as a sum of

k

other distinct elements of the set.

N8

1

Beautiful Number Theory

Prove that

5^n-3^n

is not divisible by

2^n+65

for any positive integer

n

.

N5

1

How many digits across all multiples of 1829?

For each

1\leq i\leq 9

and

T\in\mathbb N

, define

d_i(T)

to be the total number of times the digit

i

appears when all the multiples of

1829

between

1

and

T

inclusive are written out in base

10

.
Show that there are infinitely many

T\in\mathbb N

such that there are precisely two distinct values among

d_1(T)

,

d_2(T)

,

\dots

,

d_9(T)

.

N3

1

Add d or Divide by a

Let

a > 1

be a positive integer and

d > 1

be a positive integer coprime to

a

. Let

x_1=1

, and for

k\geq 1

, define

x_{k+1} = \begin{cases} x_k + d &\text{if } a \text{ does not divide } x_k \\ x_k/a & \text{if } a \text{ divides } x_k \end{cases}

Find, in terms of

a

and

d

, the greatest positive integer

n

for which there exists an index

k

such that

x_k

is divisible by

a^n

.

A7

1

Digit sums of polynomial outputs

For a positive integer

n

we denote by

s(n)

the sum of the digits of

n

. Let

P(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0

be a polynomial, where

n \geqslant 2

and

a_i

is a positive integer for all

0 \leqslant i \leqslant n-1

. Could it be the case that, for all positive integers

k

,

s(k)

and

s(P(k))

have the same parity?

C1

1

A Sequence of +1&#039;s and -1&#039;s

A

\pm 1

-sequence is a sequence of

2022

numbers

a_1, \ldots, a_{2022},

each equal to either

+1

or

-1

. Determine the largest

C

so that, for any

\pm 1

-sequence, there exists an integer

k

and indices

1 \le t_1 < \ldots < t_k \le 2022

so that

t_{i+1} - t_i \le 2

for all

i

, and

\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.

C6

1

Operations on Pebbles

Let

n

be a positive integer. We start with

n

piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of

n

) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.

N1

1

Three Distinct Divisors Sum to 2022

A number is called Norwegian if it has three distinct positive divisors whose sum is equal to

2022

. Determine the smallest Norwegian number. (Note: The total number of positive divisors of a Norwegian number is allowed to be larger than

3

.)

C4

1

Coins and Children in a Circle

Let

n > 3

be a positive integer. Suppose that

n

children are arranged in a circle, and

n

coins are distributed between them (some children may have no coins). At every step, a child with at least 2 coins may give 1 coin to each of their immediate neighbors on the right and left. Determine all initial distributions of the coins from which it is possible that, after a finite number of steps, each child has exactly one coin.

G2

1

Arc Midpoints Form Cyclic Quadrilateral

In the acute-angled triangle

ABC

, the point

F

is the foot of the altitude from

A

, and

P

is a point on the segment

AF

. The lines through

P

parallel to

AC

and

AB

meet

BC

at

D

and

E

, respectively. Points

X \ne A

and

Y \ne A

lie on the circles

ABD

and

ACE

, respectively, such that

DA = DX

and

EA = EY

. Prove that

B, C, X,

and

Y

are concyclic.

C9

1

why does C shortlist have 9 problems

Let

\mathbb Z_{\ge 0}

be the set of non-negative integers, and let

f:\mathbb Z_{\ge 0}\times \mathbb Z_{\ge 0} \to \mathbb Z_{\ge 0}

be a bijection such that whenever

f(x_1,y_1) > f(x_2, y_2)

, we have

f(x_1+1, y_1) > f(x_2 + 1, y_2)

and

f(x_1, y_1+1) > f(x_2, y_2+1)

.
Let

N

be the number of pairs of integers

(x,y)

with

0\le x,y<100

, such that

f(x,y)

is odd. Find the smallest and largest possible values of

N

.

A6

1

Pathological FE

Let

\mathbb R

be the set of real numbers. We denote by

\mathcal F

the set of all functions

f\colon\mathbb R\to\mathbb R

such that

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

for every

x,y\in\mathbb R

Find all rational numbers

q

such that for every function

f\in\mathcal F

, there exists some

z\in\mathbb R

satisfying

f(z)=qz

.

C3

1

Increments and Decrements in Square Grid

In each square of a garden shaped like a

2022 \times 2022

board, there is initially a tree of height

0

. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn:
[*] The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at most eight) then becomes one unit taller. [*] The lumberjack then chooses four different squares on the board. Each tree of positive height on those squares then becomes one unit shorter.
We say that a tree is majestic if its height is at least

10^6

. Determine the largest

K

such that the gardener can ensure there are eventually

K

majestic trees on the board, no matter how the lumberjack plays.

G4

1

Length Condition on Circumcenter Implies Tangency

Let

ABC

be an acute-angled triangle with

AC > AB

, let

O

be its circumcentre, and let

D

be a point on the segment

BC

. The line through

D

perpendicular to

BC

intersects the lines

AO, AC,

and

AB

at

W, X,

and

Y,

respectively. The circumcircles of triangles

AXY

and

ABC

intersect again at

Z \ne A

. Prove that if

W \ne D

and

OW = OD,

then

DZ

is tangent to the circle

AXY.

A1

1

Weird Sequence

Let

(a_n)_{n\geq 1}

be a sequence of positive real numbers with the property that

(a_{n+1})^2 + a_na_{n+2} \leq a_n + a_{n+2}

for all positive integers

n

. Show that

a_{2022}\leq 1

.

G3

1

Symmetric Tangents Concur on CD

Let

ABCD

be a cyclic quadrilateral. Assume that the points

Q, A, B, P

are collinear in this order, in such a way that the line

AC

is tangent to the circle

ADQ

, and the line

BD

is tangent to the circle

BCP

. Let

M

and

N

be the midpoints of segments

BC

and

AD

, respectively. Prove that the following three lines are concurrent: line

CD

, the tangent of circle

ANQ

at point

A

, and the tangent to circle

BMP

at point

B

.

G6

1

Circumtriangular Hyperbola

Let

ABC

be an acute triangle with altitude

\overline{AH}

, and let

P

be a variable point such that the angle bisectors

k

and

\ell

of

\angle PBC

and

\angle PCB

, respectively, meet on

\overline{AH}

. Let

k

meet

\overline{AC}

at

E

,

\ell

meet

\overline{AB}

at

F

, and

\overline{EF}

meet

\overline{AH}

at

Q

. Prove that as

P

varies, line

PQ

passes through a fixed point.

2022 IMO Shortlist

Subcontests

2022-tuple operations

Number of functions satisfying sum inequality

Prime factorization functions have even sum

Inequality on pairs of variables in [0,1]

Pairwise differences form geometric sequence

Exponential number of n-sequences

Factorial Divisibility

Triangles with same orthocenter and circumcircle

Cyclic hexagon with incircles

What happened to geometry

Element sum of k others

Beautiful Number Theory

How many digits across all multiples of 1829?

Add d or Divide by a

Digit sums of polynomial outputs

A Sequence of +1&#039;s and -1&#039;s

Operations on Pebbles

Three Distinct Divisors Sum to 2022

Coins and Children in a Circle

Arc Midpoints Form Cyclic Quadrilateral

why does C shortlist have 9 problems

Pathological FE

Increments and Decrements in Square Grid

Length Condition on Circumcenter Implies Tangency

Weird Sequence

Symmetric Tangents Concur on CD

Circumtriangular Hyperbola

2022 IMO Shortlist

Subcontests

2022-tuple operations

Number of functions satisfying sum inequality

Prime factorization functions have even sum

Inequality on pairs of variables in [0,1]

Pairwise differences form geometric sequence

Exponential number of n-sequences

Factorial Divisibility

Triangles with same orthocenter and circumcircle

Cyclic hexagon with incircles

What happened to geometry

Element sum of k others

Beautiful Number Theory

How many digits across all multiples of 1829?

Add d or Divide by a

Digit sums of polynomial outputs

A Sequence of +1&amp;#039;s and -1&amp;#039;s

Operations on Pebbles

Three Distinct Divisors Sum to 2022

Coins and Children in a Circle

Arc Midpoints Form Cyclic Quadrilateral

why does C shortlist have 9 problems

Pathological FE

Increments and Decrements in Square Grid

Length Condition on Circumcenter Implies Tangency

Weird Sequence

Symmetric Tangents Concur on CD

Circumtriangular Hyperbola

A Sequence of +1's and -1's