Putnam 2008 A5

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Putnam 2008 A5

G H J

Reveal topic tags

analytic geometry

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#1 h Dec 8, 2008, 12:23 AM • 3 Y

Y by Adventure10, Mango247, kiyoras_2001

Let $n\ge 3$ be an integer. Let $f(x)$ and $g(x)$ be polynomials with real coefficients such that the points $(f(1),g(1)),(f(2),g(2)),\dots,(f(n),g(n))$ in $\mathbb{R}^2$ are the vertices of a regular $n$ -gon in counterclockwise order. Prove that at least one of $f(x)$ and $g(x)$ has degree greater than or equal to $n-1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Dec 8, 2008, 12:23 AM • 2 Y

Y by Adventure10, Mango247

Define $P(x) = f(x) + ig(x).$ $P$ is a polynomial with complex coefficients. The claim that at least one of $f$ and $g$ has degree at least $n - 1$ is precisely the claim that the degree of $P$ is at least $n - 1.$

By hypothesis, $P(k) = z_0 + re^{2\pi i\frac {(k - 1)}m + i\delta}$ for some fixed $z_0$ (the center of the polygon), some $r > 0$ (the radius of the circle that circumscribes the polygon) and some $\delta$ (a measure of how far the polygon is rotated from standard position.) Subtracting a constant such as $z_0$ does not change the degree of a nonconstant polynomial (and $P$ is surely nonconstant). Multiplying or dividing by a nonzero constant such as $r$ or $e^{i\delta}$ does not change the degree of a polynomial. Hence WLOG we may assume that $P(k) = e^{2\pi i(k - 1)/n} = \zeta^{k - 1}$ for $\zeta = e^{2\pi i/n}.$

We now turn to finite differences. Define $\Delta f(x) = f(x + 1) - f(x).$ By the binomial theorem, $\Delta x^m$ equals $mx^{m - 1}$ plus terms of degree lower than $m - 1.$ It follows that if $f$ is a polynomial of degree exactly $m,$ for $m\ge 1,$ then $\Delta f$ is a polynomial of degree exactly $m - 1.$ (And if $f$ is constant, then $\Delta f = 0.$ ) By iteration, we see that if $f$ is a polynomial and if $\Delta^mf(x)\ne 0$ at any point, then the degree of $f$ must be at least $m.$
$P(k) = \zeta^{k - 1}\text{ for }0\le k\le n - 1$ $\Delta P(k) = \zeta^{k - 1}(\zeta - 1)\text{ for }0\le k\le n - 2$ $\Delta^2 P(k) = \zeta^{k - 1}(\zeta - 1)^2\text{ for }0\le k\le n - 3$ $\vdots$ $\Delta^{n - 1}P(0) = (\zeta - 1)^{n - 1}$
Since $\zeta - 1\ne 0,$ this shows that $\Delta^{n - 1} P(0)\ne 0,$ which means that the degree of $P$ is at least $n - 1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#3 h Dec 8, 2008, 12:32 AM • 4 Y

Y by Adventure10, Mango247, centslordm, and 1 other user

Go me for writing a big spiel about finite differences in my blog, then proceeding to miss that solution at the end of this problem and turning to Lagrange Interpolation to show $P$ had degree at least $n-1$ . At least it worked.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#4 h Dec 8, 2008, 12:41 AM • 2 Y

Y by Adventure10, Mango247

Palmer, I thought for sure you'd be elated once you saw this problem; I immediately thought of your post

The explicit formula for the $(n-1)^{th}$ difference of any sequence with $n$ terms is

$\sum_{k=0}^{n-1} (-1)^{n-1-k} {n-1 \choose k} p(k)$

which gives Kent Merryfield's answer immediately by the binomial theorem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#5 h Dec 8, 2008, 12:44 AM • 2 Y

Y by Adventure10, Mango247

Well, I was elated; polynomials and roots of unity tend to be something I'm good at. Doesn't mean I learned my own lessons.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

777 posts

Sly Si

#6 h Dec 8, 2008, 1:46 AM • 4 Y

Y by ASnooby, Adventure10, Mango247, kiyoras_2001

You can do it without finite differences:

