First, if $c \ge 2$ then we claim no such $f$ and $g$ exist. Indeed, one simply takes $x=1$ to get $f(1)/g(1) \le 0$, impossible. For $c < 2$, let $c = 2 \cos \theta$. We claim that $f$ exists and has minimum degree equal to $n$, where $n$ is defined as the smallest integer satisfying $\sin n\theta \le 0$. In other words \[ n = \left\lceil \frac{\pi}{\arccos(c/2)} \right\rceil. \] First we show that this is necessary. To see it, write explicitly \[ g(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-2} x^{n-2} \]with each $a_i \ge 0$, and $a_{n-2} \neq 0$. Assume that $n$ is such that $\sin(k\theta) \ge 0$ for $k=1,\dots,n-1$. Then, we have the following system of inequalities: \begin{align*} a_1 &\ge 2 \cos \theta \cdot a_0 \\ a_0 + a_2 &\ge 2 \cos \theta \cdot a_1 \\ a_1 + a_3 &\ge 2 \cos \theta \cdot a_2 \\ &\vdots \\ a_{n-5} + a_{n-3} &\ge 2 \cos \theta \cdot a_{n-4} \\ a_{n-4} + a_{n-2} &\ge 2 \cos \theta \cdot a_{n-3} \\ a_{n-3} &\ge 2 \cos \theta \cdot a_{n-2}. \end{align*}Now, multiply the first equation by $\sin\theta$, the second equation by $\sin2\theta$, et cetera, up to $\sin\left( (n-1)\theta \right)$. This choice of weights is selected since we have \[ \sin \left( k\theta \right) + \sin\left( (k+2)\theta \right) = 2 \sin\left( (k+1)\theta \right) \cos \theta \]so that summing the entire expression cancels nearly all terms and leaves only \[ \sin\left( (n-2)\theta \right) a_{n-2} \ge \sin\left( (n-1)\theta \right) \cdot 2\cos\theta \cdot a_{n-2} \]and so by dividing by $a_{n-2}$ and using the same identity gives us $\sin(n\theta) \le 0$, as claimed. Remark: Calvin Deng points out that a cleaner proof of the lower bound is to take $\alpha = \cos \theta + i \sin \theta$. Then $f(\alpha) = 0$, but by condition the imaginary part of $f(\alpha)$ is apparently strictly positive, contradiction. This bound is best possible, because the example \[ a_k = \frac{\sin\left( (k+1)\theta \right)}{\sin\theta} \ge 0 \]makes all inequalities above sharp, hence giving a working pair $(f,g)$. Remark: Guessing that $c < 2$ works at all (and realizing $c \ge 2$ fails) is the first part of the problem. The introduction of trigonometry into the solution may seem magical, but is motivated in one of two ways: Calvin Deng points out that it's possible to guess the answer from small cases: For $c \le 1$ we have $n = 3$, tight at $\frac{x^3+1}{x+1} = x^2-x+1$, and essentially the ``sharpest $n=3$ example''. A similar example exists at $n = 4$ with $\frac{x^4+1}{x^2+\sqrt 2 x+1} = x^2-\sqrt2x+1$ by the Sophie-Germain identity. The thresholds $c \le 1$ for $n = 3$, $c \le \sqrt 2$ for $n = 4$, and $c \le 2$ for $n < \infty$ suggest the unusual form of the answer via trigonometry. One may imagine trying to construct a polynomial recursively / greedily by making all inequalities above hold (again the ``sharpest situation'' in which $f$ has few coefficients). If one sets $c = 2t$, then we have \[ a_0 = 0, \quad a_1 = 2t, \quad a_2 = 4t^2-1, \quad a_3 = 8t^2-4t, \quad \dots \]which are the Chebyshev polynomials of the second type. This means that trigonometry is essentially mandatory. (One may also run into this when by using standard linear recursion techniques, and noting that the characteristic polynomial has two conjugate complex roots.) Remark: Mitchell Lee notes that an IMO longlist problem from 1997 notes that if $P(x)$ is any polynomial satisfying $P(x) > 0$ for $x > 0$ then $(x+1)^n P(x)$ has nonnegative coefficients for large enough $n$. This show that $f$ and $g$ at least exist for $c \le 2$, but provides no way of finding the best possible $\deg f$. Meghal Gupta also points out that showing $f$ and $g$ exist is possible in the following way: \[ \left( x^2-1.99x+1 \right) \left( x^2+1.99x+1 \right) = \left( x^4 - 1.9601x + 1 \right) \]and so on, repeatedly multiplying by the ``conjugate'' until all coefficients become positive. To my best knowledge, this also does not give any way of actually minimizing $\deg f$.

v_Enhance wrote: Meghal Gupta also points out that showing $f$ and $g$ exist is possible in the following way: \[ \left( x^2-1.99x+1 \right) \left( x^2+1.99x+1 \right) = \left( x^4 - 1.9601x + 1 \right) \]and so on, repeatedly multiplying by the ``conjugate'' until all coefficients become positive. To my best knowledge, this also does not give any way of actually minimizing $\deg f$. It might not give a way to minimize $\deg f$, but this shows that (for example) that if $c \le \sqrt{2 + \sqrt{2 + \sqrt{2}}}$, then $\deg f \le 16$. Now, the expression $\sqrt{2 + \sqrt{2 + \sqrt{\cdots + \sqrt{2}}}}$ (where there are $n$ square roots) is equal to $2 \cos \tfrac{\pi}{2^{n + 1}}$, which provides strong motivation to consider trigonometry, as now we have $c \le 2 \cos \tfrac{\pi}{2^n}$ implies $\deg f \le 2^n$; guessing the answer from here is not difficult.

