Well, actually this is the only problem from the USA TST 2005 that I know.

May I ask what a unitary polynomial is?

Its leading coefficient is 1. That is, a polynomial of the form $ X^n+a_{n-1} X^{n-1}+...$.

can you post your solution harazi?this problem is really interesting

Probability P(n) equal to $P(n)=\prod_{p\le n}(1-\frac{1}{p^{p}})$, were p primes less or equal n. For example P(1)=1,P(2)=0.75, $P(3)=\frac{13}{18}$, e.tc.

Could you post your solution?

Here's a solution. The latter part is a bit messy though. Suppose $ P(x)$ is a non-special polynomial. Then for some $ k$, we have $ (P(x), k) > 1$, for all integer $ x$, with finitely many exceptions. Let $ p_{1}, p_{2} ... p_{t}$ be the prime factors of $ k$. Then, for any $ x$, at least one of the following is true: $ p_{1} | P(x) ; p_{2} | P(x) ; ... p_{t} | P(x)$. Consider the equation $ P(x) \equiv 0 (mod p_{i})$. The solution set of this equation is: $ x \equiv i_{0}, i_{1} ... , i_{r} (mod p_{i})$, for some set $ S_{i} = {i_{1} ... i_{r}}$. Suppose for each prime $ p_{i}$, this solution set does not encompass all elements of $ Z_{p_{i}}$. Then for each prime $ p_{i}$, assign to it a number $ q_{i}$, such that $ q_{i}$ is not in $ S_{i}$. Then $ (P(q_{i}), p_{i}) = 1$. Consider the solution to the set of equations $ a \equiv q_{i} (mod p_{i})$, for $ i = 1,2 ... t$ (which exists due to the Chinese Remainder Theorem). Then, we have $ (P(a), k) = 1$. Consider the infinite family $ a_{i} \equiv a (mod k)$. Then $ k | a_{i} - a | P(a_{i}) - P(a)$, so $ (P(a_{i}), k) = 1$, so we can find infinitely many integers $ n$ such that $ (P(n), k) = 1$, which contradicts our choice of $ k$. Thus we have proven that, for any non-special polynomial $ P(x)$, we can associate with it a prime $ p$, so that $ P(x) \equiv 0 (mod p)$, for all integers $ x$. Lemma 1: If $ p$ is a prime, then $ 1^k + 2^k + ... + (p - 1)^k$ is divisible by $ p$, iff $ p - 1 | k$. Proof: If $ p - 1|k$, we have $ i^k \equiv 1 (mod p)$ for $ i = 1, 2 ... p - 1$, so $ 1^k + ... + (p - 1)^k \equiv p - 1 (mod p)$, so it is not divisible by $ p$. Now suppose $ k$ is not divisible by $ p - 1$. Pick a generator $ g$ in $ Z_{p}$. We know that the sets $ {g^1 ... g^{p - 1}}$ and $ {1, 2... p - 1}$ coincide in $ Z_{p}$, so the sets $ (g^k)^1, (g^k)^2 ... (g^k)^{p - 1}$ and $ 1^k, 2^k ... (p - 1)^k$ also coincide in $ Z_{p}$, so $ 1^k + ... + (p - 1)^k \equiv (g^k) ((g^k)^0 + (g^k)^1 + ... + (g^k)^{p - 2}) \equiv (g^k) \frac {(g^k)^{p - 1} - 1}{g^k - 1} \equiv 0 (mod p)$, since $ g^k - 1$ is not $ 0$ in $ Z_{p}$, since $ k$ is not divisible by $ p$. Thus lemma is proven. Lemma 2: Suppose $ Q(x)$ is an integer polynomial of degree $ p - 2$, where $ p$ is an odd prime. If $ p | Q(x)$ for all $ x$ such that $ (p,x) = 1$, then all coefficients of $ Q(x)$ are divisible by $ p$. Proof: Let $ Q(x) = a_{0} + a_{1} x + ... + a_{p - 2} x^{p - 2}$ Working in $ Z_{p}$, we have $ p | a_{0} + u a_{1} + u^2 a_{2} + ... + u^{p - 2} a_{p - 2}$, for $ u = 1, 2, ... p - 1$. Call this equation (U). To prove that $ p | a_{i}$, it suffices to prove $ p | v a_{i}$ for some $ v$ such that $ (p,v) = 1$. Thus it would be sufficient, in order to prove $ p | a_{k}$, to find some integers $ t_{1,k}, t_{2,k} ... t_{p - 1,k}$, so that $ t_{1,k} * (1) + t_{2,k} * (2) + ... + t_{p - 1,k}* (P - 1) \equiv v a_{i} (mod p)$, for some $ v$ such that $ (v,p) = 1$. (Recall that (1), (2) .. (P-1) are equations of the form p | ... ). If this is true, since $ 0 \equiv t_{1,k} * (1) + t_{2,k} * (2) + ... + t_{p - 1,k}* (P - 1) \equiv v a_{i} (mod p)$ , it would follow that $ p | a_{i}$. Now it remains to find $ t_{i,k}$ so that $ t_{1,k} * (1) + t_{2,k} * (2) + ... + t_{p - 1,k}* (P - 1) \equiv v a_{i} (mod p)$ - but this is equivalent to find $ t_{i,k}$ so that $ p | 1^s t_{1,k} + 2^s t_{2,k} + ... + (p - 1)^s t_{p - 1,k}$, for all $ s = 0,1,2 ... p - 2$ except $ k$. From Lemma 1, it's not hard to see that $ t_{i,k} = i^{p - 1 - k}$ satisfies all these conditions: so we have found our numbers $ t_{i,j}$, and consequently proved that $ p | a_{i}$, which in turns prove Lemma 2. Let $ P(x) = x^n + a_{n - 1} x^{n - 1} + ... + a_{1} x + a_{0}$, and $ P(x)$ is not special, with respect to a prime $ p$. Since $ P(p) \equiv 0 (mod p)$, we have $ a_{0} \equiv 0 (mod p)$. Now choose $ x$, so that $ (p,x) = 1$. By Fermat's Little Theorem, $ x^{r(p - 1) + s} \equiv x^{s} (mod p)$, for integer $ r$. So we have $ P(x) \equiv Q(x) (mod p)$, where $ Q(x) = b_{0} + b_{1} x + ... + b_{p - 2} x^{p - 2}$, and $ b_{0} = a_{0} + a_{p - 1} + a_{2p - 2} + ...$, $ b_{1} = a_{1} + a_{p} + ..., .... b_{p - 2} = a_{p - 2} + a_{2p - 3} + ...$, where $ a_{n} = 1$. From Lemma 2, we have: $ p | b_{0}, b_{1} ... b_{p - 2}$, so $ p | a_{0} + a_{p - 1} + ...$, $ p | a_{1} + a_{p} + ...$, ... $ p |a_{p - 2} + a_{2p - 3} + ...$ and also, $ p | a_{0}$ from before. By backtracking our steps, we can see that these $ p$ conditions are equivalent to the polynomial $ P(x)$ being non-special. Lets do the easy part first: the upper bound. We shall prove that exactly $ 25$ percent of all such polynomials are 'non-special', with respect to the prime $ 2$. The condition for a prime being special with respect to $ 2$ is fairly simple: $ 2 | a_{0}$, $ 2 | a_{1} + a_{2} + ... + a_{n - 1} + 1$ (since coefficient of $ x^n$ is $ 1$). To prove that $ 25% $ of all sets $ {a_{0} ... a_{n - 1}}$, with $ 1 \leq a_{i} \leq n!$, first note since $ n!$ is even, exactly half of all sets satisfy the condition that $ 2|a_{0}$. Of these sets, we can easily set up a bijection between between the sets satisfying $ 2 | a_{1} + a_{2} ... + a_{n - 1} + 1$ and those satisfying $ 2 | a_{1} + .. + a_{n - 1}$: biject any set $ {x_{1} ... x_{n - 1)}}$ to the set $ {y_{1} ... x_{n - 1}}$, where for each $ x_{1}$ we find the number $ y_{1}$ so that $ (x_{1}, y_{1})$ is one of the following sets: $ (1,2), (3,4) ... (n! - 1, n!)$. Lemma 3: Suppose we select $ c$ numbers from the set $ {1, 2 ... tp + k}$ where $ 0 \leq k \leq p - 1$. The probability that the sum of these numbers is equal to $ d (mod p)$, for some integer $ d$, is at most $ \frac {t + 1}{tp + k}$. Proof: Let $ f(c, d)$ be the number of ways of selecting $ c$ numbers (one number may be used more than once), from the set $ {1,2 .. tp + k}$, which have a sum equal to $ d (mod p)$. We want to prove that $ f(c,d) \leq (t + 1)(tp + k)^{c - 1}$ (since in total there are $ (tp + k)^{c}$ such sets). Let's prove the result by induction on $ c$. For $ c = 1$, it's easy to see there's at most $ t + 1$ different ways of selecting $ 1$ number that is equal to $ d (mod p)$. Suppose it is true for $ k = c - 1$. The number of ways of having a set with $ c$ numbers, with the first one being $ r (mod p)$, so that they sum to $ d (mod p)$, is equal to $ f(c - 1, d - r)$. Since there are $ t + 1$ numbers in $ {1,2 ... tp + k}$ equaling $ i (mod p)$, for $ 1 \leq i \leq k$, and $ t$ such numbers equaling $ j (mod p)$ for $ k + 1 \leq j \leq p$, we have the recurrence $ f(c,d) = (t + 1) f(c - 1, d - 1) + (t + 1) f(c - 1, d - 2) + ... + (t + 1) f(c - 1, d - k) + t f(c - 1, d - k - 1) + ... + t f (c - 1,d)$, from which we immediately get our inequality $ f(c,d) \leq (t + 1)(tp + k)^{c - 1}$, using the induction assumption. This proves Lemma 3. Continuing from before, $ P(x)$ is not special with respect to prime $ p$ iff: $ p | a_{0} + a_{p - 1} + ...$, $ p | a_{1} + a_{p} + ...$, ... $ p |a_{p - 2} + a_{2p - 3} + ...$ and $ p | a_{0}$. If $ p \leq n$, then $ p | n!$; if we let $ Pr(X) =$ probability of an event $ X$ occuring (not to confuse it with the polynomial $ P(x)$), we can see that the probability of any of the $ p$ conditions necessary for $ P(x)$ not to be special, with respect to $ p$, is the probability of a set of some $ c$ integers from $ {1,2 ... n!}$ having sum equal to $ 0 (mod p)$; by using the same bijection method with which we proved that $ 25$ percent of all our polynomials are not special with respect to the prime $ 2$, we can see that the probability of any of the $ p$ conditions to be true, is exactly $ \frac {1}{p}$. Thus the probability, that all of those $ p$ conditions are true, is equal to $ \frac {1}{p^p}$, for a prime $ p \leq n$ (since the conditions are mutually indepedent, we can multiply the probabilities). For a prime $ p$, with $ n < p < n!$, the same method fails to work, since the probability maybe slightly more than $ \frac {1}{p}$ for some of the individual conditions to work (since $ p$ no longer divides $ n!$, the same bijection method fails to work). So instead, we now rely on the crude estimate that Lemma 3 provides. We now have, that the probability of any of the $ p$ conditions is true, is at most $ \frac {t_{p} + 1}{tp + k}$, where $ t_{p}p + k = n!$ (since we seek to find to a set, that has sum of elements equal to $ 0 (mod p)$, or $ - 1 (mod p)$ - in the case where the term $ a_{n} = 1$ occurs, so Lemma 3 is directly applicable). However, the probability of the first condition, $ p |a_{0}$ occurs is clearly less than $ \frac {1}{p}$, so the probability of $ P(x)$ being not-special with respect to $ p$, is at most $ \frac {(t_{p} + 1)^{p - 1}}{p(n!)^{p - 1}}$. Clearly, the probability of a polynomial being not-special, is at most the sum of the probabilities that the polynomial is not special with respect to each prime, that is smaller than $ n!$. It suffices to prove this number is less than $ 0.29$, i.e. $ \sum_{p\le n} \frac {1}{p^p} + \sum_{p > n} \frac {(t_{p} + 1)^{p - 1}}{p(n!)^{p - 1}} < 0.29$. For $ n = 2$, we just write out the $ 4$ possible polynomials and find out $ x^2 + x + 2$ is the only non-special one; for $ n = 3$ we verify the above inequality directly (and it is incredibly tight); for $ n = 4$ a method very similar to the below works, and for $ n \ge 5$ the following method works to kill that last inequality: If $ p > n$, since $ tp + k = n!$, and $ 0 \le k \le p - 1$, we have $ t + 1 \le (n - 1)!$, so $ \frac {t + 1}{n!} < \frac {1}{n}$. So: $ \sum_{p > n} \frac {(t_{p} + 1)^{p - 1}}{p(n!)^{p - 1}} < \sum_{p > n} \frac {1}{p n^{p - 1}} < \sum_{n + 1\le m\le n!} \frac {1}{(n + 1)n^{m - 1}} < \frac {1}{(n + 1)n^n} \sum_{m \ge 1} (\frac {1}{n})^m = \frac {1}{(n + 1)n^n} \frac {1}{1 - \frac {1}{n}} < \frac {1}{n^n}$, so since $ n \ge 5$, $ \sum_{p\le n} \frac {1}{p^p} + \sum_{p > n} \frac {(t_{p} + 1)^{p - 1}}{p(n!)^{p - 1}} < \sum_{p \le n} \frac {1}{p^p} + \frac {1}{n^n} < \frac {1}{2^2} + \frac {1}{3^3} + \frac {1}{5^5} + \sum_{n \ge 5} \frac {1}{n^5} < \frac {1}{2^2} + \frac {1}{3^3} + \frac {1}{5^5} + 0.002 < 0.29$. Note that $ \sum_{n \ge 5} \frac {1}{n^5} < 0.02$, using the inequality $ \frac {1}{n^5} < \frac {1}{20 n^2} - \frac {1}{20 (n + 1)^2}$ (which can be proven easily by computation), and using telescoping sums.

