Problem 1563

1. Assume the Center of the Polygon is at the Origin:
Without loss of generality (WLOG), we can shift the coordinate system such that the center of the regular $n$-gon is at the origin $(0,0)$.

2. Define a Complex Polynomial:
Define the complex polynomial $P(x) = f(x) + i g(x)$. Here, $f(x)$ and $g(x)$ are the real and imaginary parts of $P(x)$, respectively. The degree of $P(x)$ is given by $\deg P = \max(\deg f, \deg g)$.

3. **Properties of the Regular $n$-gon:**
Since $A_1, A_2, \ldots, A_n$ form a regular $n$-gon centered at the origin, the points $P(1), P(2), \ldots, P(n)$ must be equally spaced on the complex plane. This implies that for each integer $k$ from $0$ to $n-2$ inclusive, we have:
$$P(k+1) = \omega P(k)$$
where $\omega = e^{2\pi i / n}$ is the $n$-th root of unity.

4. **Construct a New Polynomial $Q(x)$:**
Consider the polynomial:
$$Q(x) = P(x) - \omega P(x-1)$$
The degree of $Q(x)$ is at most the degree of $P(x)$, i.e., $\deg Q \leq \deg P$.

5. **Roots of $Q(x)$:**
Notice that $Q(x)$ has at least $n-2$ roots because:
$$Q(k+1) = P(k+1) - \omega P(k) = 0 \quad \text{for} \quad k = 0, 1, \ldots, n-2$$
This implies that $Q(x)$ has at least $n-2$ distinct roots.

6. **Degree of $Q(x)$:**
By the Fundamental Theorem of Algebra, a polynomial with $n-2$ roots must have a degree of at least $n-2$. Therefore:
$$\deg Q \geq n-2$$

7. **Conclusion on the Degree of $P(x)$:**
Since $\deg Q \leq \deg P$ and $\deg Q \geq n-2$, it follows that:
$$\deg P \geq n-2$$
However, since $Q(x)$ must have at least $n-1$ roots to ensure the regularity of the $n$-gon, we actually need:
$$\deg P \geq n-1$$

8. **Conclusion on the Degrees of $f(x)$ and $g(x)$:**
Since $\deg P = \max(\deg f, \deg g)$, we conclude that:
$$\max(\deg f, \deg g) \geq n-1$$

The final answer is $\boxed{ \max(\deg f, \deg g) \geq n-1 }$