MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 Added Cebysev example and link to MO69737

I haven't answered either of your questions yet. I see that while I was typing this F.Voloch did answer both. It's somewhat suggestive mysterious that my very different technique yields exactly the same bound; it generalizes to the reduction mod $p$ of moment-generating polynomials of other distributions with tractable orthogonal polynomials. In that setting the bound can actually be sharp. If we use the moments1, though again it might \phantom. 0, \phantom.\frac14, \phantom. 0, \phantom.\frac18, \phantom. 0, \phantom.\frac5{64}, \phantom. 0, \phantom.\frac7{128}, \ldotsof $(2/\pi) \sqrt{1-x^2} \phantom. dx$ on $(-1,1)$, and subtract $2$ from the $x^{p-1}$ coefficient of the resulting polynomial1 + \frac12 \frac{x^2}{2} + \frac12 \cdot \frac34 \frac{x^4}{3} + \frac12 \cdot \frac34 \cdot \frac56 \frac{x^6}{4} + \cdots \pm 2x^{p-1}mod $p$ (which is OK because the argument does not be use this leading coefficient), we get a polynomial with $t$ or $t+1$ roots according as $t$ is even or odd, namely $x=\pm1$ with multiplicity $1$, and each $x$ for which $1-x^2$ is a quadratic residue with multiplicity $2$; and indeed the corresponding orthogonal polynomials, which are Čebyšev polynomials of much interest since it's hard to push the bounds below second kind, are "tractable" for our purpose, but the relevant one $p/2$ U_t$ has simple roots at all other nonzero $x \bmod p$ — and also at $x=0$ when $t$ is odd, which did not happen in Putnam B-6 and explains how an extra root can appear here.

For the actual count must be B-6 polynomials, G.Myerson reports that the paper Voloch cited actually gets a bound $O(p^{2/3})$ on the number of roots mod $p$, which is much smallerlower than $p/2$ but still well above what we expect to be true. Here's some numerical evidencefor the B6 polynomial: the gp code

P.S. This would make another good example for this MO question (#69737: Contest problems with connections to deeper mathematics).
show/hide this revision's text 1

This is quite a coincidence. Some 25+ years ago I observed that a very similar result follows from classical formulas and properties for Laguerre polynomials, i.e. the orthogonal polynomials for the measure $e^{-x}dx$ on $[0,\infty)$, whose moments $k! = \int_0^\infty x^k e^{-x} dx$ are the coefficients of the polynomial in problem B6. I thought at the time that this was a curiosity of very little interest because one expects such a random polynomial to have no more than say $O(\log^2 p)$ roots mod $p$. Now this problem appears on the Putnam exam. I was able to reconstruct and modify my argument to produce this solution, but wondered how anybody would be expected to find that under contest conditions. Your solution is much likelier to be the intended one.

I haven't answered either of your questions yet. I see that while I was typing this F.Voloch did answer both. It's somewhat suggestive that my very different technique yields exactly the same bound; it generalizes to the reduction mod $p$ of moment-generating polynomials of other distributions with tractable orthogonal polynomials, though again it might not be of much interest since it's hard to push the bounds below $p/2$ and the actual count must be much smaller. Here's some evidence for the B6 polynomial: the gp code

B6(p) = poldegree(gcd(Mod(1,p)*(x^p-x), Mod(1,p)*sum(k=0,p-1,x^k*k!)))
forprime(p=3,200,print([p,B6(p)]))

finds only one $p<200$ for which the polynomial has as many as $5$ roots mod $p$, namely $p=151$, and only three each for $4$ roots ($p=37, 97, 167$) or $3$ (these being $53,191,199$).