OLYMPIC-REVENGE 2020

Let $n$ be a positive integer and $a_1, a_2, \dots, a_n$ non-zero real numbers. What is the least number of non-zero coefficients that the polynomial $P(x) = (x - a_1)(x - a_2)\cdots(x - a_n)$ can have?

For a positive integer $n$ , we say an $n$ -shuffling is a bijection $\sigma: \{1,2, \dots , n\} \rightarrow \{1,2, \dots , n\}$ such that there exist exactly two elements $i$ of $\{1,2, \dots , n\}$ such that $\sigma(i) \neq i$ .

Fix some three pairwise distinct $n$ -shufflings $\sigma_1,\sigma_2,\sigma_3$ . Let $q$ be any prime, and let $\mathbb{F}_q$ be the integers modulo $q$ . Consider all functions $f:(\mathbb{F}_q^n)^n\to\mathbb{F}_q$ that satisfy, for all integers $i$ with $1 \leq i \leq n$ and all $x_1,\ldots x_{i-1},x_{i+1}, \dots ,x_n, y, z\in\mathbb{F}_q^n$ , $$f(x_1, \ldots ,x_{i-1}, y, x_{i+1}, \ldots , x_n) +f(x_1, \ldots ,x_{i-1}, z, x_{i+1}, \ldots , x_n) = f(x_1, \ldots ,x_{i-1}, y+z, x_{i+1}, \ldots , x_n),$$ and that satisfy, for all $x_1,\ldots,x_n\in\mathbb{F}_q^n$ and all $\sigma\in\{\sigma_1,\sigma_2,\sigma_3\}$ , $$f(x_1,\ldots,x_n)=-f(x_{\sigma(1)},\ldots,x_{\sigma(n)}).$$

For a given tuple $(x_1,\ldots,x_n)\in(\mathbb{F}_q^n)^n$ , let $g(x_1,\ldots,x_n)$ be the number of different values of $f(x_1,\ldots,x_n)$ over all possible functions $f$ satisfying the above conditions.

Pick $(x_1,\ldots,x_n)\in(\mathbb{F}_q^n)^n$ uniformly at random, and let $\varepsilon(q,\sigma_1,\sigma_2,\sigma_3)$ be the expected value of $g(x_1,\ldots,x_n)$ . Finally, let $$\kappa(\sigma_1,\sigma_2,\sigma_3)=-\lim_{q \to \infty}\log_q\left(-\ln\left(\frac{\varepsilon(q,\sigma_1,\sigma_2,\sigma_3)-1}{q-1}\right)\right).$$

Pick three pairwise distinct $n$ -shufflings $\sigma_1,\sigma_2,\sigma_3$ uniformly at random from the set of all $n$ -shufflings. Let $\pi(n)$ denote the expected value of $\kappa(\sigma_1,\sigma_2,\sigma_3)$ . Suppose that $p(x)$ and $q(x)$ are polynomials with real coefficients such that $q(-3) \neq 0$ and such that $\pi(n)=\frac{p(n)}{q(n)}$ for infinitely many positive integers $n$ . Compute $\frac{p\left(-3\right)}{q\left(-3\right)}$ .

Let $ABC$ be a triangle and $\omega$ its circumcircle. Let $D$ and $E$ be the feet of the angle bisectors relative to $B$ and $C$ , respectively. The line $DE$ meets $\omega$ at $F$ and $G$ . Prove that the tangents to $\omega$ through $F$ and $G$ are tangents to the excircle of $\triangle ABC$ opposite to $A$ .

Let $n$ be a positive integer and $A$ a set of integers such that the set $\{x = a + b\ |\ a, b \in A\}$ contains $\{1^2, 2^2, \dots, n^2\}$ . Prove that there is a positive integer $N$ such that if $n \ge N$ , then $|A| > n^{0.666}$ .