2023 Japan TST

Part of Japan TST

Subcontests

(5)

1

The Kingdom of Moles

The Kingdom of Moles consists of

2023

cities, and there are several tunnels connecting different pairs of cities. Each tunnel allows bidirectional travel, and there is at most one tunnel connecting any two distinct cities. Furthermore, it is possible to travel between any two distinct cities through a combination of several tunnels.
A pair of distinct cities

\{A, B\}

is considered good if it satisfies the following condition for any city

C

A

B

d_{C,A}

be the minimum number of tunnels required to travel from

C

A

d_{C,B}

be the minimum number of tunnels required to travel from

C

B

. For any such pair

\{A, B\}

, it is guaranteed that regardless of the paths

X

Y

chosen to travel from

C

A

d_{C,A}

tunnels) and from

C

B

d_{C,B}

tunnels), respectively,

X

Y

do not share any common tunnel.
Find the second largest possible value for the number of good pairs of cities. Note that the pairs

\{A, B\}

\{B, A\}

are considered the same combination.

1

Japanese Geo

ABC

be an acute triangle and point

P

lies inside the triangle (excluding the vertices on the boundary) such that lines

AP

BC

are not orthogonal. Let

X

Y

be the points symmetric to

P

AB

AC

, respectively, and let

\omega

be the circumcircle of triangle

AXY

Q

lies inside triangle

ABC

(excluding the vertices on the boundary) and satisfies

\angle QBC = \angle CAP

\angle QCB = \angle BAP

AQ

\omega

R

, distinct from

A

Q

. Prove that the circumcircles of triangles

ABC

PQR

\omega

have a common point.

1

Long Long Long Game Again

A and B are playing a game on a blackboard. At the beginning, a positive real number

x

is fixed. First, A chooses a prime number

p

greater than or equal to

7

. Then, B selects non-negative real numbers

r_1

r_2

. A then chooses two integers

s

t

r_1<s<r_1+xp

r_2<t<r_2+xp

, and writes on the blackboard the remainders of

0

s

t

st

when divided by

p

in this order.
After that, A can repeatedly choose one of the following three operations as many times as they like:
[*] Choose an integer

m

1

p-1

inclusive, and replace each of the four numbers on the blackboard with the remainder of adding

m

and then dividing by

p

. [*] Choose an integer

n

2

p-1

inclusive, and replace each of the four numbers on the blackboard with the remainder of multiplying by

n

and then dividing by

p

. [*] Replace each of the four numbers on the blackboard with its remainder when squared and then divided by

p

, but this operation is not allowed if at least one of the four numbers is

0

.
A's objective is to make the numbers on the blackboard become

0

2

3

6

in that order. However, if there are no integers

s

t

r_1<s<r_1+xp

r_2<t<r_2+xp

, then A cannot achieve the objective.
Find the maximum possible value of

x

such that regardless of A's actions, B can always prevent A from achieving the objective.

1

Tiling game again

Consider a tile consisting of

2023

squares arranged as shown in the figure. Place several of these tiles on a

2023\times 2023

grid such that they do not overlap. Find the maximum possible number of tiles that can be placed. Note that the tiles can be rotated but must not extend beyond the grid.

1

GCD and arithmetic sequence

n

be a positive integer with at least

4

positive divisors. Let

d(n)

be the number of positive divisors of

n

. Find all values of

n

for which there exists a sequence of

d(n) - 1

positive integers

a_1

a_2

\dots

a_{d(n)-1}

that forms an arithmetic sequence and satisfies the following condition: for any integers

i

j

1 \leq i < j \leq d(n) - 1

\gcd(a_i , n) \neq \gcd(a_j , n)