Just an idea that came to my mind. I think there won't be any. Maybe we could use some arguments about density to prove that $P$ is linear in each variables. Now set $y, z$ to some constant, so that the linear function of $x$ can take a square value..?

In fact, spoiler

.

The following is a reply I wrote up on the day you posted it, but did not bother actually submitting, hoping someone else would beat me to it. Now that the cat is out of the bag ("such a polynomial does exist"), and since no one has posted their solution yet, I figured I might as well... Cute problem, v_Enhance! (By the way, why is it in the Unsolved section?) Perhaps surprisingly, there does exist such a polynomial $P \in \mathbb{Z}[X, Y, Z]$. The key idea: what does the condition "$n$ is not a perfect square" remind you of? Pell's equation, of course! Now I claim that \[P = Z^2(X^2 - ZY^2-1)^2 + Z\] does the trick. If $n$ is not a perfect square, then by "the key idea" (Lagrange's theorem) we may find a pair of positive integers $(x, y) \in \mathbb{N}^2$ such that $x^2 - ny^2 - 1 = 0$, meaning there is a triple of positive integers (namely $(x, y, n)$) for which $P(x, y, n)=n$ (by construction). For the converse, again by the "key idea" we only need to look at those triples $(x, y, z) \in \mathbb{N}^3$ for which $|x^2 - zy^2 - 1| \ge 1$ and now it suffices to note that \begin{align*} (z(x^2 - zy^2 -1))^2 &< P(x,y,z) \\ &< z^2(x^2 - zy^2 -1)^2 + 2z|x^2 - zy^2 -1| + 1 = (z|x^2 - zy^2 -1| + 1)^2, \end{align*} meaning there is no triple $(x, y, z) \in \mathbb{N}^3$ such that $P(x, y, z)$ is a perfect square.

Ha, that's actually a completely different construction than the one I used on the test. We claim that \[ \boxed{P(x,y,z) = \left( 1-2013(z-1)(z-2) \right)\left( (x+y-1)^2 + 2y-2 + z \right)} \]is a solution. We need only consider $z \le 2$ since otherwise $P(x,y,z) < 0$ when $x,y,z \in \mathbb Z^+$. Thus, we can rewrite this as \[ P(x,y,z) = \begin{cases} a^2 + 2b + 1& \text{if } z = 1 \\ a^2 + 2b + 2 & \text{if } z = 2 \end{cases} \]where $a > b \ge 0$ are arbitrary nonnegative integers. Explicitly, $a = x+y-1$ and $b = y-1$. Then $a^2 < P(x,y,z) \le a^2+2(a-1)+2 < (a+1)^2$, but you can attain any value in between such ranges, and so we're done.

How do you think of these constructions?

This was a difficult problem by any standard; it was given only to the "top 18" IMO candidates, and only one student got any points at all. But with that warning... I think the difficulty of this problem comes from the following. 1. If you believe the answer is "no", which is the more natural first guess, you are dead, dead, dead -- any questions? 2. It's very tempting to try number-theoretic methods (for both "yes" and "no"), given the innocuous phrasing of the problem. You can see that my solution involves no NT. 3. You need to be crazy enough to try ad-hoc "programming" to get the polynomial that you want. The actual polynomial is very artificial, and you can only reach such an artificial result by very deliberate effort. If you manage to clear all these hurdles (but that's a huge "if", most people failed to clear the first one) then the problem is not so bad. The idea is "a number is a square iff it is of the form $a^2+b$ for $1 \le b \le 2a$". The $2$ is actually the obstacle here; if we had $a^2 + b$ for $1 \le b < a$, we could just let $a = x+y$, $b=x$, for $x,y \in \mathbb N$. So you need to get around this by writing $b = 2(\le a) + (0 \text{ or } 1)$. That's why I introduced the third variable $z$ above. To make sure $z$ only was every $1$ or $2$, you multiply the whole thing by this contrived expression $1 - 2013(z-1)(z-2)$ that causes the entire polyonmial to self-destruct (become very negative) if we put in any larger $z$. And that's how you get the $P$...

Can this be generalized? Determine if there exists a (k-variable) polynomial $P(x_1, x_2,...x_k)$ with integer coefficients satisfying the following property: a positive integer $n$ is not a perfect square if and only if there is a triple $(x_1, x_2,...x_k)$ of positive integers such that $P(x_1, x_2,...x_k) = n$.

