IMO Team Selection Test 1

Answer: $n = 1$ and $n = 6$.

We first note that $n = 1$ satisfies.

We now prove that $\beta(n) = \frac{n}{2}$ for $n \ge 2$. Indeed, $\gcd(k, n) = \gcd(k - n, n) = \gcd(n - k, n)$, so $\gcd(k, n) = 1$ if and only if $\gcd(n - k, n) = 1$. This yields a partition of the positive integers $1 \le k \le n - 1$ with $\gcd(k, n) = 1$ into pairs $(k, n - k)$, which have mean $\frac{n}{2}$. For $n \ge 2$, $\gcd(n, n) > 1$, so we see that the average of all the numbers $1 \le k \le n$ with $\gcd(k, n) = 1$ is also equal to $\frac{n}{2}$. The number $\frac{n}{2}$ might have been double counted, but that does not matter since the average is $\frac{n}{2}$.

Prime numbers do not satisfy, because then $\alpha(n) = \frac{n+1}{2}$ and $\beta(n) = \frac{n}{2}$.

Now suppose $d$ is a positive divisor of $n$ with $d$ unequal to $1$ and $n$. Then we have $2 \le d \le \frac{n}{2}$, so $(\frac{n}{2} - d)(d - 2) \ge 0$, so $\frac{n}{2}d + 2d \ge n + d^2$, so $\frac{n}{2} + 2 \ge \frac{n}{d} + d$.

Now suppose $n > 6$ is compound. We can divide the positive divisors of $n$ into pairs $(d, \frac{n}{d})$. The pair $(1, n)$ has average $\frac{n+1}{2}$, all other pairs have average $\frac{\frac{n}{d}+d}{2} \le \frac{\frac{n}{2}+2}{2} < \frac{n-1}{2}$, or it is just the number $\sqrt{n} \le \frac{n}{3} < \frac{n-2}{2}$ (in this case, $n \ge 9$ holds). If $n$ is not the square of a prime number, we have a pair with average $\frac{n+1}{2}$, a pair with average smaller than $\frac{n-1}{2}$, and even possibly more pairs (or a single number) all with average smaller than $\frac{n-1}{2}$, making the total average smaller than $\frac{n}{2}$. If $n$ is the square of a prime number, we find $\alpha(n) = \frac{1+\sqrt{n}+n}{3} < \frac{1+\frac{n-2}{2}+n}{3} = \frac{3n}{6} = \frac{n}{2}$. So $n > 6$ does not satisfy.

Also $n = 4$ does not satisfy, because $\alpha(4) = \frac{1+2+4}{3} = \frac{7}{3}$ while $\beta(4) = \frac{4}{2} = 2$.

Finally, we check that $n = 1$ and $n = 6$ indeed satisfy:

* $n = 1$: We have $\alpha(1) = \beta(1) = 1$.
* $n = 6$: We have $\alpha(6) = \frac{1+2+3+6}{4} = 3$ and $\beta(6) = \frac{1+5}{2} = 3$.

We conclude that $\alpha(n) = \beta(n)$ if and only if $n = 1$ or $n = 6$. $\square$