v_Enhance wrote: The thresholds $c \le 1$ for $n = 3$, $c \le \sqrt 2$ for $n = 4$, and $c \le 2$ for $n < \infty$ suggest the unusual form of the answer via trigonometry How are these values enough - it took me up to $c \le \frac{\sqrt{5}+1}{2}$ for $n=5$ and $c \le \sqrt{3}$ for $n=6$ to think of $n = \left\lceil \frac{\pi}{\arccos(c/2)} \right\rceil$. Whoops.

The fastest way to see that trig is needed, in my opinion, is to consider what the polynomial $f$ is at the boundaries $c=1, \sqrt{2}, \dfrac{\sqrt{5}+1}{2}$. At these values $f$ is equal to $x^3+1, x^4+1, x^5+1$. But factoring $x^n+1$ is easy with roots of unity, and you can easily see that $x^2 - 2\cos \dfrac{\pi}{n}x+1$ divides $f=x^n+1$, at which point it is immediate what the answer is.

What does TSTST stand for?

meagain wrote: What does TSTST stand for? Team Selection Test for the Selection Team

So we have some selected people and they take TST? But is not that just TST?

meagain wrote: So we have some selected people and they take TST? But is not that just TST? Unfortunately, the $T=TST$ conjecture is unproven. If you forward me the solution and don't show anyone else, I promise to wire you $100%

meagain wrote: So we have some selected people and they take TST? But is not that just TST? Taken from http://web.evanchen.cc/FAQs/rules.html : Quote: Starting in 2011 and as of 2016, the IMO selection procedure is as follows. In the USA the main olympiad event is the USA(J)MO held in April each year. Roughly 250 students qualify for the USAMO and 250 students qualify for the USA(J)MO via scores on previous short-answer contests. Then things get interesting: * In USAMO of year N−1, about 60 students in grades 11 and below, as well as the IMO team and alternate of that year, are invited to the three-week Mathematical Olympiad Summer Program, abbreviated MOP (also called MOSP in more official sources). * At the end of MOP, an IMO-style exam called the TSTST (yes, I know) is given. The top approximately 18 students are then selected for the year-round TST's for the IMO of year N. * Two TST's are given in December and January, administered by schools. Contestants also usually participate in APMO and RMM Day 1 (though this occasionally varies). * Finally, the USAMO of year N serves as the final TST. Student's scores over these five tests are added to select the IMO team (usually just the top six sums, but the team leader can pick otherwise.) Hence the IMO selection process takes an entire year. The IMO team is known shortly after the USAMO grading in May. Note in particular that winning the USAMO is neither necessary or sufficient for qualifying for the American IMO team, since the IMO team is determined by several different exams.

