First note that there exists a pair $(x,y)$ satisfying the property, namely $x = 1$ and $y = P(1)$. Now suppose $x | P(y)$ and $y | P(x)$. Then $P(x) = yk$ for some positive integer $k$, and gcd($x$, $yk$) $= 1$. Thus $x | k^n * P(y) = k^n * P(P(x)/k) = P(x)^n + a_{n-1}kP(x)^{n-1} + \cdots + a_1 k^{n-1} P(x) + k^n$. Since $P(x) \equiv 1 \pmod x$, we have $x | 1 + a_{n-1}k + \cdots + a_1k^{n-1} + k^n = 1 + a_1 k + \cdots + a_{n-1}k^{n-1} + k^n = P(k)$. The second to last equality follows since we're given that $a_k = a_{n-k}$ for $k = 1, 2, \ldots, n-1$. Therefore, $x | P(k)$ and $k | P(x)$ (since $P(x) = yk$). That is, we can replace $y$ by $P(x)/y$ or replace $x$ by $P(y)/x$. Suppose both $P(x)/y \leq y$ and $P(y)/x \leq x$. Then $P(x) \leq y^2$ and $P(y) \leq x^2$, therefore $P(x) + P(y) \leq x^2 + y^2$. But this is impossible since $x,y$ are *positive* integers and $a_{k}$ are also *positive* integers. Therefore from a pair $(x,y)$ satisfying the property, we can always move it to $(P(y)/x, y)$ or $(x, P(x)/y)$ to obtain a pair with strictly larger coordinates.