by Brandon Wang. The philosophy behind this is to find or create (hallucinate) an underlying structure in some process, or to put yourself in the shoes of the things happening in the problem and trying to see the problem from different viewpoints in order to solve it. I liked 2018 IMOSL C3 and 2018 USA TSTST P2. In a problem like 2018 IMOSL C3, it appears in the form of "physics", or trying to assign some real physical meaning to the things happening. Problems where one introduces gravity or colors or object types, or even another player acting as an ally or an enemy are also a good example of hallucination.
Let \(P_1\), \(P_2\), \(\dots\), \(P_{2n}\) be \(2n\) distinct points on the unit circle \(x^2 + y^2 = 1\), other than \((1, 0)\). Each point is colored either red or blue, with exactly \(n\) red points and \(n\) blue points. Let \(R_1\), \(R_2\), \(\dots\), \(R_n\) be any ordering of the red points. Let \(B_1\) be the nearest blue point to \(R_1\) traveling counterclockwise around the circle starting from \(R_1\). Then let \(B_2\) be the nearest of the remaining blue points to \(R_2\) travelling counterclockwise around the circle from \(R_2\), and so on, until we have labeled all of the blue points \(B_1\), \(\dots\), \(B_n\). Show that the number of counterclockwise arcs of the form \(R_i \to B_i\) that contain the point \((1, 0)\) is independent of the way we chose the ordering \(R_1\), \(\dots\), \(R_n\) of the red points.
Okay this is like fairly trivial because we can just swap any \(R_i\) and \(R_{i+1}\) and that doesn't change the number, so we keep doing this and win.
Let \(m\) be a positive integer. Consider a \(4m \times 4m\) array of square unit cells. Two different cells are related to each other if they are in either the same row or in the same column. No cell is related to itself. Some cells are coloured blue, such that every cell is related to at least two blue cells. Determine the minimum number of blue cells.
So I've been told the answer is \(6m\) and the construction is fairly simple. Now we want to show the bound. Using the advanced technique known as metagaming, we introduce the bipartite graph that the grid represents. Led by equality cases, note that if there are less than \(6m\) edges, some connected component exists with \(\le 3\) vertices, which is impossible.
There are \(n\ge 2\) line segments in the plane such that every two segments cross and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it facing the other endpoint. Then he will clap his hands \(n-1\) times. Every time he claps,each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will ever occupy the same intersection point at the same time.
The first part is trivial - we can just consider an odd \(n\)-gon and the extensions of its segments. In doing the second part, I realized that it is only the orientation of the segments that in fact matters, and we can simply consider the \(2\) endpoints of each segment - the decision for any \(n = 2k\) is only about which of the two endpoints we must choose. And it's trivial to show that we can't choose any two adjacent endpoints when looking at the clockwise ordering, so we have to choose either \(\{1, 3, \dots, 4k - 1\}\) or \(\{2, 4, \dots, 4k\}\). But \(1\) and \(2k + 1\) are actually on the same segment, and so are \(2\) and \(2k + 2\). So we're done.
A physicist encounters \(2015\) atoms called usamons. Each usamon either has one electron or zero electrons, and the physicist can't tell the difference. The physicist's only tool is a diode. The physicist may connect the diode from any usamon \(A\) to any other usamon \(B\). (This connection is directed.) When she does so, if usamon \(A\) has an electron and usamon \(B\) does not, then the electron jumps from \(A\) to \(B\). In any other case, nothing happens. In addition, the physicist cannot tell whether an electron jumps during any given step. The physicist's goal is to isolate two usamons that she is sure are currently in the same state. Is there any series of diode usage that makes this possible?
I reckon it's not, and the physicist basically has a fixed set of moves he can carry out in any scenario, so we're claiming that there is some configuration such that for any fixed set of moves, her algorithm doesn't work out. Indeed, understanding the \(2015 = 3\) case leads to the solution, where the configurations \(110\) and \(100\) never end up matching. Therefore we consider the set of binary representations with \(i\) ones at the start and \(2015 - i\) zeroes at the end - using the move on any ordered pair can be hallucinated of either as a swap on all the members of the set, or nothing happening on all the members. Either way, after any number of moves, nothing actually ends up happening, and we're done.
Let \(n \ge 3\) be a fixed integer. The number \(1\) is written \(n\) times on a blackboard. Below the blackboard, there are two buckets that are initially empty. A move consists of erasing two of the numbers \(a\) and \(b\), replacing them with the numbers \(1\) and \(a + b\), then adding one stone to the first bucket and \(\gcd(a, b)\) stones to the second bucket. After some finite number of moves, there are \(s\) stones in the first bucket and \(t\) stones in the second bucket, where \(s\) and \(t\) are positive integers. Find all possible values of the ratio \(t/s\).
by Victor Rong and Yufei Zhao. A short section with root sizes and primes and bounding and triangle inequalities.
Let \(f(x) = a_nx^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0\) be a polynomial with integer coefficients such that \(p \mid a_i\) for \(0 \le i < k\), \(p \nmid a_k\) and \(p^2 \nmid a_0\). Then \(f(x)\) has an irreducible factor of degree \(\ge k\).
Suppose \(f = gh\), in which case we wish to show that one of \(g\) and \(h\) have degree \(\ge k\) in any scenario. On the contrary, assume that they have both degree \(< k\), say, \(i\) and \(j\). Then taking modulo \(p\), their base terms should be of the form \(cx^{i_0}\) and \(dx^{j_0}\), where \(i_0 + j_0 = k\) and \(0 < i_0, j_0 < k\). But this means that \(p^2 \mid a_0\) must hold since we both the constant terms are divisible by \(p\).
Let \(P(x) = x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0\) be a polynomial with \(a_0 \neq 0\) and \[|a_{n-1}| > 1 + |a_{n-2}| + \dots + |a_1| + |a_0|\] Then \(P(x)\) is irreducible.
The proof is cute. As Yufei Zhao puts it, the \(a_{n-1}\) dominates the polynomial. When we take out the root \(z\) with \(|z| > 1\), as it turns out through Vieta's relations, the monic term in the remaining polynomial dominates. Thus none of the roots have size \(> 1\).
In fact, it in general holds that for a complex polynomial, if \(a_k\) is dominating the expression, then \(n - k\) roots will lie outside the unit circle, and \(k\) will lie inside it.
Let \(P(x) = a_0 + a_1 x + \dots + a_nx^n\), where \(0 < a_0 \le a_1 \le \dots \le a_n\) are real numbers, then any complex zero of the polynomial satisfies \(|z| \le 1\). Moreover, for any polynomial \(Q(x) = b_0 + b_1 x + \dots + b_nx^n\) with positive real coefficients, all its zeroes lie in the annulus \[\min_{1 \le k \le n} \frac{a_{k-1}}{a_k} \le | z| \le \max_{1 \le k \le n} \frac{a_{k-1}}{a_k}\]
Remember that to bound you realistically need some negative terms. So you can just generate them out of nowhere! For instance, since you wish to keep the original polynomial and add some negative terms, you can look at 'equality cases' (like very loose ones) and just multiply by \(1 - z\) and be done with it.
Let \(f\) and \(g\) be two nonzero polynomials with integer coefficients and \(\deg f > \deg g\). Suppose that for infinitely many primes \(p\) the polynomial \(pf + g\) has a rational root. Prove that \(f\) has a rational root.
So we have arbitrarily large primes \(\{p_i\}\) and the corresponding rational numbers \(\{r_i\}\) such that \[f(r_i) = \frac{- g(r_i)}{p_i}\] These rationals \(r_i\) must be pretty small, as in, they must be in the range where \(f\) still has roots, because otherwise \(f(r_i)\) would dominate \(g(r_i)\) due to degree reasons. Okay, right, so if \(f\) doesn't have a rational root, then we have these \(r_i\) that are 'near' roots, but then we have infinitely many such \(r_i\), so they must apparently be near some rational root of \(f\) or something? I suppose this is the main idea that we have to formalize.
I also want to use rational root theorem at some point. Using it now tells me that if \(r_i = x_i / y_i\), then \(y_i \mid p_i f_n\) and \(x_i \mid p_i f_0 + g_0\), where \[f(x) = f_nx^n + \dots + f_1x + f_0, \;\;\;\; g(x) = g_mx^m + \dots + g_1 x + g_0\] If \(y_i \mid f_n\) then there are only finitely many values \(y_i\), and since \(r_i\) is bounded, there are finitely many values for \(x_i\) and thus \(r_i\). This is certainly a problem if it happens often since the infinite set \(\{p_i\}\) is defined through the infinite set \(\{r_i\}\) as \(p_i = - g(r_i) / f(r_i)\). Therefore, \(y_i \mid p_i\) infinitely often. In fact, if we can choose a subsequence of \(\{r_i\}\) that converges, say to \(R\), then \[\frac{-f(r_i)}{g(r_i)} \to \frac{1}{\infty} = 0\] which means that \(R\) is a root of \(f\).
But how do we know this \(R\) is rational? Let us consider the \(r_i = x_i / y_i\) that lead to it. We can assume that \(y_i \mid p_i\) holds for all \(r_i\). If \(y_i = 1\) infinitely often, then \(r_i \in \mathbf{Z}\), which is fine, since then \(R \in \mathbf{Z}\). Otherwise, we can consider \(y_i = p_i\) to always be true. But now we have a small problem when considering a large prime undisturbed by the coefficients of \(g\) and \(f\), in the equation \[f(x_i / p_i) = \frac{-g(x_i / p_i)}{p_i}\] Here we know something like \(\nu_{p_i}(f(x_i / p_i)) = -n\), and \(\nu_{p_i}(g(x_i/p_i)) = -m\), so \(n = m + 1\). \[p_i(f_n(x_i / p_i)^n + \dots + f_1 (x_i / p_i) + f_0) + (g_{n - 1} (x_i / p_i)^{n-1} + \dots + g_1 (x_i / p_i) + g_0) = 0\] \[f_n x_i^n + g_{n-1} x_i^{n-1} \equiv 0 \pmod{p_i} \implies x_i \equiv -g_{n-1} / f_n \pmod{p_i}\] But this means that \[\frac{x_i}{p_i} = z_i - \frac{g_{n-1} / f_n}{p_i}\] for some \(z_i \in \mathbf{Z}\). And since \(p_i \to \infty\) while \(g_{n-1} / f_n\) is a constant, what matters is \(z_i\), and we know that convergent integer sequences are eventually constant, so there's that.
"Why things are true" style NT with a focus on "take large".
Find all pairs of positive integers \(m\), \(n \ge 3\) for which there exist infinitely many positive integers \(a\) such that \[\frac{a^m + a - 1}{a^n + a^2 - 1}\] is itself an integer.
It's clear that \(a^n + a^2 - 1\) must divide \(a^m + a - 1\) as polynomials, so for any root \(r\) of the former, it must be a root of the latter. Indeed, we must have that if \(r^n + r^2 = 1\), then \(r^m + r = 1\) holds as well. \[r^m + r = r^n + r^2 \implies r^n(1 - r^{m - n}) = r(1 - r) \implies r^{m - n + 1} + r^{m - n} = 1\] which means \(m - n + 1 \le n\) and so \(m \le 2n - 1\). Now we're kind of at a dead end. But we're actually not, because we actually have \[r^n + r^2 = 1 \implies r^{m - n + 1} + r^{m - n} = 1\] This means that \(a^n + a^2 - 1 \mid a^{m - n + 1} + a^{m - n} - 1\), and since \(m \le 2n - 1\), this means that \(m - n = 2\), \(n = 3\), \(m = 5\), which works.
Interplay between playing with numbers from a Euclid-style viewpoint and looking at them as roots of a polynomial. They have opposite effects to each other in terms of bounding here, which is to be kept in mind.
by Evan Chen. Continuation of previous section.
Let \(P(x) \in \mathbf{Q}[x]\) be a nonconstant irreducible polynomial of degree \(n\). Prove that the number of polynomials \(Q(x)\) of degree less than \(n\) with rational coefficients such that \(P(x)\) divides \(P(Q(x))\) is at most \(n\).
Prove that if \(m\), \(n\) are relatively prime positive integers, \(x^m - y^n\) is irreducible in \(\mathbf{C}[x, y]\). Indeed, prove that if \(f\) and \(g\) are polynomials with complex coefficients and coprime degrees, then \(f(x) + g(y)\) is irreducible in \(\mathbf{C}[x, y]\).
Let \(f \in \mathbf{Z}[x]\) be a monic polynomial and let \(a\) be a nonzero integer. Prove that for all sufficiently large positive integers \(q\), the polynomial \[(x - q)f(x) + a\] is irreducible over the integers.
by Rijul Saini, and others.
Let \(S\) be a finite set of complex numbers with modulus \(1\). Show that there exists a complex polynomial \(f(z)=a_nz^n+a_{n-1}z^{n-1}+\cdots +a_0\), such that \(|a_0|=|a_1|=\cdots =|a_n|=1\), and \[\left\{z\in\mathbb C\mid f (z)=0,|z|=1\right\}=S\]
Let \(n > 1\) be an integer, and let \(k\) be the number of distinct prime divisors of \(n\). Prove that there exists an integer \(a\), \(1 < a < \frac{n}{k} + 1\), such that \(n \mid a^2-a\).
Given a positive integer \(n\) and \(x_1 \leq x_2 \leq \ldots \leq x_n\), \(y_1 \geq y_2 \geq \ldots \geq y_n\), satisfying \[\sum_{i = 1}^{n} ix_i = \sum_{i = 1}^{n} iy_i\] Show that for any real number \(\alpha\), we have \[\sum_{i =1}^{n} x_i \lfloor i\alpha \rfloor \geq \sum_{i =1}^{n} y_i \lfloor i\alpha \rfloor\]
Let \(x_1\), \(x_2\), \(\ldots\), \(x_n\) be real numbers such that \(|x_1 + x_2 + \ldots + x_n| = 1\) and \(|x_i| \le (n+1)/2\) for all \(i \in [1, n]\). Show that there exists a permutation \(\{y_i\}\) of \(\{x_i\}\) such that \[ | y_1 + 2 y_2 + \cdots + n y_n | \leq \frac {n + 1}{2}. \]
Prove that there exists \(N\) such that if an irreducible polynomial \(p(x) \in \mathbf{Q}[x]\) has all its roots lying inside a disc of radius $0.99$ (not necessarily centered at origin) then \(\deg p < N\).
courtesy of Yousuf.
Consider all the functions \(f : \mathbf{N} \to \mathbf{N}\) such that \(f(f(n) + n) =n\) and \(f(a + b - 1) \le f(a) + f(b)\) for all positive integers \(a\), \(b\), \(n\). Prove that there are at most two values for \(f(2022)\).
Suppose that there exists a nonempty set \(X \subset \mathbf{R}\) and a function \(f : X \to X\) satisfying \[f(x) + y \in X \iff x \neq y\] for every \(x\), \(y \in X\). Prove that \(f(x) + x\) is constant while \(x\) varies in \(X\).
Let functions \(f, g : \mathbf{Z} \to \mathbf{Z}\) satisfy \[f(g(x) + y) = g(f(y) + x)\] for all integers \(x\), \(y\). If \(f\) is bounded, prove that \(g\) is periodic.
Determine whether there exists a function \(f : \mathbf{N} \to \mathbf{N}\) such that for all naturals \(m\) and \(n\), \[f(m + nf(m)) = f(n)^m + 2024! \cdot m\]
Plugging in \(m = 1\), we obtain \[f(nf(1) + 1) = f(n) + 2024!\] This means that if we have some \(f(n) \equiv k \pmod{2024!}\), then all numbers larger than \(f(n)\) that are \(k \pmod{2024!}\) are in the image of \(f\). In fact, if we have some appropriate residue set \(k\) somehow, then we can establish surjectivity for large numbers by varying \(m\) and obtaining every single residue. Basically, we have large number surjectivity over all residues covered by \(f(n)^m\). Pursuing surjectivity seems useless because we're looking for a more size-based contradiction, intuitively. Anyway, trying traditional FE things, suppose we can get \(af(1) + 1 = bf(2) + 2\) for some \(a\), \(b\) - that would mean \[f(a) + 2024! = f(b)^2 + 2 \cdot 2024!\] So we get a power difference, which we can possibly use to our advantage by instead having \(af(1) + 1 = bf(k) + k\): \[f(a) + 2024! = f(b)^k + k \cdot 2024!\] But I can't exactly tell what's happening without knowing whether I can set things like this or not: \[\frac{bf(k) + k - 1}{f(1)} = a\] Indeed, if I let \(f(1) \mid k - 1\) and \(f(1) \mid b\), then this is very possible. So we get \[f(a) - f(b)^k = (k - 1) \cdot 2024!\] But wait, though this means not much as it is, if we use \(f(2)\) instead of \(f(1)\) we obtain \[f(a)^2 - f(b)^k = (k - 2) \cdot 2024!, \;\; f(a) - f(b)^{k/2} \ge 1 \implies (k - 2) \cdot 2024! \ge f(b)^{k/2}\] Indeed, this means that for every large multiple \(b\) of \(f(2)\), \(f(b) = 1\). Looking again at what we have, \[f(a)^2 - 1 = (k - 2) \cdot 2024!\] for \(k \equiv 2 \pmod{f(2)}\). But consider now \(k - 2 = f(2) p\) for an unimaginably large prime \(p\). That would give \((f(a) - 1)(f(a) + 1) = p \cdot f(2) \cdot 2024!\) which is absurd.
Let \(f : \mathbf{N} \to \mathbf{N}\) be such that for every \(n \in \mathbf{N}\) there exists \(k \in \mathbf{N}\) for which \(f^{2k}(n) = n + k\). If \(k_i\) is the smallest such \(k\) for \(n = i\), prove that the sequence \(\{k_i\}\) is unbounded.
by Victor Rong.
Let \(P \in \mathbf{Z}[x]\) be nonconstant and let \(n\) be a positive integer. Assume for every positive integer \(b\), the sequence \[n, \; P(n), \; P(P(n)), \; \cdots, \; P^i(n), \; \cdots\] contains a \(b\)th power of an integer greater than \(1\). Show that \(P(x)\) is linear.
Let the sequence be named \(p_0\), \(p_1\), \(\dots\), so that \[p_1 - p_0 \mid p_2 - p_1 \mid \dots\] and indeed \(p_j \equiv p_i \pmod{p_{i+1} - p_i}\) for all \(j \ge i\). Since someone is an actual \(b\)th power, everyone is, modulo \(p_{i+1} - p_i\) for all large \(b\). We would like to use \(\phi(p_{i+1} - p_i)\) but there are coprime shenanigans, so we'd rather just take the prime powers dividing \(p_{i+1} - p_i\) individually. This yields \[p_{i+1} - p_i \mid p_x(p_x - 1)\] for all \(x\), and is especially useful for \(x = i\) from a degree perspective - it eliminates all polynomials of degree \(\ge 2\).
So we are now left to consider polynomials of the form \(ax^2 + bx + c\). But now \[P(x) - x \mid x^2 - x\] for infinitely many \(x\), so if \(P\) has degree \(2\), then \(P(x) - x = x^2 - x\) or \(x - x^2\). This means \(P(x) = x^2\) or \(P(x) = -x^2 - 2x\), both of which clearly cannot work.
Let \(P \in \mathbf{Z}[x]\) be nonconstant. Prove that there is no function \(T : \mathbf{Z} \to \mathbf{Z}\) such that the number of integers \(x\) with \(T^n(x) = x\) is equal to \(P(n)\) for all \(n \ge 1\).
I have an idea - consider \(T^p(x) = x\) for some prime \(p\) - this consists of the numbers which are in a cycle of length \(p\), and the numbers that are standalone fixed points. Thus we get \[p \mid P(p) - P(1) \implies p \mid P(1) - P(0)\] This is true for all \(p\), so \(P(1) = P(0)\) must be true. Now consider \(T^{pq}(x) = x\) for primes \(p\), \(q\). If \(C_i\) denotes the number of numbers in a minimum cycle of length \(i\), then we get \[P(pq) = C_{pq} + C_p + C_q + C_1 = C_{pq} + C_q + P(p)\] \[q \mid C_{pq} + C_q = P(pq) - P(p) \implies q \mid P(p) - P(0)\] Now varying \(q\), this tells us that \(P(p) = 0\), and varying \(p\), the polynomial \(P\) is zero at infinitely many points and thus identically so, a contradiction.
Find all \(p \in \mathbf{R}[x]\) for which there exists \(q \in \mathbf{R}[x]\) such that \[p(1) + p(2) + \dots + p(n) = p(n) q(n)\] for all positive integers \(n\).
Taking the integral, we obtain that \(\deg q = 1\) and the leading coefficient is \(\frac{1}{d+1}\) where \(d\) is the degree of \(p\). We have \(p(1) = p(1)q(1)\), which means that either \(p(1) = 0\) or \(q(1) = 1\). Also note that \(p(n+1) = p(n+1)q(n+1) - p(n)q(n)\) for all \(n\), or rather \[p(n+1) = p(n+1)\left( q(n) + \frac{1}{d+1} \right) - p(n)q(n) = (p(n + 1) - p(n))q(n) + \frac{p(n+1)}{d+1}\] \[\frac{dp(n+1)}{d+1} = q(n) (p(n+1) - p(n))\] Indeed, this must hold for all real and complex \(n\), which means the roots on the LHS and the RHS are the same - \(p(n+1)\) and \(p(n)\) have the same roots save one. This means that \(p(x)\) is built like \[p(x) = (x - a + 1)(x - a + 2) \dots (x - a + d)\] Now if \(q(1) = 1\), then we know that \(q(x) = \frac{x+d}{d+1}\) and \(p(x) = x(x + 1) \dots (x + d - 1)\). If \(p(1) = 0\), then \(p(x)\) has some \(d - 2\) choices, and \(q(x)\) can be appropriately made.
Let \(n\) be a positive integer and \(a_1\), \(a_2\), \(\dots\), \(a_n\) be non-zero reals. What is the least number of nonzero coefficients that the polynomial \[P(x) = (x - a_1) (x - a_2) \dots (x - a_n)\] can have?
Let's work through the small cases - if \(n = 1\), then there must be \(2\) nonzero coefficients. If \(n = 2\), there must be \(2\) nonzero coefficients still, with \((x - a)(x + a)\). If \(n = 3\), for the polynomial \((x - a)(x - b)(x - c)\), we want \(ab + bc + ca = 0\) and \(a + b + c = 0\) simultaneously, or \[ab = (a + b)^2 \implies a^2 + ab + b^2 = 0 \implies b \in \{a \omega, a \omega^2\}\] which is not possible. So for \(n = 3\), there must be \(3\) nonzero coefficients. For \(n = 4\), we are looking at the quantities \[abcd, \;\; abc + abd + acd + bcd, \;\; ab + ac + ad + bc + bd + cd, \;\; a + b + c + d\] \[(a + b + c + d, abc + abd + acd + bcd) = (0, 0) \implies abc = (ab + bc + ca)(a + b + c) \implies (a + b)(b + c)(c + a) = 0 \] which is fine. \[(a + b + c + d, ab + ac + ad + bc + bd + cd) = (0, 0) \implies ab + bc + ca = (a + b + c)^2 \implies (a + b)^2 + (b + c)^2 + (c + a)^2 = 0\] btu this is bad and leads to no progress. \[(abc + abd + acd + bcd, ab + ac + ad + bc + bd + cd) = (0, 0) \implies \frac{ab+bc+ca}{abc}= \frac{a+b+c}{ab+bc+ca} \implies a^2 (b+c)^2 + b^2 (c+a)^2 + c^2 (a+b)^2 = 0\] This is once more bad. So it seems that the answer for \(n = 4\) is \(3\). It seems like the answer is \(\lceil n/2 \rceil + 1\) and I think I've figured out why - it might be that two adjacent symmetric polynomials cannot together be \(0\). If this is the case, then all that remains for us is the construction. Indeed, let \(S(n, k)\) be the symmetric sum of \(n\) variables taken \(k\) at a time - we then wish for \(S(n, k + 1) = S(n, k) = 0\) for some \(k\). This would mean \[\frac{S(n - 1, k + 1)}{S(n - 1, k)} = \frac{S(n - 1, k)}{S(n - 1, k - 1)} \implies S(n - 1, k)^2 = S(n - 1, k - 1) S(n - 1, k + 1)\]
Oh, but instead of doing this, since we really want to induct, we can just do so from the coefficients point of view - note that the derivative is something that has the 'same' coefficients as the original polynomial and must have all real roots when our polynomial has all real roots. Since we know that if the polynomial is \(f(x) = x^n + \dots + a_2 x^2 + a_1 x + a_0\) then \(a_1\) and \(a_2\) cannot simultaneously be \(0\), we can take cases and either \(f'\) or \(f''\) gives us a working induction.
In fact, Newton's inequality states that for the weighted real symmetric sums \(D(n, k) = S(n, k)/\binom{n}{k}\): \[D(n, k) \ge D(n, k -1) D(n, k+1)\] or, rewritten, \[S(n, k) \ge \frac{(k+1)(n-k+1)}{k(n-k)} S(n, k-1) S(n, k+1)\] and can be proven inductively.
Prove that any real polynomial of the form \(1 + a_n x^n + a_{n+1} x^{n+1} + \dots + a_k x^k\) for \(k \ge n\) has at least \(n - 2\) non-real roots (counting multiplicity), where \(a_k \neq 0\).
Note that the derivative of this polynomial is \[n a_n x^{n-1} + (n+1)a_{n+1} x^{n} + \dots + k a_k x^{k-1} = x^{n-1} ( \dots + k a_k x^{k - n} )\] Indeed, if there are at most \(n - 3\) non-real roots to the original polynomial, then there are at least \(k - n + 3\) real roots. If there are \(r\) roots positive and \(s\) roots negative so that \(r + s = k - n + 3\) (since no roots are at \(0\)), interlacing tells us that there are at least \(k - n + 1\) nonzero roots in the derivative. But there are clearly at most \(k - n\) such roots, and we are done.
by Dragomir Grozev.
Let \(a_1\), \(a_2\), \(\dots\), \(a_n\) be a sequence of real numbers, and let \(m\) be a fixed positive integer less than \(n\). We say an index \(k\) with \(1\le k\le n\) is good if there exists some \(l\) with \(1 \le l \le m\) such that \[a_k+a_{k+1}+ \cdots +a_{k+l-1} \ge 0\] where the indices are taken modulo \(n\). Let \(T\) be the set of all good indices. Prove that \[\sum_{k \in T} a_k \ge 0\]
The first thing you think of works. 0 MOHS.
Let \(a_1\), \(a_2\), \(\dots\), \(a_n\) be a sequence of nonnegative integers. For \(k = 1\), \(2\), \(\dots\), \(n\), denote \[ m_k = \max_{1 \le l \le k} \frac{a_{k-l+1} + a_{k-l+2} + \cdots + a_k}{l}. \] Prove that for every \(\alpha > 0\) the number of values of \(k\) for which \(m_k > \alpha\) is less than \[ \frac{1}{\alpha} \sum_{i=1}^n a_i \]
Let \(n\) be a positive integer and \(a_1\), \(a_2\), \(\ldots\), \(a_{2n+1}\) be positive reals. For \(k=1\), \(2\), \(\ldots\), \(2n+1\), denote \[b_k = \max_{0\le m\le n}\left(\frac{1}{2m+1} \sum_{i=k-m}^{k+m} a_i \right)\] where indices are taken modulo \(2n+1\). Prove that the number of indices \(k\) satisfying \(b_k\ge 1\) does not exceed \[2\sum_{i=1}^{2n+1} a_i\]