Iranian Mathematical Olympiad

First we claim that for every positive integer $k$, the edges which their numbers are divisible by $k$ form a cluster. Indeed, suppose on the contrary that $S$ is the largest cluster such that the number of its edges is divisible by $k$ and $v \notin S$ is another such edge. Applying problem statement on edge $v$ and edges of cluster we get there exists a larger cluster with number on edges divisible by $k$.

Now suppose that $p \mid \binom{n}{2}$ where $p$ is a prime number. Therefore the edges with numbers divisible by $\frac{1}{p}\binom{n}{2}$ form a cluster and the number of such edges is $p$. So

$$\begin{aligned} p &= \begin{pmatrix} t \\ 2 \end{pmatrix} \Rightarrow 2p = t(t-1) \\ &\Rightarrow \begin{cases} p \mid t \Rightarrow t-1 \mid 2 \Rightarrow t=2 \text{ or } t=3 \Rightarrow t=3, p=3 \\ p \mid t-1 \Rightarrow t \mid 2 \Rightarrow t=1 \text{ or } t=2 \Rightarrow \text{Contradiction!} \end{cases} \end{aligned}$$

Thereby the only prime divisor of $\begin{pmatrix} n \\ 2 \end{pmatrix}$ is three, so $\begin{pmatrix} n \\ 2 \end{pmatrix} = 3^a$ where $a \in \mathbb{N}$. If $a = 1$ and so $n = 3$ and numbers $1,2,3$ satisfies problem statement. If $a > 1$ there exist $9$ multiple of $\frac{1}{9}\begin{pmatrix} n \\ 2 \end{pmatrix}$ among numbers, but $9$ cannot be written in the form $\begin{pmatrix} t \\ 2 \end{pmatrix}$ so for $n > 3$ such numbers do not exist. $\square$