epitomy01's solution is very long and rather hard to read... I've compiled a more readable and shorter solution. Define a polynomial to be $p$-special if $f$ does not vanish modulo $p$. Then a polynomial is special iff it is special with respect to every prime. Lemma 1: If $\deg f < p$, then $f$ does not vanish modulo $p$. Proof: This is trivial and well-known. $f$ has at most $\deg f$ roots over $\mathbb{F}_p$ as $\mathbb{F}_p$ is a field, and the result follows. $\square$ Hence it follows for the selection of polynomials in the problem, it suffices to consider whether or not polynomials are $p$-special where $p$ is a prime $\le n$. Lemma 2: Given a random polynomial specified in the problem, the probability $f$ is $p$-special is $1 - \frac{1}{p^p}$. Proof: Given a random polynomial $f$, reduce it modulo $p$ and then modulo $x^p - x$. Clearly this does not alter whether or not the polynomial vanishes modulo $p$. Hence it suffices to consider the $p^{p}$ polynomials $a_0 + a_1x + ... + a_{p-1}x^{p-1}$ where $0 \le a_i \le p-1$ (remark each of them corresponds to $\frac{n!^{n!}}{p^p}$ polynomials before reducing them). Only $1$ of them vanishes modulo $p$ , hence it follows the probability a polynomial vanishes modulo $p$ is $1 - \frac{1}{p^p}$ and we are done. $\square$ Remark that a polynomial being $p$-special and $q$-special are independent events when $p,q$ are distinct primes by CRT. Hence it follows the probability a random polynomial is special is $\prod_{p \le n} \left (1 - \frac{1}{p^p} \right )$. Now we prove the theorem. As $1 - \frac{1}{2^2} = 0.75$, it follows $\prod_{p \le n} \left (1 - \frac{1}{p^p} \right ) \le 0.75$. Thus it suffices to show $\prod_{p \le n} \left (1 - \frac{1}{p^p} \right ) \ge 0.71$, or $\prod_{p} \left (1 - \frac{1}{p^p} \right ) \ge 0.71$. Remark that for all $k$, $\prod_{k \le p} \left (1 - \frac{1}{p^p} \right ) > \frac{1}{\zeta(k)}$ by the Euler Product Formula. Now, observe: $\prod_{p} \left (1 - \frac{1}{p^p} \right ) > \frac{\left ( 1 - \frac{1}{2^2} \right ) \left ( 1 - \frac{1}{3^3} \right ) \left ( 1 - \frac{1}{5^5} \right ) \left ( 1 - \frac{1}{7^7} \right )}{\zeta(8)} > \frac{0.72}{\zeta(8)}$ But: $\zeta(8) = (-1)^9 \cdot \frac{(2\pi)^8B_8}{2 \cdot 16!} = \frac{\pi^8}{9450}$ because by a little algebra $B_8 = \frac{-1}{30}$ It's not hard to estimate then that $\zeta(8) < 1.005$, hence $\prod_{p} \left (1 - \frac{1}{p^p} \right ) > \frac{0.72}{1.05} > 0.71$, as desired so we are done. $\square$ (Bounding $\zeta(n)$ without using the exact value while still getting a good enough value is possible, but this route for the last few steps of bounding is pretty mindless and just number crunching horror)