v_Enhance wrote: First, if $c \ge 2$ then we claim no such $f$ and $g$ exist. Indeed, one simply takes $x=1$ to get $f(1)/g(1) \le 0$, impossible. For $c < 2$, let $c = 2 \cos \theta$. We claim that $f$ exists and has minimum degree equal to $n$, where $n$ is defined as the smallest integer satisfying $\sin n\theta \le 0$. In other words \[ n = \left\lceil \frac{\pi}{\arccos(c/2)} \right\rceil. \] First we show that this is necessary. To see it, write explicitly \[ g(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-2} x^{n-2} \]with each $a_i \ge 0$, and $a_{n-2} \neq 0$. Assume that $n$ is such that $\sin(k\theta) \ge 0$ for $k=1,\dots,n-1$. Then, we have the following system of inequalities: \begin{align*} a_1 &\ge 2 \cos \theta \cdot a_0 \\ a_0 + a_2 &\ge 2 \cos \theta \cdot a_1 \\ a_1 + a_3 &\ge 2 \cos \theta \cdot a_2 \\ &\vdots \\ a_{n-5} + a_{n-3} &\ge 2 \cos \theta \cdot a_{n-4} \\ a_{n-4} + a_{n-2} &\ge 2 \cos \theta \cdot a_{n-3} \\ a_{n-3} &\ge 2 \cos \theta \cdot a_{n-2}. \end{align*}Now, multiply the first equation by $\sin\theta$, the second equation by $\sin2\theta$, et cetera, up to $\sin\left( (n-1)\theta \right)$. This choice of weights is selected since we have \[ \sin \left( k\theta \right) + \sin\left( (k+2)\theta \right) = 2 \sin\left( (k+1)\theta \right) \cos \theta \]so that summing the entire expression cancels nearly all terms and leaves only \[ \sin\left( (n-2)\theta \right) a_{n-2} \ge \sin\left( (n-1)\theta \right) \cdot 2\cos\theta \cdot a_{n-2} \]and so by dividing by $a_{n-2}$ and using the same identity gives us $\sin(n\theta) \le 0$, as claimed. Remark: Calvin Deng points out that a cleaner proof of the lower bound is to take $\alpha = \cos \theta + i \sin \theta$. Then $f(\alpha) = 0$, but by condition the imaginary part of $f(\alpha)$ is apparently strictly positive, contradiction. This bound is best possible, because the example \[ a_k = \frac{\sin\left( (k+1)\theta \right)}{\sin\theta} \ge 0 \]makes all inequalities above sharp, hence giving a working pair $(f,g)$. Remark: Guessing that $c < 2$ works at all (and realizing $c \ge 2$ fails) is the first part of the problem. The introduction of trigonometry into the solution may seem magical, but is motivated in one of two ways: Calvin Deng points out that it's possible to guess the answer from small cases: For $c \le 1$ we have $n = 3$, tight at $\frac{x^3+1}{x+1} = x^2-x+1$, and essentially the ``sharpest $n=3$ example''. A similar example exists at $n = 4$ with $\frac{x^4+1}{x^2+\sqrt 2 x+1} = x^2-\sqrt2x+1$ by the Sophie-Germain identity. The thresholds $c \le 1$ for $n = 3$, $c \le \sqrt 2$ for $n = 4$, and $c \le 2$ for $n < \infty$ suggest the unusual form of the answer via trigonometry. One may imagine trying to construct a polynomial recursively / greedily by making all inequalities above hold (again the ``sharpest situation'' in which $f$ has few coefficients). If one sets $c = 2t$, then we have \[ a_0 = 0, \quad a_1 = 2t, \quad a_2 = 4t^2-1, \quad a_3 = 8t^2-4t, \quad \dots \]which are the Chebyshev polynomials of the second type. This means that trigonometry is essentially mandatory. (One may also run into this when by using standard linear recursion techniques, and noting that the characteristic polynomial has two conjugate complex roots.) Remark: Mitchell Lee notes that an IMO longlist problem from 1997 notes that if $P(x)$ is any polynomial satisfying $P(x) > 0$ for $x > 0$ then $(x+1)^n P(x)$ has nonnegative coefficients for large enough $n$. This show that $f$ and $g$ at least exist for $c \le 2$, but provides no way of finding the best possible $\deg f$. Meghal Gupta also points out that showing $f$ and $g$ exist is possible in the following way: \[ \left( x^2-1.99x+1 \right) \left( x^2+1.99x+1 \right) = \left( x^4 - 1.9601x + 1 \right) \]and so on, repeatedly multiplying by the ``conjugate'' until all coefficients become positive. To my best knowledge, this also does not give any way of actually minimizing $\deg f$. I am curious about that how many students received some points from this question ?

Is the following solution also correct for $c<2$? $n,$ the degree of $g,$ is the smallest integer such that $c-\frac{1}{c-\frac{1}{c-\frac{1}{\ddots -\frac{1}{c}}}} \le 0$ where there are n+1 c's

Start by assuming that $\gcd(f,g)=1$ and let $f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$, $g(x)=x^{n-2}+b_{n-3}x^{n-3}+\cdots+b_1x+b_0$. We claim that $c\ge 2$ fails. Suppose it works. Note that \[\frac{f(1)}{g(1)}=2-c\le 0,\]but $f(1)/g(1)\ge 0$ also, so $f(1)=0$. Thus, $\sum_{i=0}^{n-1}a_{n-1}=0$, so $a_i=0$ for all $i$, so $f\equiv 0$, which is a contradiction. Thus, we need $c<2$. We claim that if $c<2$, then we can find $f$, with the minimum possible degree of $f$ being $\boxed{\left\lceil\frac{\pi}{\cos^{-1}(c/2)}\right\rceil}$. First we show that we can find $f$ with degree $n=\lceil\pi/\theta\rceil$ where $c=2\cos\theta$ and $\theta\in(0,\pi/2)$. What this boils down to is the following claim. Claim: We have \[(x^2-(2\cos\theta)x+1)\left(x^{n-2}+\frac{\sin(2\theta)}{\sin\theta}x^{n-3}+\cdots+\frac{\sin(n-1)\theta)}{\sin\theta}\right)=x^n-\frac{\sin(n\theta)}{\sin\theta}x+1.\] Claim: The proof is "you just check it". It is a bit annoying, but the key computation is that \[a_k=\frac{\sin((n-1-k)\theta)}{\sin\theta}-2\cos\theta\frac{\sin((n-k)\theta)}{\sin\theta}+\frac{\sin((n-k+1)\theta)}{\sin\theta}=0\]for $2\le k\le n-1$ by using sum to product on the first and the last terms. $\blacksquare$ Now, for $n=\lceil\pi/\theta\rceil$, it is clear that this claim provides a valid construction. All we have to do now is to show that $n\ge \pi/\theta$ is required. To see this, note that $e^{i\theta}$ is a root of $x^2-cx+1$, so it must be a root of $f$ as well. Thus, taking the imaginary part, we have \[\sum_{j=0}^n a_n\sin(n\theta)=0.\]If $n<\pi/\theta$, then all terms except the first are positive, so $a_i=0$ for all $i\ge 0$, so $f$ is constant, which clearly doesn't work. Thus, $n\ge \pi/\theta$, as desired.

