10
$\begingroup$

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).

1 Answers 1