HMIC 2015

Let $S$ be the set of positive integers $n$ such that the inequality

$$\phi(n) \cdot \tau(n) \geq \sqrt{\frac{n^{3}}{3}}$$

holds, where $\phi(n)$ is the number of positive integers $k \leq n$ that are relatively prime to $n$, and $\tau(n)$ is the number of positive divisors of $n$. Prove that $S$ is finite.

Let $m, n$ be positive integers with $m \geq n$. Let $S$ be the set of pairs $(a, b)$ of relatively prime positive integers such that $a, b \leq m$ and $a+b>m$.

For each pair $(a, b) \in S$, consider the nonnegative integer solution $(u, v)$ to the equation $a u-b v=n$ chosen with $v \geq 0$ minimal, and let $I(a, b)$ denote the (open) interval $(v / a, u / b)$. Prove that $I(a, b) \subseteq(0,1)$ for every $(a, b) \in S$, and that any fixed irrational number $\alpha \in(0,1)$ lies in $I(a, b)$ for exactly $n$ distinct pairs $(a, b) \in S$.

Let $M$ be a $2014 \times 2014$ invertible matrix, and let $\mathcal{F}(M)$ denote the set of matrices whose rows are a permutation of the rows of $M$. Find the number of matrices $F \in \mathcal{F}(M)$ such that $\operatorname{det}(M+F) \neq 0$.

Prove that there exists a positive integer $N$ such that for any positive integer $n \geq N$, there are at least 2015 non-empty subsets $S$ of $\left\{n^{2}+1, n^{2}+2, \ldots, n^{2}+3 n\right\}$ with the property that the product of the elements of $S$ is a perfect square.

Let $\omega=e^{2 \pi i / 5}$ be a primitive fifth root of unity. Prove that there do not exist integers $a, b, c, d, k$ with $k>1$ such that

$$\left(a+b \omega+c \omega^{2}+d \omega^{3}\right)^{k}=1+\omega$$