Claim: $c<2$. Proof: If $c\ge 2$, then $x^2-cx+1$ has a positive root, and thus $f(x)$ shares it. However, this is impossible since it has only positive coefficients. Now, I claim that the minimum degree of $f$ is given by $\left\lceil\frac{n}{\cos^{-1}(c/2)}\right\rceil$. First, define the sequence of polynomials $P_n(x)$, where $P_0(x)=0, P_1(x)=1$, and $P_{n+1}(x)=xP_n(x)-P_{n-1}(x)$. I claim that $P_n(2\cos\theta)=\frac{\sin n\theta}{\sin\theta}$ We can show this with induction. The claim is clear for $n=1,2$. For higher $n$, note that $$P_{n+1}(2\cos\theta)=2\cos\theta P_{n}(2\cos\theta)-P_{n-1}(2\cos\theta)$$$$=\frac{2\sin n\theta\cos\theta-\sin(n-1)\theta}{\sin\theta}=\frac{\sin(n+1)\theta+\sin(n-1)\theta-\sin(n-1)\theta}{\sin\theta}$$$$=\frac{\sin(n+1)\theta}{\sin\theta}$$as desired. This implies that the roots of $P_n$ which lie between $0$ and $2$ are $2\cos\left(\frac{k\pi}{n}\right)$. Suppose, now, that $g(x)=(a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0)$. Then, if $f(x)=(x^2-cx+1)g(x)$ has nonnegative coefficients, we must have that: $$a_{n-1}\ge ca_{n},\,a_1\ge ca_0,a_i+a_{i+2}\ge ca_{i+1}\forall 0\le i\le n-2$$We now prove by induction that $P_{i+1}(c)\cdot a_{i+1}\ge P_{i+2}(c)\cdot a_i$ for $0\le i<n$, given that $P_i(c)>0\forall 1\le c\le n+1$. Our base case of $i=1$ is clear. Now, note that $$a_i+a_{i-2}\ge ca_{i-1}\implies a_i+\frac{P_{i-1}(c)\cdot a_{i-1}}{P_{i}(c)}\ge ca_{i-1}$$$$\implies P_{i}a_i\ge (cP_{i}(c)-P_{i-1})a_{i-1}=P_{i+1}(c)a_{i-1}$$as desired. We continue this until we get $P_{n}(c)a_n\ge P_{n+1}(c)a_{n-1}$. Combining with $a_{n-1}\ge ca_n$, we need $$P_{n}(c)\ge cP_{n+1}(c)\implies P_{n+2}(c)\le 0$$Writing $c=2\cos\theta$, $0<\theta<\frac{\pi}{2}$, since we know $0<c<2$, we get $\sin (n+2)\theta\le 0$. So, $n$ has minimum $1$ when $\theta\ge\frac{\pi}{3}$, $n$ has minimum $2$ when $\frac{\pi}{4}\le\theta <\frac{\pi}{3}$, and so forth. In general, the minimum is $n$ if $$\frac{\pi}{n+2}\le \theta< \frac{\pi}{n+1}\implies n+1<\frac{\pi}{\cos^{-1}(c/2)}\le n+2$$which gives our initial answer, as $\deg(f)=n+2=\left\lceil\frac{n}{\cos^{-1}(c/2)}\right\rceil$.

Let $f(n) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0$. We claim the answer is $\left\lceil \frac{\pi}{\cos^{-1} \left(\frac{c}{2}\right)} \right\rceil$. Claim: We must have $c < 2$. Proof: Assume that $c \ge 2$. Then, we have $\left(\frac{c}{2}\right)^2 - c \frac{c}{2} + 1 \le 0$, but we also know that \[ \frac{f \left(\frac{c}{2}\right)}{g\left(\frac{c}{2}\right)} > 0\]since $\frac{c}{2}$ is positive and $f$ and $g$ have nonnegative integer coefficients. Thus, we must have $c<2$. $\blacksquare$ Claim: The degree of $f$ is at least $\frac{\pi}{\cos^{-1} \left(\frac{c}{2}\right)}$. Proof: For $c <2$, the roots of $x^2 - cx + 1$ are of the form $\cos \theta \pm i \sin \theta$ where $c = 2 \cos \theta$. We can rewrite the given equation as $(x^2-cx+1)g(x) = f(x)$ and plug in $\cos \theta + i \sin \theta$. We obtain $f(\cos \theta + i \sin \theta) = 0$. The imaginary part of this is \[ \sum_{k=0}^n a_k \sin (k \theta)=0.\]For $n< \frac{\pi}{\cos^{-1} \left(\frac{c}{2}\right)}$, $\sin (k\theta)$ is always positive and $a_k$ is nonnegative, so this is not possible. $\blacksquare$ We can provide a construction for the degree of $n=\left\lceil \frac{\pi}{\cos^{-1} \left(\frac{c}{2}\right)} \right\rceil$. We can let \[ g(x) = x^{n-2} + \frac{\sin (2\theta)}{\sin \theta} x^{n-1} + \frac{\sin (3\theta)}{\sin \theta} x^{n-2} + \cdots + \frac{\sin((n-1)\theta)}{\sin \theta} .\]The coefficient of $x^i$ in $(x^2 - 2\cos (\theta) x+ 1)g(x)$ where $2 \le i \le n-1$ is \[ \frac{\sin((n+1-i)\theta)}{\sin \theta} - 2 \cos \theta \frac{\sin ((n-i)\theta)}{\sin \theta} + \frac{\sin ((n-i-1)\theta)}{\sin \theta} = 0\]since $\sin((n+1-i)\theta) + \sin ((n-i-1)\theta) = 2 \cos \theta \sin ((n-i)\theta)$. We then obtain that \[ (x^2 -2 \cos (\theta) x+ 1) g(x) = x^n - \frac{ \sin (n\theta)}{\sin \theta} x+ 1 .\]which has nonnegative coefficients for our value of $n$.

