Never Perfect Square Permutation Polynomials I had made up this problem a while back, and I think I had a tedious, uninsightful proof. Also, I am not able to reconstruct the proof I had.
Here is the problem:
Let $\displaystyle \pi: \{1,2, \dots, 13\} \to \{1,2,\dots, 13\}$ be a bijection, i.e. it is basically a permutation of the first $\displaystyle 13$ positive integers.
For each such $\displaystyle \pi$ construct the polynomial $\displaystyle P_{\pi}: \mathbb{Z} \to \mathbb{Z}$ such that
$$P_{\pi}(x) = \sum_{j=1}^{13} \ \ \pi(j) \ x^{j-1}$$
Is there some $\displaystyle \pi$ such that for every $\displaystyle n \in \mathbb{Z}$, $\displaystyle P_{\pi}(n)$ is never a perfect square?
I believe it is true that there is such a $\displaystyle \pi$. In fact, I seem to recollect having "proved" that there are at least $7!$ such permutations. 
So the questions are:
a) Is there a "slick" proof of the existence of at least one such $\displaystyle \pi$? (Any proof welcome, though).
b) What if $\displaystyle 13$ is replaced by a generic natural number $\displaystyle M$? Can we give a different (and hopefully simpler) characterization of the $\displaystyle M$ for which such a $\displaystyle \pi$ exists?
Please consider posting an answer even if you don't have an answer for b).
 A: Edit: The original solution was wrong, but fortunately could be fixed.
Given $M$, we find a sufficient condition for a permutation $\pi$ to work. We use the following simple property: $m^2 \pmod{4} \in \{0,1\}$. So if we can force $P_\pi(n) \pmod{4} \in \{2,3\}$, we are done.
There are four cases to consider, according to $n \pmod{4}$. If $n \pmod{4} = 0$ then $$P_\pi(n) \equiv \pi(1) \pmod{4},$$ and so we need $\pi(1) \pmod{4} \in \{2,3\}$. If $n \pmod{4} = 2$ then $$P_\pi(n) \equiv \pi(1) + 2\pi(2) \pmod{4},$$ and so we need $\pi(2)$ to be even. If $n \pmod{4} = 1$ then $$P_\pi(n) \equiv \sum_{i=1}^M \pi(i) = \sum_{i=1}^M i = \frac{M(M+1)}{2} \pmod{4};$$ that happens whenever $M \pmod{8} \in \{2,3,4,5\}$. Finally, if $n \pmod{4} = 2$ then $$P_\pi(n) \equiv \sum_{i=1}^M (-1)^{i+1} \pi(i) \equiv \frac{M(M+1)}{2} + 2\sum_{j=1}^{\lfloor M/2 \rfloor} \pi(2j) \pmod{4}.$$ Thus we need $$\sum_{j=1}^{\lfloor M/2 \rfloor} \pi(2j) \equiv 0 \pmod{2}.$$
Claim: Whenever $M\geq 3$ satisfies $M \pmod{8} \in \{2,3,4,5\}$, we can find such a $\pi$.
Proof: Set $\pi(1) = 3$ and $\pi(2m) = 2m$.
This method of proof can probably be generalized by replacing $4$ with other moduli.
