MathDB

P7

Part of 2023 China Team Selection Test

Problems(1)

2023 China TST Problem 7

Source: 2023 China TST Problem 7

3/18/2023
Given the integer n≥2n\geq 2 and a integer a{a}, which is coprime with n{n}. A country has n{n} islands D1D_1, D2D_2, ⋯\cdots, DnD_n. For any 1≤i≠j≤n1\leq i\neq j\leq n, there is a one-way ferry DiD_i to DjD_j if and only if ij≡ia(modn)ij\equiv ia\pmod n. A tourist can initially fly to any of the islands, and then he can only take a one-way ferry. What is the maximum number of islands he can visit?
Created by Zhenhua Qu
combinatoricsgraph theoryChina TST