We can translate $P(x)$ without changing its degree so that the polygon is centered at the origin. Call the new polynomial $Q(x)$ . Now if we let $z=e^{\frac{2 \pi i}{n}}$ , notice that for $n=1,2,3,...,n-1$ , $Q(n+1)=zQ(n)$ .

So now we define a new polynomial $R(x) = Q(x+1) - zQ(x)$ . This has degree at most the degree of $Q$ , and it has $n-1$ roots. Therefore the degree of $Q$ is at least $n-1$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatalystOfNostalgia

1479 posts

CatalystOfNostalgia

#7 h Dec 8, 2008, 2:56 AM • 2 Y

Y by Adventure10, Mango247

Ahhh! I almost had this one! It seems that I made a computational error in my finite difference calculations. Oh well.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7 posts

#8 h Dec 8, 2008, 3:07 AM • 2 Y

Y by Adventure10, Mango247

Sly Si wrote:

You can do it without finite differences:

We can translate $P(x)$ without changing its degree so that the polygon is centered at the origin. Call the new polynomial $Q(x)$ . Now if we let $z = e^{\frac {2 \pi i}{n}}$ , notice that for $n = 1,2,3,...,n - 1$ , $Q(n + 1) = zQ(n)$ .

So now we define a new polynomial $R(x) = Q(x + 1) - zQ(x)$ . This has degree at most the degree of $Q$ , and it has $n - 1$ roots. Therefore the degree of $Q$ is at least $n - 1$ , as desired.

dang this is far more nice than the lagrange interpolation / finite difference route

pretty sweet

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

calcer

#9 h Dec 8, 2008, 8:51 AM • 2 Y

Y by Adventure10, Mango247

So, what I got to was proving that both of these could not be true:
$\sum_{k = 1}^{n - 1} ( - 1)^{k - n + 1} \left(\!\!\begin{array}{c}n - 1 \\ k - 1\end{array}\!\!\right) \cos{\left(\theta + \frac {2\pi (k - 1)}{n}\right)} = \cos{\left(\theta - \frac {2\pi}{n}\right)}$

$\sum_{k = 1}^{n - 1} ( - 1)^{k - n + 1} \left(\!\!\begin{array}{c}n - 1 \\ k - 1\end{array}\!\!\right) \sin{\left(\theta + \frac {2\pi (k - 1)}{n}\right)} = \sin{\left(\theta - \frac {2\pi}{n}\right)}$
Did anybody else somehow get to that? Or, rather - does it look possible to prove?

Looking over these posts, I can't believe I didn't think of using complex numbers, but hey, whatcha gonna do...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#10 h Dec 8, 2008, 3:15 PM • 2 Y

Y by Adventure10, Mango247

The first equation plus $i$ times the second equation is $e^{ i \theta} (e^{\frac {2 \pi i}{n} } - 1)^{n - 1}$ on the LHS and $e^{ i \theta} e^{ - \frac {2 \pi i}{n} }$ on the RHS. The factor on the LHS has absolute value $1$ if and only if $n = 3, 6$ .

It looks like you Lagrange interpolated through the first $n - 1$ points and you're trying to show that you can't get to the last point, correct?

Here's a thought. The conclusion no longer holds if we drop the requirement that the points be in order. What is the smallest degree required to produce $n$ points on an $n$ -gon in some order?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

calcer

#11 h Dec 8, 2008, 6:36 PM • 1 Y

Y by Adventure10

Yeah, that's exactly what I did. Would what I did get any points, do you think?

Again, I just can't believe I didn't think to use complex numbers.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1963 posts

#12 h Dec 9, 2008, 5:42 PM • 1 Y

Y by Adventure10

Sly Si wrote:

You can do it without finite differences:

We can translate $P(x)$ without changing its degree so that the polygon is centered at the origin. Call the new polynomial $Q(x)$ . Now if we let $z = e^{\frac {2 \pi i}{n}}$ , notice that for $n = 1,2,3,...,n - 1$ , $Q(n + 1) = zQ(n)$ .

So now we define a new polynomial $R(x) = Q(x + 1) - zQ(x)$ . This has degree at most the degree of $Q$ , and it has $n - 1$ roots. Therefore the degree of $Q$ is at least $n - 1$ , as desired.