Sorry to bump this, but I was going back through old TSTs to practice for the upcoming USAMO, and I randomly picked the 2005 one to do. Unfortunately, the problem statement here is just unclear enough that I can't actually do the problem without some clarification. Specifically, the statement is clearly false if $n = 1$, so is the restriction on $n$ that $n \ge 2$, or something else? Additionally, the definition of special starts with a polynomial $g$ and then references a polynomial $f$; I assume these are supposed to be the same? Finally, I know someone clarified this in the comments, but a rewording of this problem that avoids the word "unitary," instead using "monic" or even "with leading coefficient 1" would be great. If anyone has access to the original statement of this problem, please clarify these things and maybe even repost it so other people who use this for practice don't have the same problem. EDIT: Also, hide tags for the solutions. Those would be nice.

Rebump. I realize it's possible nobody has the old TST, but I'm hoping somebody will give me a usable version of the problem soon so I can get to work on it.

Suppose $n \geq 2$. By CRT it suffices to look at primes only, by periodicity it suffices to find a single integer value $m$ such that $p \nmid f(m)$. In general, by Lagrange interpolation there is a single polynomial of degree at most $p-1$ which is always $0 \pmod{p}$, namely the zero polynomial, so we can ignore $p>n$. For primes $p \leq n$, arbitrarily select the coefficients of every term with degree at least $p$, leaving $p$ undetermined coefficients, and call this polynomial $f_0(x)$. Then by Lagrange interpolation, in $\mathbb{F}_p$ there always exists exactly one polynomial $f_1(x)$ with degree at most $p-1$ such that $f_0(x)+f_1(x)=0$ for all $x \in \mathbb{F}_p$, so the proportion of the remaining $(n!)^{p}$ choices for the rest of the coefficients that results in a polynomial not being special is exactly $p^{-p}$. By only looking at $p=2$ we easily get the upper bound. For the lower bound, summing over all $p$ we have a probability of at most $\sum_{p \text{ prime}} p^{-p}$ that a polynomial is not special. However, $$\sum_{p\text{ prime}} p^{-p} \leq -1-4^{-4}+\sum_{n=1}^\infty n^{-n} \approx -1-4^{-4}+1.291286=.28737975,$$which is small enough. $\blacksquare$