12th Czech-Polish-Slovak Mathematics Competition

We have $\tau (1)=\phi (1)=1$, that is $n=1$ satisfies the given condition. In the following, we assume $n>1$. For such $n$, clearly $\tau (n)\le n$ and $\phi (n)<n$. This means $n$ cannot be the arithmetic mean of $\tau (n)$ and $\phi (n)$. We are left with two cases.

Case 1: $\tau (n)=\frac{1}{2}(\phi (n)+n)$. Then we have $\tau (n)>\frac{1}{2}n$. For each divisor $d$ of $n$, the number $n/d$ is also the divisor. One of the numbers $d,n/d$ is less or equal $\sqrt{n}$, which means the set $\{1,2,\dots ,\lfloor \sqrt{n}\rfloor \}$ contains at least half of the divisors¹. This clearly implies $\frac{1}{2}\tau (n)\le \sqrt{n}$. We get $$2\sqrt{n}\ge \tau (n)>\frac{1}{2}n\Rightarrow 4n>\frac{1}{4}{n}^2\Rightarrow 16>n.$$ For $1<n<16$, we can easily calculate $\tau (n)$, check the condition $\tau (n)>\frac{1}{2}n$, and calculate $\phi (n)$ in the remaining few cases:

n	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\tau (n)$	2	2	3	2	4	2	4	3	4	2	6	2	4	4
$\tau (n)>1/2n$ ?	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓
$\phi (n)$	1	2	2		2
$\tau (n)=1/2(\phi (n)+n)$ ?	×	×	✓		✓

We have $n=4$ and $n=6$ as solutions.

Case 2: $\phi (n)=\frac{1}{2}(\tau (n)+n)$. We transform this relation into $$\tau (n)=2\phi (n)-n.(1)$$ If $n$ is even, then no even number is relatively prime to $n$, thus $\phi (n)\le \frac{1}{2}n$. But then from (1) we get $\tau (n)\le 0$, which is impossible. Therefore, $n$ must be odd. Then (1) implies $\tau (n)$ must be odd as well, which means $n$ is a perfect square (of an odd number). Write the prime factorization of $n$ in the form $$n=p_1^{2{\alpha }_1}\cdots p_k^{2{\alpha }_k},k\ge 1,p_i\ge 3,{\alpha }_i\ge 1.$$

Applying the well-known formula for $\tau (n)$ and $\phi (n)$, we rewrite (1) as $$\begin{gathered} (2{\alpha }_1+1)\cdots (2{\alpha }_k+1)=2p_1^{2{\alpha }_1-1}(p_1-1)\cdots p_k^{2{\alpha }_k-1}(p_k-1)-p_1^{2{\alpha }_1}\cdots p_k^{2{\alpha }_k}= \\ =p_1^{2{\alpha }_1-1}\cdots p_k^{2{\alpha }_k-1}(2(p_1-1)\cdots (p_k-1)-p_1\cdots p_k). \end{gathered}$$ The right hand side is divisible by $p_1^{2{\alpha }_1-1}\cdots p_k^{2{\alpha }_k-1}$, and so must be the left hand side as well. From this, we obtain $$p_1^{2{\alpha }_1-1}\cdots p_k^{2{\alpha }_k-1}\le (2{\alpha }_1+1)\cdots (2{\alpha }_k+1).(2)$$ However, for every integers $p\ge 3$ and $\alpha \ge 1$, the inequality $p^{2\alpha -1}\ge (2\alpha +1)$ holds, with equality only for $p=3$ and $\alpha =1$. To prove this, we use induction on $\alpha$: The case $\alpha =1$ is trivial (with equality only for $p=3$) and when $\alpha$ increases by 1, the right hand size increases by 2, while the left hand size increases by 1. $$p^{2(\alpha +1)-1}-p^{2\alpha -1}=p^{2\alpha -1}(p^2-1)>2.$$ Therefore, each of the (positive) factors on the left hand side of (2) is greater or equal than the corresponding factor on the right hand side. The only possible way to satisfy (2) is to put $k=1$, $p_1=3$, ${\alpha }_1=1$, that is, $n=9$. Indeed, we have $\tau (9)=3$ and $\phi (9)=6$, thus (1) holds for $n=9$.

Answer. The given condition is fulfilled for $n\in \{1,4,6,9\}$.