You have to be careful to show that $R$ is not identically zero, but nice.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#13 h Dec 9, 2008, 5:43 PM • 1 Y

Y by Adventure10

Its leading coefficient is $1 - z$ times the leading coefficient of $Q$ . I suppose you're right that that issue does need to be addressed, though; that is, $R$ has degree exactly the degree of $Q$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

777 posts

Sly Si

#14 h Dec 9, 2008, 10:59 PM • 2 Y

Y by Adventure10, Mango247

Nukular wrote:

Sly Si wrote:

You can do it without finite differences:

We can translate $P(x)$ without changing its degree so that the polygon is centered at the origin. Call the new polynomial $Q(x)$ . Now if we let $z = e^{\frac {2 \pi i}{n}}$ , notice that for $n = 1,2,3,...,n - 1$ , $Q(n + 1) = zQ(n)$ .

So now we define a new polynomial $R(x) = Q(x + 1) - zQ(x)$ . This has degree at most the degree of $Q$ , and it has $n - 1$ roots. Therefore the degree of $Q$ is at least $n - 1$ , as desired.

You have to be careful to show that $R$ is not identically zero, but nice.

*kicking self* How many points do you think I lost for not doing that?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1693 posts

#15 h Dec 10, 2008, 12:23 AM • 2 Y

Y by Adventure10, Mango247

you probably lost 1 point at the most. The solution is really nice and the graders are more lenient in the A(B)5 A(B)6 region.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

805 posts

#16 h Dec 13, 2008, 8:23 PM • 2 Y

Y by Adventure10, Mango247

Kent Merryfield wrote:

$P(k) = \zeta^{k - 1}\text{ for }0\le k\le n - 1$

$\Delta P(k) = \zeta^{k - 1}(\zeta - 1)\text{ for }0\le k\le n - 2$

$\Delta^2 P(k) = \zeta^{k - 1}(\zeta - 1)^2\text{ for }0\le k\le n - 3$

$\vdots$

$\Delta^{n - 1}P(0) = (\zeta - 1)^{n - 1}$
Since $\zeta - 1\ne 0,$ this shows that $\Delta^{n - 1} P(0)\ne 0,$ which means that the degree of $P$ is at least $n - 1.$

Just a minor detail...did you mean to write, for example, $1\le k\le n$ instead of $0\le k\le n - 1$ and $\Delta^{n - 1}P(1) = (\zeta - 1)^{n - 1}$ instead of $\Delta^{n - 1}P(0) = (\zeta - 1)^{n - 1}$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#17 h Dec 13, 2008, 9:20 PM • 2 Y

Y by Adventure10, Mango247

The notation in this problem works out nicer if you let $P(x) = f(x + 1) + i g(x + 1)$ instead, although that's a cosmetic distinction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#18 h Dec 13, 2008, 10:42 PM • 2 Y

Y by Adventure10, Mango247

I fixed that in the handout I gave my class afterwards - I guess I forgot to fix it here. Read what I meant to say, not what I actually said.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

805 posts

#19 h Dec 13, 2008, 10:46 PM • 1 Y

Y by Adventure10

Hmmm...someone above mentioned a Lagrange Interpolation solution. The Lagrange Interpolant is (after transforming the polygon to the roots of unity)

$L(z) = \sum_{k=1}^n e^{2 \pi i (k-1)/n} \frac{ (z-1) (z-2) \cdots (z-(k-1)) (z-(k+1)) \cdots (z-n)} {(k-1) (k - 2) \cdots(k - (k-1) ) (k - (k+1)) \cdots (k - n) }$

so we would need to show that the coefficient of $z^{n-1}$

$\sum_{k=1}^n e^{2 \pi i (k-1)/n} \frac{1} {(k-1) (k - 2) \cdots(k - (k-1) ) (k - (k+1)) \cdots (k - n) }$

is not zero. How would one do that?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5850 posts

#20 h Dec 13, 2008, 10:48 PM • 1 Y

Y by Adventure10

That would have been me.

Multiply that giant fraction by $(n-1)!$ to make it a binomial coefficient times -1 to the something, then apply the binomial theorem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#21 h Dec 13, 2008, 11:11 PM • 2 Y

Y by Adventure10, Mango247