Not interesting; just take a $P$ that solves the three variable case, and then set $P'(x_1,x_2,\cdots,x_k)=P(x_1,x_2,x_3)$.

How about $k=2$?

Does anyone have a solution to $k=2$? Thanks a lot!

Does anyone know of a construction for $k=2$? If not, would you suggest using number theoretic methods or algebraic methods or density methods as suggested in the 2nd post. Can anyone give me some tips to finding a solution? Thank you very much and look forward to your reply!

I think this may be yet another construction:\[P(x,y,z) = (2x+2-(y+z))((y+z)-2x)(x^2+y)\] As said by v_enhance, any positive integral non-square $n$ can be expressed as $a^2+b$ with $b \in \{1,2,\ldots,2a\}$ and $a \in \mathbb{N}$. For such an $n$, take $x = a$, $y = b$ and $z = 2a+1-b$. Conversely, if there existed $x_0,y_0,z_0 \in \mathbb{N}$ with $P(x_0,y_0,z_0) = n$ where $n$ is a positive integral square, then $y_0+z_0 = 2x_0+1$: if $y_0+z_0 \le 2x_0$, then the first and third factors are positive while the middle factor is non-positive. If $y_0+z_0 \ge 2x_0+2$, then the second and third factors are positive while the middle factor is non-positive. Either then implies that $n \le 0$, which doesn't work. With $y_0+z_0 = 2x_0+1$, $n = P(x_0,y_0,z_0) = x_0^2+y_0$. Since $y_0$ and $z_0$ are both positive, $y_0 \le 2x_0$ so $x_0^2 < n < (x_0+1)^2$, a contradiction.

Evil Problem: Show that there exists an integer polynomial $Q$ in 12 variables such that a positive integer $n$ is not a perfect square if and only if there is a 12-tuple $(x_1, x_2, \cdots, x_{12})$ of integers satisfying $Q(x_1, x_2, \cdots, x_{12}) = n$.

Sketch

I think $z(2-(x^2-zy^2)^2)$ works. since $x,y,z,n$ are positive integers if $z(2-(x^2-zy^2)^2)=n$ then $|x^2-zy^2| \le 1$ so $|x^2-zy^2|=1$should hold if $z$ is not a square and $x^2-zy^2=0$should hold if $z$ is a square thus $z(2-(x^2-zy^2)^2)$ is either $z$ ($z$ is a non square) or $2z$ ($z$ is a square) which is clearly not a perfect square but can represent every other positive integers(choose $z=n$ and $(x,y)$is a solution of the pell equation $x^2-zy^2=1$)

I'm not very impressed because the following also holds: There exists a multi-variant polynomial $P$, that a positive number $n$ is attained by $P$ (while all its variants are positive integers) iff $n$ is a prime number.

Click to reveal hidden text

Why those contestants don't know this is beyond me.

Hopefully this works.

Click to reveal hidden text

This construction also works \[ \left (100-99((z-1)(z-2)+1)^2 \right )(x+y-1)^2 + (z-1)(2x) - (z-2)(2x+1) \]I don't really have time to write up but good problem.

In fact, the polynomial $P(x,y,z)=(x+y+z-3)^2+4x+2y-4$ works, and in my opinion, it's the most motivated construction here by far. Let $u=x-1,\,v=y-1,\,w=z-1$, so $u,v,w$ are nonnegative integers with $P(u,v,w)=(u+v+w)^2+4u+2v+2$. If $u+v+w=k$ is fixed, $4u+2v+2$ takes on the values $2,4,\dots,4k+2$. Thus $\{P(u,v,w)\mid u+v+w=k\}=\{k^2+2,k^2+4,\dots,(k+2)^2-2\}$, creating a ``double-layered'' pattern.

this is the literal definition of an anti-problem Take \[P(x, y, z) = (x+y-1)^2 + 2y-(2-z) - 100! (z-1)(z-2)\left((x+y-1)^2 + 2y\right).\]Then, When $z = 1$, we get numbers of the form $(x+y-1)^2 + 2y-1$, which can be reparametrized as $a^2 + b$ for $b > 0$ odd at most $2a$; When $z=2$, we get numbers of the form $(x+y-1)^2 + 2y$, which can be reparametrized as $a^2+b$ for $b>0$ even at most $2a$; When $z \geq 3$, we get random negative numbers. This polynomial clearly satisfies the given conditions.