Oops I saw the answer(not the solution though) then I actually partially solved it lol(but didn't do equality case). Such a beautiful problem, unfortunately IDK how to do equality case, can someone give me hints for that? Thanks. Firstly, let $f(x) = a_nx^n+a_{n-1}x^{n-1}+\cdots + a_1x+a_0$. We will always use this notion throughout this work. Claim: For $c\geq 2$ no $f, g$ exist. Proof: Note that plugging in $x = 1$ implies $2 - c = \frac{f(1)}{g(1)}$. Since $f(x), g(x)\in \mathbb{Z}_{\geq 0}[x]$, we have $f(1), g(1)\geq 0$. If $c > 2$ then $2-c < 0$ and in order for $\frac{f(1)}{g(1)}$ to be negative, one of $f(1), g(1)$ is negative. However that is absurd since we already have $f(1), g(1) \geq 0$. If $c = 2$ then $2-c = 0$ so it follows that $f(1) = 0$. But $f(1) = \sum_{k=0}^{n}a_k\geq 0$, so it follows that $a_0 = a_1 = a_2 = a_3 = \cdots = a_{n-1} = a_n = 0$, so $f \equiv 0$. That implies $x^2-cx+1 = 0$ for all $x$ which is absurd. Claim: For $c < 2$, we have the minimum possible degree of $f$ is $\left \lceil \frac{\pi}{\arccos\left(\frac{c}{2}\right)}\right \rceil$. Here, $\arccos$ takes its principal value. Half-Proof(no construction): Note that $g\not \equiv 0$ since that would imply that the RHS is undefined. With this in mind, we multiply both sides by $g(x)$ to get $g(x)(x^2-cx+1) = f(x)$. By the quadratic formula, we have the roots of $x^2-cx+1$ are $\frac{c\pm \sqrt{c^2-4}}{2}=\frac{c}{2}\pm \sqrt{\frac{c^2}{4} - 1}$, but since $c < 2$, we have this is equal to $\frac{c}{2}\pm i\sqrt{1-\frac{c^2}{4}}$. Now note that the magnitude of these roots is invariant - it's always $1$. Thus we have these roots can be written as $e^{ip}$ and $e^{-ip}$ for $0< p < \pi$(the $\pi$ instead of $2\pi$ since if $\pi< p < 2\pi$, we can swap $p$ for $-p$, also its $<$ instead of $\geq$ since $p = 0$, $p = \pi$ imply $c = -2, 2$ resp. both which do not work as we are given $c>0$ and we showed if $c\leq 2$ then no solutions) since one of them is the conjugate of another. It follows that $\cos(p) = \frac{c}{2}\implies 2\cos(p) = c\implies p = \arccos\left(\frac{c}{2}\right)$, where $\arccos$ takes its principal value. Thus we have $g(x)(x-e^{ip})(x-e^{-ip}) = f(x)$ so since $g\not \equiv 0$, we must have $f(e^{ip}) = 0$, so $$\sum_{k=0}^{n}a_ke^{ikp} = 0.$$Now assume for the sake of contradiction that $\deg(f) < \left \lceil \frac{\pi}{\arccos\left(\frac{c}{2}\right)}\right \rceil = \left \lceil \frac{\pi}{p}\right \rceil$. Then we have $0\leq kp<\pi$ for all $0\leq k\leq n$. Now note that $\text{Im}\left(\sum_{k=0}^{n}a_ke^{ikp}\right) = \sum_{k=0}^{n}a_k\sin(kp)$. However since $0\leq kp < \pi$ we have $\sin(kp) > 0$,and we are given $a_k > 0$, thus $\sum_{k=0}^{n}a_k\sin(kp) > 0$ so we can't have $f(e^{ip}) = 0$. Thus we must have $\deg(f)\geq \left \lceil \frac{\pi}{\arccos\left(\frac{c}{2}\right)}\right \rceil$. Now I need equality case to show that lower bound can be achieved - can somebody please help? Just a hint though thanks

Nice problem! Solved with nukelauncher. If \(c\ge2\), we would have \(f(1)/g(1)\le0\), which is absurd, so no \(f\), \(g\) exist. For \(0<c<2\), let \(c=2\cos\theta\) for \(0<\theta<\pi/2\). The answer is \(\lceil\pi/\theta\rceil\). In what follows, we let \begin{align*} f(x)&=a_0+a_1x+a_2x^2+\cdots+a_nx^n,\\ g(x)&=b_0+b_1x+b_2x^2+\cdots+b_{n-2}x^{n-2}. \end{align*} \bigskip Proof that \(n\ge\pi/\theta\): Observe that \(e^{i\theta}\) is a root of \(x^2-(2\cos\theta)x+1\), so \(e^{i\theta}\) is also a root of \(f\). Taking the imaginary part, \[0=\operatorname{Im}\left(e^{i\theta}\right)=\sum_{k=1}^na_k\sin(k\theta).\](The summation starts at \(k=1\) since \(a_k\sin(k\theta)=0\) at \(k=0\).) But note that if \(n<\pi/\theta\), then \(\sin(k\theta)>0\) for \(1\le k\le n\), which is absurd unless \(n=0\). In that case, \(f\) is constant, contradiction. \bigskip Construction for \(n=\left\lceil\pi/\theta\right\rceil\): With this choice of \(n\), we have \(\sin(k\theta)>0\) for \(1\le k\le n-1\) and \(\sin(n\theta)\le0\). I claim that selecting \(b_k=\sin( (k+1)\theta)\) for \(0\le k\le n-2\) works. (Note that all these \(b_k\) are nonnegative.) For convenience, let \(b_j=0\) for \(j<0\) and \(j>n-2\). Observe that \(a_{k+1}=b_{k+1}+b_{k-1}-(2\cos\theta)b_k\), so for \(f\) to have nonnegative coefficients, it is sufficient to verify \[b_{k+1}+b_{k-1}\ge(2\cos\theta)b_k\quad\text{for all }0\le k\le n-2.\]Indeed, most of these are sharp: the three statements below verify the hypothesis for \(k=0\), \(1\le k\le n-3\), and \(k=n-2\) respectively: \begin{align*} (2\cos\theta)b_0&=2\cos\theta\sin\theta=\sin2\theta=b_1;\\ (2\cos\theta)b_k&=2\cos\theta\sin( (k+1)\theta)=\sin( (k+2)\theta)+\sin(k\theta)=b_{k+1}+b_{k-1};\\ (2\cos\theta)b_{n-2}&=2\cos\theta\sin( (n-1)\theta)=\sin( (n-2)\theta)+\sin(n\theta)\le\sin( (n-2)\theta)=b_{n-3}. \end{align*} In conclusion, \[\Big[x^2-(2\cos\theta)x+1\Big]\cdot\left[\sum_{k=0}^{n-2}\sin( (k+1)\theta)\cdot x^k\right]=\sin(\theta)-\sin(n\theta)\cdot x^{n-1}+\sin( (n-1)\theta)\cdot x^n,\]as desired.

@above thx for showing how to get to the construction.

Really nice problem! For $c<2$, the minimum degree of $f$ is the ceiling of the value $$\frac{\pi}{\arccos(\frac{c}{2})},$$and no such polynomials $f,g$ exist for $c \geq 2$. The latter can be checked easily by taking $x=1$, from which either $f(1)$ or $g(1)$ is non-positive. Henceforth set $c = 2 \cos \theta$, and let $a_k$ be the coefficient of $x^k$ in $f$. Construction: We show that if $n \geq \pi/\theta$, then we can write $f$ and $g$ with non-negative real coefficients and degrees $n$ and $n-2$, respectively. Indeed, the polynomial $$g(x) = \sum _{k=1} ^{n-1} \sin(k\theta)x^{n-k-1}$$works, which can be checked with trig identities. Lower Bound: I now contend that we must have $n \geq \pi/\theta$. Suppose the contrary. Remark that $e^{i \theta}$ is a root of $f$, and thus evidently $f(e^{i \theta})$ must have imaginary part $0$. But note that the imaginary part of $f(e^{i \theta})$ can be also written as the sum of $a_k \sin (k \theta)$ for $k \leq n$, which are all positive by hypothesis. This yields the desired contradiction.

Clearly if $c \geq 2$ then $f, g$ do not exist as then $f(1)/g(1) = 2 - c < 0$, impossible since $f(1), g(1) > 0$ due to $f, g$ having all nonnegative real coefficients. In the case of $c < 2$, if we let $c = 2\cos{\theta}$ for some $\theta \in [0, \pi)$, then the minimum degree of $f$ is the least positive integer $n$ where $\sin{(n\theta)} \leq 0$. FTSoC suppose $n = \deg{f} < \pi/\theta$. Note that $e^{i\theta}$ is a root of $x^2 - 2\cos{\theta}x + 1$ so it must be a root of $f$. If we write\[f(x) = a_nx^n + \ldots + a_1x + a_0\]then since $f(e^{i\theta}) = 0$ we have\[\text{Re}f(e^{i\theta}) = \sum_{m = 0}^{n} a_m\cos{(m\theta)} = \text{Im}f(e^{i\theta}) = \sum_{m = 0}^n a_m\sin{(m\theta)} = 0.\]Specifically, we know that $\sin{m\theta}$ for every $m \leq n < \pi/\theta$ is $> 0$, impossible unless all $a_i$ are $0$ which would absurdly imply $f$ constant. So indeed, the bound $n \geq \pi/\theta$ is necessary. Now, letting $N$ be the described least $n$ for which $\sin{(n\theta)} \leq 0$, we provide a construction. I claim that the polynomial\[g(x) = \sum_{m = 0}^{N-2} \left(\frac{\sin{((N-1-m)\theta)}}{\sin{\theta}}\right)x^m\]yields a valid $f(x) = (x^2 - 2\cos{\theta} + 1)g(x)$. Indeed, one can check that this yields\[f(x) = x^N - \frac{\sin{(N\theta)}}{\sin{\theta}}x + 1\]where $\tfrac{\sin{(N\theta)}}{\sin{\theta}} \geq 0$ by definition of $N$. We are done.

Solved with rama1728. 600th post (and 69th on HSO)! If $c \ge 2,$ then $(1)^2 -c(1) + 1 \le 0.$ But $f(1)/g(1)$ is positive, contradiction. If $c < 2,$ let $c = 2 \cos(\theta),$ where $\theta = \arccos(c/2).$ Note that $e^{i\theta}$ is a root of $x^2-2\cos(\theta)x+1$ and thus $f(x).$ Let $n$ be the degree of $f(x).$ If $n < \frac{\pi}{\theta}$ then each of the nonzero and nonconstant terms will have positive imaginary part in $f(e^{i\theta}).$ Thus $f(e^{i\theta})$ is imaginary, contradiction. Let $n= \left \lceil \frac{\pi}{\theta} \right \rceil.$ Then take $$f(x) = (x^2-2\cos(\theta)x+1)g(x) = (x^2-2\cos(\theta)x+1)\bigg(x^{n-2} \sin(\theta)+x^{n-3} \sin(2\theta) + \dots + \sin((n-1)\theta) \bigg).$$The coefficients in $g(x)$ are nonnegative clearly, as are the $x^n$ and $x^0$ coefficients in $f(x).$ The coefficient of $x^{n-1}$ in $f(x)$ is $\sin(2\theta) - 2\cos(\theta)\sin(\theta) = 0$ and coefficient of $x$ is $\sin((n-2)\theta)-2\sin((n-1)\theta)\cos(\theta) = -\sin(xk)$ which is nonnegative. All the other coefficients are $0$ by sum-to-product, so the conditions are satisfied. Thus, $f(x)$ has minimum degree $\left \lceil \frac{\pi}{\arccos(c/2)} \right \rceil$ if $c<2,$ and no $f,g$ exist if $c \ge 2.$

700th post!, when u see u can actualy use complex numbers xD Claim 1: $c<2$ Proof: if $c \ge 2$ then set $x=1$ to get that $0 \ge \frac{f(1)}{g(1)}$ which would mean that $f(1)=0$ which means that $f=0$ which is a contradiction. Finishing: So we need to bound $\deg f=n$ in a way, in the complex plane, u can take a exponent to a trigonometric function hence why not trying that and also another thing is that roots help so first let $c=2 \cos(\alpha)$ for $0< \alpha<\pi$ and now consider a root of $x^2-2 \cos(\alpha)x+1$ and using the quadratic formula $x=\frac{2 \cos(\alpha) \pm \sqrt{4 \cos^2(\alpha)-4}}{2}=\cos(\alpha) \pm i \sin(\alpha)$ so here we will pick the one without the negative sign becuase of our choose of $\alpha$. Now take the imaginare part on both sides of the equation and setting $x=\cos(\alpha)+i \sin(\alpha)$ and using Movire's Formula $$0=\text{Im}(f(\cos(\alpha)+i \sin(\alpha)))=\sum_{k=1}^{n}b_k \sin(n \alpha)$$Now realice that becuase we set $0<\alpha<\pi$ we have that $n \ge \frac{\pi}{\alpha}$ hence the minimun is $n=\left\lceil\frac{\pi}{\cos^{-1}(\frac{c}{2})}\right\rceil$

If $c \geq 2$ no such $(f,g)$ exist, since $f(1)/g(1)\leq 0$, which is impossible. For $c<2$, if $c=2\cos\theta $, then the minimum degree of $f$ is the least integer $n$ such that $\sin n\theta\leq 0$. Note that if some choice of $g$ works for some $c$, then that $g$ works for anything less than $c$, and likewise if $g$ doesn't work for $c$, then $g$ won't work for anything more than $c$. Suppose that $$g(x)=a_0+a_1x+\cdots+a_{n-3}x^{n-3}+a_{n-2}x^{n-2},$$where $a_i\geq 0$ for $0 \leq i \leq n-3$ and $a_{n-2}>0$. Then for $f$ to have nonnegative coefficients, it is necessary and sufficient to have all of the following inequalities: \begin{align*} a_1 &\geq ca_0\\ a_0+a_2 &\geq ca_1\\ a_1+a_3 &\geq ca_2\\ &\vdots\\ a_{n-5}+a_{n-3} &\geq ca_{n-4}\\ a_{n-4}+a_{n-2} &\geq ca_{n-3}\\ a_{n-3} &\geq ca_{n-2}. \end{align*}For $c=2\cos \tfrac{\pi}{n}$, taking $a_i=\sin \tfrac{(i+1)\pi}{n}$ works by the product to sum formulas (we have equality everywhere), which is a construction. On the other hand, suppose we drop the requirement that $a_i \geq 0$ and only require that $a_{n-2}>0$. I claim that, up to scaling, the sequence $a_i=\sin \tfrac{(i+1)\pi}{n}$ is still the only one that works for $c=2\cos \tfrac{\pi}{n}$. Suppose that some sequence $c_i:=a_i+b_i$ worked, where $b_{n-2}=0$ by scaling. Then let $k \geq 2$ be maximal such that $b_{n-k}=0$, so $b_{n-k-1}>0$. We have the inequalities \begin{align*} b_{n-k-2}&\geq cb_{n-k-1}\\ b_{n-k-3}+b_{n-k-1}&\geq cb_{n-k-2}\\ &\vdots\\ b_1+b_3&\geq cb_2\\ b_0+b_2&\geq cb_1\\ b_1&\geq cb_0, \end{align*}so the sequence $b_0,\ldots,b_{n-k-1}$ should form the coefficients of a working choice of $g(x)$ for $c$ such that $\deg g\leq n-3$. On the other hand, if we use induction, we should have already proved that if $\deg g \leq n-3$ we require $c \leq 2\cos \tfrac{\pi}{n-1}<2\cos \tfrac{\pi}{n}$ (the base cases of $n=3$ and $n=4$ are clear by manual computation), which the existence of such a $b_i$ sequence would contradict. Thus $a_i=\sin \tfrac{(i+1)\pi}{n}$ is the only choice of coefficients for $c=2\cos \tfrac{\pi}{n}$, but because equality holds we cannot increase $c$ any further with this choice of coefficients. Thus we are done. $\blacksquare$

hardest part is construction lol, i hope the motivation behind my thinking was clear, we only needed nonnegativity stuff. I'll remark that the construction might seem nontrivial, but by trig identities we KNOW that the coefficients of g would be of the form sin(O(i)theta)cos(O(i)theta), and indeed the simplest worked. not gonna lie i hope these dont appear in the future though, if they do im gnna get unlucky and not get construction. how many points does anyone think no construction is worth? maybe 3-4? for obvious reasons, c<2 and we must have n>pi/theta (by the idea that cis(theta) is a root), where c=2costheta. As is, we claim the minimal degree is $\left \lceil \frac{\pi}{\arccos(c/2)} \right \rceil$ (if c<2). For xonkstrukshin, the following should be easily bashed by hand, but for the sake of completeness ill include it. take $$\sum_{i=0}^na_ix^if(x) = (x^2-2\cos(\theta)x+1)g(x) = (x^2-2\cos(\theta)x+1)\sum_{i=1}^{n-1}x^{n-i-1}\sin(i\theta):$$$$a_{n-1}=\sin(2\theta)-2\cos(\theta)\sin(\theta)=0,a_1=\sin((n-2)\theta)-2\cos(\theta)\sin((n-1)\theta)=\tfrac12(\sin((n-2)\theta)-\sin(n\theta))$$$$\approx\tfrac12(1-(-0))>0,\forall 2\le i\le n-2,a_i=\sin((n-(i-1))\theta)-2\cos(\theta)\sin((n-i)\theta)+\sin((n-(i+1))\theta)=0$$(by the theorem of wolfram alpha of testing small cases and generalizing, since proof is easy but bashy), so they have nonnegative coefficients as claimed. i suppose evan's solution doesn't actually have that issue, but evan, u said "[f]irst we show this is necessary" but u didnt show sufficiency, id like to see other constructions; i also suppose that i didnt even read evan's solution yet (i didnt) so maybe his solution shows that a specific degree is possible without needing construction nvm he literally provided the cosntucctoion by mylutiplinyg by the cosntants, i suppose thats the mtoviation

Why do trig bounding when you can just use dot products? We claim the answer is $\deg f = \left\lceil \frac{\pi}{\cos^{-1}(c/2)} \right\rceil$ for $c < 2$ and doesn't exist for $c \ge 2$. Claim: This is impossible for $c \ge 2$. Proof. Since $c^2 \ge 4$, $x$ has a real root $r$, but $f(r) > 0$, contradiction. $\blacksquare$ Fix $n-1 < \frac{\pi}{\cos^{-1}(c/2)} \le n$ or $2\cos\left(\frac{2\pi}{2(n-1)}\right) < c \le 2\cos\left(\frac{2\pi}{2n}\right)$. Claim: Such a polynomial pair $(f, g)$ exists of degree $n$. Proof. Let \[ x^n + 1 = \left(x^2 - 2\cos\left(\frac{2\pi}{2n}\right)x + 1\right)P(x) \]The coefficients of \[ P(x) = a_{n-2}x^{n-2} + a_{n-3}x^{n-1} + \dots + 1 \]satisfy $a_{k+2} = ca_{k+1} - a_ k = 0$ where we take $a_0 = 1, a_1 = c$. We can solve this recurrence to get \[ a_k = \frac{1}{\omega - \omega^{-1}} \cdot \frac{\omega^k - \omega^{-k}}{2} = \frac{1}{\sin\left(\frac{2\pi}{2n}\right)} \sin\left(\frac{2k\pi}{2n}\right) \]so all coefficients of $P$ are positive. Then the coefficients of \[ \left(x^2 - cx + 1\right)P(x) - (x^n + 1) = \left(c - 2\cos\left(\frac{2\pi}{2n}\right)\right) P(x) \ge 0 \]are all positive which implies the result. $\blacksquare$ Claim: Such a polynomial $f$ does not exist of degree $n-1$. Proof. FTSOC suppose that $f(x) = a_{n-1} x^{n-1} + a_{n-2}x^{n-2} + \dots + a_0$. Let $t$ be a root of $x^2 - cx + 1$ in the upper half complex plane, which lies on the unit circle and between the $2n-2$th and $2n$th roots of unity. Then if we let $v_i$ denote the vector corresponding $t^i$ for $0 \le i \le n-1$, then \[ a_{n-1} v_{n-1} + a_{n-2} v_{n-2} + \dots + a_0 v_0 = 0 \]If we let $v \coloneq v_{n-1} + v_0$, then \[ a_{n-1} \langle v_{n-1}, v \rangle + a_{n-2} \langle v_{n-2}, \rangle + \dots + a_0 \langle v_0, v \rangle = 0 \]which gives a contradiction since each dot product is greater than $0$. $\blacksquare$