As is usually the case when the $x$ coordinates are well-spaced, the interpolation is much easier using Newton polynomials than using Lagrange interpolation. See here, especially the first practice problem, which is an alternate approach - you can interpolate through the first $n-1$ points and show that you can't reach the last point.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

29 posts

#22 h Dec 2, 2011, 7:58 PM • 2 Y

Y by Adventure10, Mango247

Hmm does this work?

First we can translate the polygon so that its center is the origin. This is because setting $f_2(x) = f(x)-k$ doesn't affect its degree.

Let $a = 2\pi/n$ be the angle of rotation. Then we have the identities:

$f(x+1) = \cos(a)f(x) - \sin(a)g(x)$ and $g(x+1) = \sin(a)f(x)+cos(a)g(x)$ for $x=1,2...n-1$ .

Define $d_1(x) = f(x+1) - \cos(a)f(x) + \sin(a)g(x)$ and $d_2(x) = g(x+1) - \sin(a)f(x) - cos(a)g(x)$ . Since $d_1$ has at least $n-1$ roots, it is either of degree $n-1$ or greater or the zero polynomial. In the first case, since the degree of $f(x+1)$ is the same as the degree of $f(x)$ , at least one of $f(x)$ or $g(x)$ have degree at least $n-1$ . Hence we can assume $d_1(x) = 0$ , similarly we can assume $d_2(x) = 0$ .

Then $f(x+1) = \cos(a)f(x) - \sin(a)g(x)$ and $g(x+1) = \sin(a)f(x)+cos(a)g(x)$ holds for all $x$ , squaring both equations and adding, we get

$(f(x+1))^2+(g(x+1))^2 = (f(x))^2+(g(x))^2$ for all $x$ . Thus $(f(k))^2+(g(k))^2 = (f(1))^2+(g(1))^2$ for all integer $k$ , which implies that $f(x)$ cannot tend to plus or minus infinity as $x$ tends to infinity. Yet this implies that $f(x)$ is a constant polynomial, which of course can't work for regular polygons of three or more vertices (the $x$ coordinate can't be constant). Contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

TheStrangeCharm

290 posts

TheStrangeCharm

#23 h Nov 14, 2014, 12:50 AM • 2 Y

Y by Adventure10, Mango247

A lagrange interpolation solution has already been discussed, but here is a more complete one:

Like other solutions, we consider the polynomial $P(x) = f(x) + ig(x)$ , with complex coefficients. Our goal is now to show that $P$ has degree at least $n-1$ , as this will imply that either $f$ or $g$ have degree at least $n - 1$ . Now, we know that $P$ takes on the value of a regular n-gon somewhere in the complex plane at the values 1,2...,n. There is a polynomial of minimal degree that does this, and clearly this polynomial must be a factor of $P$ . Thus, it suffices to show that the minimal degree polynomial that takes on these values has degree at least $n - 1$ . But we know how using lagrange interpolation to explicitly construct this polynomial.

Let $\omega = e^{\frac{2\pi i}{n}}$ . Then we know that $P(k) = r\omega ^{k-1} + z_0$ , where $r$ and $z_0$ are some complex numbers. for k = 1,2,...,n. Now lagrange interpolation tells us that

$P(x) = \sum_{k=1}^n P(k) \cdot \prod_{j = 1, j \neq k}^n \frac{x - j}{k - j}$

It suffices to show that the coefficient of $x^{n-1}$ in this polynomial is non-zero, which will imply the result. It is not hard to see that coefficient of $x^{n-1}$ in this polynomial is

$\sum_{k = 1}^n P(k) \cdot \prod_{j = 1, j \neq k}^n \frac{1}{k-j}$

Now, we note that we have that
$\prod_{j = 1, j \neq k}^n \frac{1}{k-j} = \frac{(-1)^{n-k}}{(k-1)!(n - k)!}$

If the coefficient of $x^{n-1}$ is not zero, then certainly it will not be zero after we multiply if by $(n-1)!$ , so after we multiply the coefficient of $x^{n-1}$ by $(n-1)!$ , we get

$\sum_{k = 1}^n P(k) \cdot (-1)^{n-k} \cdot \binom{n-1}{k-1}$

Subtracting a constant from $P(x)$ and multiplying it by some non-zero complex number clearly does not change the degree of the polynomial, so we may just assume that $P(k) = \omega^{k-1}$ for k = 1,2,...,n. Now, all we have to show is that
$\sum_{k=1}^n \omega^{k-1} \cdot (-1)^{n-k} \cdot \binom{n-1}{k-1}$ is nonzero. But by the binomial theorem, this is just $(\omega - 1)^{n-1}$ , which is clearly non-zero as $\omega \neq 1$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#24 h Sep 22, 2022, 1:50 AM

Y by

Let $P(x)=f(x)+ig(x)$ . Then via a suitable linear transformation we can assume $P(x)=\omega^x$ for $x=0,1,\cdots,n-1$ where $\omega=e^{\frac{2\pi i}{n}}$

I will show if $P(x)=k^x$ for some $k\ne 1$ and for all $x=0,\cdots,n-1$ then $\deg P\ge n-1$ .

Induct on $n$ ; consider $Q(x)=\frac{P(x+1)-P(x)}{k-1}$ , which has degree at least $n-2$ by inductive hypothesis.

This post has been edited 1 time. Last edited by CANBANKAN, Sep 22, 2022, 2:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8219 posts

#25 h Sep 22, 2022, 4:38 AM

Y by

Yet another way. Repeating a lot of what previous users have said, using some transformations, we see that we must prove that given a polynomial such that for $x=0,1,\ldots,n-1$ we have $P(x)=\omega^x$ where $\omega=e^{2\pi i/n}$ must have degree at least $n-1$ . It suffices to find a degree $n-1$ polynomial $Q(x)$ that satisfies $Q(x)=\omega^x$ for $x=0,1,\ldots,n-1$ . This is because if we found such a polynomial, then $Q(x)-P(x)$ would have $n$ roots, so it must either be the zero polynomial or a polynomial of degree at least $n$ . We can see that if $P(x)$ had degree less than $n-1$ then neither case would be true.

Now to construct our $Q$ consider $Q(x)=\sum_{k=0}^{n-1} \binom{x}{k}(\omega-1)^k$ . Note that $\binom{x}{k}=\frac{1}{k!}x(x-1)(x-2)\cdots(x-k+1)$ is a polynomial in $x$ of degree $k$ so this sum is indeed a polynomial of degree $n-1$ . Moreover, by binomial theorem, for any $x=0,1,\ldots,n-1$ we have $Q(x)=(1+\omega-1)^x=\omega^x$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

703 posts

#26 h May 20, 2023, 11:02 PM

Y by

Let $\zeta=e^{2\pi i/n}$ , and assume FTSOC that $\max(\deg f, \deg g)< n-1$ . We may take the linear transformation mapping this polygon to the one centered at the origin with the $n$ th roots of unity, so that we result in $(\widetilde f(0),\widetilde g(0))$ , $(\widetilde f(1),\widetilde g(1))$ , etc. Now let $g(X)=\widetilde f(X)+i\widetilde g(X)$ . Then $g(0)=1$ , $g(1)=\zeta$ , $g(2)=\zeta^2$ , etc, so $\zeta g(X)-g(X+1)=0\qquad\text{for }X=0, 1, 2,\dots,n-2.$ Therefore $X(X-1)(X-2)\cdots(X-(n-2))$ divides $\zeta g(X)-g(X+1)$ , so $g$ must have degree at least $n-1$ .
However, $\max(\deg f(x),\deg(g(x))$ implies that $\deg g<n-1$ , contradiction.

This post has been edited 3 times. Last edited by cinnamon_e, Jul 21, 2023, 6:47 PM
Reason: edited solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6 posts

#28 h Aug 11, 2023, 4:58 AM

Y by

Without loss of generality let the polygon be centered at the origin and on the unit circle. We can do this since we can just shift by the centroid of the polygon and scale down, neither of which change the degree of the polynomials. Letting $a = \cos \frac{2\pi}{n}$ and $b = \sin \frac{2\pi}{n}$ we obtain the following:

$\begin{align*} a\cdot f(x)-b\cdot g(x) &= f(x+1), \\ b \cdot f(x)+a \cdot g(x) &= g(x+1), \end{align*}$
for $x = 0, 1, \ldots, n-2$ . We get this by multiplying the complex number $f(k) + i \cdot g(k)$ by $e^{2 \pi i /n}$ and equating real and imaginary parts with the complex number $f(k+1) + i \cdot g(k+1)$ , again for $k = 0, 1, \ldots, n-2$ .

Now suppose $\max (\deg f, \deg g) < n-1$ . Rewriting both equations by moving everything to left side, we see that the degree of the left is at most $n-2$ . However, both polynomials have $n-1$ solutions, which is a contradiction. Thus, $\max (\deg f, \deg g) \geq n-1$ .

This post has been edited 3 times. Last edited by Ninjurikens, Dec 1, 2023, 7:51 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

194 posts

#29 h Aug 30, 2023, 6:50 PM

Y by

This is such an amazing problem.
Let $(s, t)$ be a center of regular $n$ -gon with vertices $(f(0), g(0)), ... , (f(n - 1), g(n - 1))$ and let $r$ be a its circumcircle radius. Replacing $f(X), g(X)$ to $\frac{1}{r}(f(X) - s), \frac{1}{r}(g(X) - t)$ , we can assume that circumcircle of regular $n$ -gon with vertices $(f(0), g(0)), ... , (f(n - 1), g(n - 1))$ is unit circle. Let $a$ be a real number such that $f(0) = \cos{a}, g(0) = \sin{a}$ . Then for $0 \leq k \leq n - 1$ , we have $f(k) = cos(\frac{2\pi k}{n} + a), g(k) = sin(\frac{2\pi k}{n} + a)$ . Assume deg $f$ , deg $g$ $\leq n - 1$ . Then $f$ is the interpolation polynomial of $n$ points $(0, cos(a)), (1, cos(\frac{2\pi}{n} + a)), ... , (n - 1, cos(\frac{2\pi(n - 1)}{n} + a))$ , so $f(X) = \sum_{k=0}^{n-1}cos(\frac{2\pi k}{n} + a)\prod_{i=0,i\neq k}^{n-1}\frac{X-i}{k-i}$ . Therefore the coefficient of $X^{n-1}$ of $f$ is $\sum_{k=0}^{n-1}cos(\frac{2\pi k}{n} + a)\prod_{i=0, i\neq k}^{n-1}\frac{1}{k-i} = \sum_{k=0}^{n-1}cos(\frac{2\pi k}{n} + a)\frac{(-1)^{n - 1 - k}}{k!(n - 1 - k)!} = \frac{1}{(n-1)!}\sum_{k=0}^{n-1}cos(\frac{2\pi k}{n} + a)(-1)^{n-1-k}\binom{n-1}{k}$ . Similarly the coefficient of $X^{n-1}$ of $g$ is
$\frac{1}{(n-1)!}\sum_{k=0}^{n-1}sin(\frac{2\pi k}{n} + a)(-1)^{n-1-k}\binom{n-1}{k}$ . Let $a$ and $b$ be coefficient of $X^{n-1}$ of $f, g$ , respectively. Then $a + bi = \frac{1}{(n-1)!}\sum_{k=0}^{n-1}(cos(\frac{2\pi k}{n} + a) + isin(\frac{2\pi k}{n}+a))(-1)^{n-1-k}\binom{n-1}{k} = \frac{e^{ia}}{(n-1)!}\sum_{k=0}^{n-1}e^{\frac{2\pi k}{n}}(-1)^{n-1-k}\binom{n-1}{k} = \frac{e^{ia}}{(n-1)!}(e^{\frac{2\pi}{n}} - 1)^{n-1} \neq 0$ . Therefore one of the $a,b$ is not equal to 0 means $\max(\deg$ f $, \deg$ g $) \geq n - 1$ , as desired.

This post has been edited 3 times. Last edited by thdnder, Jan 19, 2024, 5:59 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

793 posts

#30 h Oct 17, 2023, 4:45 AM

Y by

We can throw this on the complex plane by defining $m(x) = f(x) + g(x) \cdot i$ . Since $m(x)$ forms a regular $n$ -gon the complex plane for $x = 0, 1, \ldots, n-1$ , we have
$m(x+1) = \operatorname{cis } \left(\frac{2\pi}{n}\right) \cdot m(x)$
for $x = 0, 1, \ldots, n-2$ . As a result, we know
$n(x) = m(x+1) - m(x) \cdot \operatorname{cis } \left(\frac{2\pi}{n}\right)$
has roots $0, 1, \ldots, n-2$ . Hence
$n-1 \leq \deg(n) \leq \deg(m) \leq \max(\deg (f), \deg (g)).~\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

930 posts

#31 h May 4, 2024, 8:45 AM • 1 Y

Y by tohill

The regular n-gon is the takeaway from this problem

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2513 posts

#32 h Aug 17, 2024, 6:47 PM

Y by

Transform the function so the center of the $n$ -gon is the origin. Then, let $h(x) = f(x)+ig(x)$ . We have

$h(x) = e^{\frac{2i\pi}{n}} h(x-1),$
for $x = 1,2,\dots,n-1$ . Thus, the polynomial

$h(x)-e^{\frac{2i\pi}{n}} h(x-1)$
has $n-1$ roots $x = 1,2,\dots,n-1$ , which implies the desired statement (as the polynomial is written in terms of $f$ and $g$ ). $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

116 posts

Iveela

#33 h Nov 9, 2024, 5:33 PM

Y by

Really proud of this one!

We can shift $f$ and $g$ to ensure that $(0, 0)$ is the center of the polygon. Redefine $f$ to be $\frac{f(x) + i g(x)}{f(0) + ig(0)}$ . Observe that for each $0 \leq k \leq n - 1$ , we have $f(k) = \omega^k$ where $\omega = \exp \left( \frac{2 \pi i}{n} \right)$ . It suffices to show that $\deg(f) \geq n - 1$ . In fact, it is true that if $0 \leq k \leq m < n$ implies $f(k) = \omega^k$ , we have $\deg(f) \geq m$ .

We will use induction on $m$ with the base case $1$ being trivial. Let $g(x) = \frac{f(x + 1) - f(x)}{\omega - 1}$ . Note that $\deg(g) < \deg(f)$ . For each $0 \leq k \leq m - 1$ , we have $g(k) = \frac{\omega^{k + 1} - \omega^k}{\omega - 1} = \omega^k$ . By induction hypothesis, this implies $\deg(g) \geq m - 1$ and as $\deg(f) > \deg(g)$ , it is true that $\deg(f) \geq m$ , as desired.

This post has been edited 1 time. Last edited by Iveela, Nov 9, 2024, 5:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

54 posts

#34 h Apr 3, 2025, 5:28 AM

Y by

Let the center of that $n$ -gon be $(a,b)$ . Notice that the polynomial
$H(x) = f(m) - a + ig(m) - bi$ fulfills the property that $H(i) = \omega^{i+k}$ where $\omega$ is a primitive root of unity of $n$ where $i \in \mathbb{N}$ with $0 \leq i \leq n-1$ , $k$ denotes some random integer. We shall show that this polynomial has degree at least $n-1$ , doing so clearly shows that $\max(\deg(f(x)), \deg(g(x))) \geq n-1$ .

Assume FTSOC that $\deg(H(x)) \leq n-1$ . We use Lagrange Interpolation, notice that
$H(x) = \sum_{j=0}^{n-1} \omega^{j+k} \cdot \prod_{0 \leq r \neq j \leq n-1} \frac{x-r}{j - r}$ if this polynomial doesn't have degree $n-1$ , then we must obviously have
$0 = \sum_{j=0}^{n-1} \omega^{j+k} \cdot \prod_{0 \leq r \neq j \leq n-1} \frac{1}{j - r}$ however we can just divide by $\omega^k$ and simplify to obtain
$0 = \sum_{j=0}^{n-1} \omega^{j} \cdot \frac{1}{(j!){(-1)}^{n-1-j}(n-1-j)!} = \frac{1}{(n-1)!} \cdot \sum_{j=0}^{n-1} \binom{n-1}{j} \cdot {(-1)}^{n-1-j} \cdot \omega^{j}$ Getting rid of the $(n-1)!$ term and using the binomial theorem gives us
$0 = {(w-1)}^{n-1}$ which is plainly a contradiction.

This post has been edited 3 times. Last edited by Ihatecombin, Apr 3, 2025, 5:30 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a