Observe that $Q(r_1, \dots, r_n)=\prod_{i<j} (r_i-r_j)$ divides $P$ so we can write $P =QR$ for some polynomial $R$. By a well-known property of the Vandermonde determinant, $Q$ consists of $n!$ monomials of the form $r_1^{\pi (1)} r_2^{\pi(2)}\dots r_n^{\pi (n)}$, one for every permutation $\pi$ on $[1,2,\dots, n]$. It follows the Newton Polytope of $Q$ contains $n!$ vertices (all of the form $(\pi(1), \dots, \pi(n))$ for permutations $\pi$). But it’s well-known (see the link) that since $P=QR$ we have $\text{Newt} (P) = \text{Newt} (Q) + \text{Newt} (R )$, where $+$ denotes the Minkowski sum operation on polytopes. Since the number of vertices of a polytope cannot decrease via the Minkowski sum operation, it follows $\text{Newt} (P)$ has at least $n!$ vertices, so $P$ contains at least $n!$ nonzero terms. For more resources on the combinatorial properties of polytopes, check out the homepage for the MIT Spring 2020 course Topics in Combinatorics: Polytopes and Hyperplane Arrangements YUH.

Mine! Here's the solution I came up with, which is somewhat tricky. I can't say I expected this to appear only on JMO... in my opinion this problem is quite technical for the JMO pool (and not even that easy). Call such polynomials regular. We proceed by induction on $n$, with base case $n = 2$ obvious. Let $P(x_1, \dots, x_n)$ be a regular polynomial; without loss of generality suppose $P$ is not divisible by any of $x_1, \dots, x_n$. Claim. No term of $P$ can have zero degree in two variables. Proof. Suppose term $t$ of $P$ has zero degree in $x_i$ and $x_j$. Then $t$ cannot be cancelled upon setting $x_i = x_j$. $\square$ Let $S_k$ be the set of terms of $P$ having zero degree in $x_k$; let $P_k$ be the polynomial composed of the terms in $S_k$. By the claim, $S_1, \dots, S_n$ are pairwise disjoint (and nonempty by assumption). It is also apparent that each $P_k$ is regular (as an $(n-1)$-variable polynomial). Thus each $|S_k| \ge (n-1)!$ by inductive hypothesis and so $P$ contains at least $|S_1| + \dots + |S_k| \ge n \cdot (n-1)! = n!$ terms.

How much points would we get for doing a bunch of stuff with induction?

Emathmaster wrote: how much points would we get for doing a bunch of stuff with induction? Pretty much what I did lol. I proved the Vandermonde determinant (@3above) using induction because I didn't know it existed. And I got that $\pi$ is a permutation on [0, 1,..., n-1] and not [1, 2, ...n]. From there, given some term in Q (still using @3above's notation, I showed that we can multiply some term in Q (WLOG $r_1^{n-1}r_2^{n-2}...r_n^0$) by the term in R with the highest degree of $r_1$. If there's multiple terms in R with the same highest degree of $r_1$, take the term with the higher degree of $r_2$, then $r_3$, and so on. Multiplying this term by $r_1^{n-1}r_2^{n-2}...r_n^0$ will trivially give a term that cannot be canceled out with anything else in the product QR (no other term in QR will have the same degrees of $r_i$ for all i. Since Q has $n!$ monomials and each term in Q generates at least one term in QR, then P has at least $n!$ monomials.

A cute problem imho; break it into the following three natural steps: (I index always from $0$ and identify naturals (of which $0$ is the first) with the set of naturals strictly less than them when appropriate (i.e., $0=\emptyset$).) Given natural $n\colon\mathbb{N}$, Claim 1: For characteristic $0$ integral domain $R$, if polynomial $p\colon R\left[x_{0},x_{1}\right]$ is such that $p\colon\prod_{i\colon 2}R\to R$ vanishes whenever the two inputs agree, then $p$ is divisible by $x_{i_{2}}-x_{i_{1}}$.

Corollary: If polynomial $p\colon\mathbb{R}\left[x_{i}\right]_{i\colon n}$ is such that for any nonidentical $i_{1},i_{2}\colon n$, the function $p\colon\prod_{i\colon n}\mathbb{R}\to\mathbb{R}$ vanishes whenever the inputs in index $i_{1}$ and $i_{2}$ agree, then $p$ is divisible by $\prod_{i_{1}<i_{2},\ i_{1},i_{2}\colon n}x_{i_{2}}-x_{i_{1}}$. Hint: As a ring of polynomials over a UFD, $\mathbb{R}\left[x_{i}\right]_{i\colon n}$ is itself a UFD. Claim 2: Denote by $\text{Aut}\left(n\right)$ the group of permutations $n\to n$, and by $\text{sgn}\colon\text{Aut}\left(n\right)\to\mathbb{Z}^{\times}$ the canonical signature mapping thereof. One has that $$\prod_{i_{1}<i_{2},\ i_{1},i_{2}\colon n}\left(x_{i_{2}}-x_{i_{1}}\right)=\sum_{\sigma\colon\text{Aut}\left(n\right)}\left(-1\right)^{\text{sgn}\left(\sigma\right)}\prod_{i\colon n}x_{i}^{\sigma\left(i\right)}.$$In particular, it follows that the aforementioned polynomial has precisely $n!$ nonzero terms.

Now construct the standard additive lattice $\mathbb{N}^{n}$ generated by the $n$-tuples $$\langle 1,0,\dots,0\rangle,\langle 0,1,\dots,0\rangle,\dots,\langle 0,0,\dots,1\rangle$$and let $$\Lambda=\left\{\langle\sigma\left({i}\right)\rangle_{i\colon n}\right\}_{\sigma\colon\text{Aut}\left(n\right)}.$$ Definition: Given subsets $Q_{1},Q_{2}\subseteq\mathbb{N}^{n}$, define the naïve sum $$Q_{1}+_{N}Q_{2}:\equiv\left\{q_{1}+q_{2}\dashv q_{1}\colon Q_{1}\text{ and }q_{2}\colon Q_{2}\right\}.$$ Definition: Given subsets $Q_{1},Q_{2}\subseteq\mathbb{N}^{n}$, define the pure sum $$Q_{1}+_{P}Q_{2}:\equiv\left\{q_{1}+q_{2}\dashv q_{1}\colon Q_{1}\text{ and }q_{2}\colon Q_{2}\right\}-\left\{q_{1}+q_{2}=q_{1}'+q_{2}'\dashv q_{1}\neq q_{1}'\colon Q_{1}\text{ and }q_{2}\neq q_{2}'\colon Q_{2}\right\}.$$ Definition: Given $\sigma\colon\text{Aut}\left(n\right)$, define over $\mathbb{N}^{n}$ the total order $\leqslant_{\sigma}$ obtained by lexicographically ordering $\mathbb{N}^{n}$, first by the $\sigma^{-1}\left(n-1\right)^{\text{st}}$ entry, then by the $\sigma^{-1}\left(n-2\right)^{\text{nd}}$, etc..., then finally by the $\sigma^{-1}\left(0\right)^{\text{th}}$. For finite subset $Q\subseteq\mathbb{N}^{n}$, define $\text{max}_{\sigma}Q$, termed the $\sigma$-maximal element of $Q$ to be the unique maximal element of $Q$ under $\leqslant_{\sigma}$. Remark: As a concrete example, $$\text{max}_{\sigma}\Lambda=\langle\sigma\left({i}\right)\rangle_{i\colon n}.$$ Remark: If $s_{1}\leqslant_{\sigma}t_{1}$ and $s_{2}\leqslant_{\sigma}s_{2}$, then $s_{1}+s_{2}\leqslant_{\sigma}t_{1}+t_{2}$. If, moreover, either of the summand inequalities is strict, then so too is the sum inequality. It follows that if $Q_{1},Q_{2}\subseteq\mathbb{N}^{n}$ are subsets, then $$\text{max}_{\sigma}\left(Q_{1}+_{N}Q_{2}\right)=\text{max}_{\sigma}\left(Q_{1}\right)+\text{max}_{\sigma}\left(Q_{2}\right)$$$$\text{max}_{\sigma}\left(Q_{1}+_{P}Q_{2}\right)=\text{max}_{\sigma}\left(Q_{1}\right)+\text{max}_{\sigma}\left(Q_{2}\right)$$(and in particular that the latter is nonempty). Claim 3: With $\Lambda$ as above and for $Q$ homogeneous, the map that sends $\langle\sigma\left({i}\right)\rangle_{i\colon n}\colon\Lambda$ to $\langle\sigma\left({i}\right)\rangle_{i\colon n}+\text{max}_{\sigma}Q$ is an injection. In particular, $$\left|\Lambda+_{P}Q\right|\geq\left|\Lambda\right|.$$ Proof: Direct corollary of the above discussion. $\Box$ Corollary: For any nonzero $q\colon\mathbb R\left[x_{i}\right]_{i\colon n}$, the polynomial $$q\prod_{i_{1}<i_{2},\ i_{1},i_{2}\colon n}\left(x_{i_{2}}-x_{i_{1}}\right)$$has at least $n!$ nonzero terms.

Proposed by Ankan Bhattacharya

Zero fancy things, just math: First we show $$Q_n = \prod_{i < j \le n} (a_i - a_j) \mid P.$$As factors of the form $a_i - a_j$ of $Q_n$ are coprime it suffices by symmetry to show that $a_1 - a_2 \mid P$. Let $P = (a_1 - a_2) D(a_1, \cdots, a_n) + R(a_1, \cdots, a_n)$. As long as $a_1 = a_2$, we have that $R(a_1, a_1, a_3, a_4, \ldots, a_n)$ is zero, which implies $R \equiv 0$ as we have many possible inputs, so $a_1 - a_2 \mid R \implies R = 0$. Now we claim that any multiple of $Q_n$ has at least $n!$ terms (monomials). We do this through induction: first it's obviously true for $Q_1 = 1$. For each $1 \le i \le n$, let $Z_i(p)$ for a polynomial $p = \sum_{i = 0}^{m} a_1^{e_1} a_2^{e_2} \ldots a_n^{e_n}$ be the set \[ Z_i(p) = \{ a_1^{e_1} a_2^{e_2} \ldots a_n^{e_n} : 0 \le i \le m, e_i = \text{deg}_{a_i} p \}. \]Essentially, all the terms in $p$ with maximal degree in $a_i$. Let $P = Q_n \cdot R$. Fix $i$. Clearly $$Z_i(P) = Z_i(Q_n) Z_i(R) = \{ r \cdot s : r \in Z_i(Q_n), s \in Z_i(R) \}$$from that $P = Q_n \cdot R$. Claim. For any $i, j$, we have $Z_i(Q_n) \cap Z_j(Q_n) = \emptyset$. Proof. Consider the process by which an arbitrary term in $Q_n$ is constructed: in some factor $a_k - a_l$, we "select" either $a_k$ or $a_l$ to be added on to this term. There are at most $n - 1$ terms with an arbitrary $a_k$ in them, one for every other $a_l$; thus $\text{deg}_{a_k} (Q_n) = n - 1$. Furthermore this means that for a term $t \in Z_i (Q_n) \cap Z_j (Q_n)$, both $a_i$ and $a_j$ need to be selected in the factor $a_i - a_j \mid Q_n$, which is impossible. Thus no such term exists. $\square$ It immediately follows that for any $i, j$, $Z_i (P) \cap Z_j (P) = \emptyset$ as well. Claim. $Z_i(P) \ge (n - 1)!$. Proof. Consider the same process by which we construct a term in $Q_n$ from earlier, by picking $a_k$ or $a_l$ from a factor $a_k - a_l$. Suppose that in all terms with $a_i$ in them, $a_i$ is picked, creating a term in $Z_i(Q_n)$. Now the possible choices for the other term is exactly of the form $$\pm \prod_{k < l \le n, i \ne k, l} (a_k - a_l) = \pm Q_{n - 1} (a_1, \ldots, a_{i - 1}, a_{i + 1}, \ldots, a_n).$$Thus $Z_i(Q_n) = \pm a_i^{n - 1} Q_{n - 1} (a_1, \ldots, a_{i - 1}, a_{i + 1}, \ldots, a_n)$ so $$Z_i(P) = \pm a_i^{n - 1} Q_{n - 1} (a_1, \ldots, a_{i - 1}, a_{i + 1}, \ldots, a_n) \cdot Z_i(R)$$and as any multiple of $Q_{n - 1}$ has at least $(n - 1)!$ terms so must the polynomial above, whose terms are $Z_i(P)$ exactly. Thus $|Z_i(P)| \ge (n - 1)!$. $\square$ Now let the set of terms of $P$ be $Z$. As $Z_i(P)$ for all $i$ are disjoint and all have cardinality at least $(n - 1)!$, $$|Z| \ge \left | \bigcup_{i = 1}^n Z_i(P) \right | = n \cdot (n - 1)! = n!,$$as desired. $\square$

Super clean outline: We use induction, base case n=2 is simple. WLOG that none of $x_1, x_2, \cdots x_n$ divide $P$ (RIP -1 point at most I hope for forgetting this) Consider $Q_1 = P(0, x_2, x_3, \cdots, x_n)$ and define $Q_2, Q_3, \cdots Q_n$ similarly. By induction $Q_i$ has $(n-1)!$ terms. We can easily get that $x_2x_3 \cdots x_n$ divides $Q_1$ using the property given and setting stuff to 0. Also $Q_1$ represents the monomials of $P$ that do not include $x_1$. This together means that $Q_i$ and $Q_j$ cannot share any terms between them. Thus summing them all up we get at least $n(n-1)! = n!$ monomials. God I hope this isn't a fake solve

My solution is long. This was definitely the hardest problem on both days; it took me 2+ hours to solve, though it seems I did too much work. Anyway, I hope this solution is right; everything is also quite elementary, which is a bonus! Lemma: If two polynomials $f,g\in\mathbb{R}[x_1,\dots,x_n]$ agree for all selections of $x_i\in\mathbb{R}$, then $f\equiv g$ (coefficients match). Proof: Apparently this is well-known. I just stated that writing out $f,g$ and plugging in a ton of things and solving the resultant system will give you that all coefficients match. Note that this only works because $\mathbb{R}$ is infinite (e.g. $X^p-X\not\equiv 0$ in $\mathbb{F}_p$ even though it vanishes everywhere). Claim 1: For the $P$ in the problem, we have \[\prod_{1\le i<j\le n}(x_i-x_j)\mid P(\mathbf{x}).\](i.e. there exists a polynomial $Q(\mathbf{x})$ such that $P=Q\cdot\prod (x_i-x_j)$). Proof: Since $\mathbb{R}[x_1,\dots,x_n]$ is a UFD, it suffices to check this for any given $i,j$. View $P$ as a polynomial in only $x_i$, fixing all other $x_k=r_k$ and apply Euclidean division (note that this cannot be done for multivariate polynomials, but can be done in single variables) of $P$ by $x_i-r_j$. \[P(x_i)=Q(x_i)(x_i-r_j)+R(x_i),\]where $\deg R<1$. When $x_i=r_j$, the problem tells us that $P=0$, so then $R\equiv 0$. Now note that this identity holds for any $x_i$ and any $r_j$, so by our lemma above, $P=Q(x_i-x_j)$, and we can repeat, giving the desired. $\square$ Claim 2: The expansion of \[\prod_{1\le i<j\le n}(x_i-x_j)\]contains exactly $n!$ monomials, each of the form $\alpha_\sigma x_{\sigma(1)}^0x_{\sigma(2)}^1\cdots x_{\sigma(n)}^{n-1}$ for every permutation $\sigma$ of $\{1,2,\dots,n\}$ and $\alpha_\sigma = \pm1$. (tree3 notes this is a result of Vandermonde determinants.) Proof: Note that the degree of every term in the expansion should be exactly $\binom{n}2=0+1+2+\cdots+(n-1)$. Therefore, it suffices to show that the exponents of two variables cannot be equal in the expansion; this is quite a combinatorial proof. Let's count the number of monomials of the form $x_1^ex_2^ex_3^{e_3}\cdots x_n^{e_n}$, where WLOG the first two exponents are equal. We claim that the coefficient of this monomial must be $0$, and this follows by a pairing argument. In our product, we are essentially choosing either $x_i$ or $-x_j$ from each factor $(x_i-x_j)$ and then multiplying them all together. We make a few choices to create our monomial: Pick either $x_1$ or $-x_2$ in the $(x_1-x_2)$ factor. For each index $i\neq 1,2$, consider $(x_1-x_i)(x_2-x_i)$, and we have one of four choices. Denote by $A$ the set of indices $i$ where you pick both $x_1$ and $x_2$; by $B$ the set of indices where you pick both $-x_i$s, by $C_1$ the set of indices where you pick $x_1$ and $-x_i$, and by $C_2$ the set of indices where you pick $x_2$ and $-x_i$. Now consider the following pairing: for each choice of $x_1$ or $-x_2$, as well as the sets $A,B,C_1,C_2$, consider the selection where instead you pick the opposite of $x_1$ or $-x_2$, the same sets $A$ and $B$, but flip $C_1$ and $C_2$. Note that applying this pairing operation twice results in the identity operation, so it is bijective (and nothing is a fixed point either). To achieve the equal exponents of $e$, first WLOG that $x_1$ is chosen from the $(x_1-x_2)$ factor. Then, $|A|+|C_1|=e-1$ while $|B|+|C_2|=e$. After the swap, note that the exponents of $x_1$ and $x_2$ remain at $e$, while the sign flips since we went from $x_1$ to $-x_2$. Nothing else changes. Therefore, we have successfully paired selections to show that any monomial with two equal exponents must vanish. Therefore, each monomial must look like $\alpha_\sigma x_{\sigma(1)}^0x_{\sigma(2)}^1\cdots x_{\sigma(n)}^{n-1}$, and it is pretty clear that this can be selected in exactly $1$ way; we first must pick every $x_{\sigma(n)}$ possible, then the remaining $x_{\sigma(n-1)}$s, and so on. The sign, however, is indeterminate, so $\alpha_\sigma=\pm 1$. Now we can finish up, we just have to show that terms don't really die. We do this by induction: Claim 3: We can write \[P(\mathbf{x})=\left(\sum_{\sigma}\alpha_\sigma x_{\sigma(1)}^0x_{\sigma(2)}^1\cdots x_{\sigma(n)}^{n-1}\right)Q(\mathbf{x}).\]For any selection of $\alpha_\sigma\in\{-1,1\}$ and $Q(\mathbf{x})$, we claim that $P$ still has $n!$ distinct nonzero monomial terms. Proof: The proof is by induction on $n$. Base Case of $n=2$: Here, we have \[P(x,y)=(\pm x\pm y)Q(x,y),\]and we wish to show that $P$ contains at least two monomials. Consider the term $\alpha_mx^{m_1}y^{m_2}$ in $Q(x,y)$ such that $m_1$ is maximized, and of all such monomials containing $x^{m_1}$, $m_2$ is also maximized. Analogously define $\alpha_nX^{n_1}Y^{n_2}$ by first maximizing $n_2$, then $n_1$. Note that the two monomial terms \[\pm\alpha_mx^{m_1+1}y^{m_2}\text{ and }\pm\alpha_nx^{n_1}y^{n_2+1}\]remain, and cannot be canceled due to maximality. Inductive Step: We can actually extend the idea above, consider terms in \[\sum_{\sigma}\alpha_\sigma x_{\sigma(1)}^0x_{\sigma(2)}^1\cdots x_{\sigma(n)}^{n-1}\]with $\sigma(n)=1$. Now, consider terms in $Q(\mathbf{x})$ with maximum exponent $e$ of $x_1$. Multiplying these with the terms in the sum mentioned before of the form $x_1^{n-1}\left(\sum\pm x_2^{e_2}\cdots x_n^{e_n}\right)$ produces the terms \[x_1^{n-1+e}\left(\sum \pm x_2^{e_2}\cdots x_n^{e_n}\right)\cdot Q_{1,\text{reduced}}(x_2,\dots,x_n),\]where $x_1^e\cdot Q_{1,\text{reduced}}(x_2,\dots,x_n)$ are all the $x_1^e$ terms in $Q$. By the inductive hypothesis on $n-1$ variables, \[\left(\sum \pm x_2^{\sigma(0)}\cdots x_n^{\sigma(n-2)}\right)\cdot Q_{1,\text{reduced}}(x_2,\dots,x_n),\]where $\sigma$ is a permutation of $\{0,1,\dots,n-2\}$, contains at least $(n-1)!$ different monomial terms. Multiplying these by $x_1^{n-1+e}$, and the maximality of $n-1$ and $e$, ensures that these terms cannot be canceled. Repeating for $x_1$ replaced with $x_2,\dots,x_n$ gives a total of $n\cdot (n-1)!=n!$ distinct monomial terms which cannot be canceled due to maximality reasons. And finally, we are done.

Twistya wrote: Super clean outline: We use induction, base case n=2 is simple. WLOG that none of $x_1, x_2, \cdots x_n$ divide $P$ (RIP -1 point at most I hope for forgetting this) Consider $Q_1 = P(0, x_2, x_3, \cdots, x_n)$ and define $Q_2, Q_3, \cdots Q_n$ similarly. By induction $Q_i$ has $(n-1)!$ terms. We can easily get that $x_2x_3 \cdots x_n$ divides $Q_1$ using the property given and setting stuff to 0. Also $Q_1$ represents the monomials of $P$ that do not include $x_1$. This together means that $Q_i$ and $Q_j$ cannot share any terms between them. Thus summing them all up we get at least $n(n-1)! = n!$ monomials. God I hope this isn't a fake solve oops that's so simple why didn't i think of it ugh, my way was similar but i might have fakesolved what you left out is that all the terms in each $Q$ must have at least $n-1$? distinct $x_i$ in each term otherwise some would cancel but I think that's just easy induction or maybe it's false I'm thinking about it

tigershark22 wrote: Twistya wrote: Super clean outline: We use induction, base case n=2 is simple. WLOG that none of $x_1, x_2, \cdots x_n$ divide $P$ (RIP -1 point at most I hope for forgetting this) Consider $Q_1 = P(0, x_2, x_3, \cdots, x_n)$ and define $Q_2, Q_3, \cdots Q_n$ similarly. By induction $Q_i$ has $(n-1)!$ terms. We can easily get that $x_2x_3 \cdots x_n$ divides $Q_1$ using the property given and setting stuff to 0. Also $Q_1$ represents the monomials of $P$ that do not include $x_1$. This together means that $Q_i$ and $Q_j$ cannot share any terms between them. Thus summing them all up we get at least $n(n-1)! = n!$ monomials. God I hope this isn't a fake solve oops that's so simple why didn't i think of it ugh, my way was similar but i might have fakesolved what you left out is that all the terms in each $Q$ must have at least $n-1$ distinct $x_i$ in each term otherwise some would cancel but I think that's just easy induction That follows from Q is divisible by $x_1x_2...x_n$. Wow, this solution is so simple, surprised no one else thought of it yet.

Yeah, I had a solution that was kinda similar and I know others did as well. But I think the way I did it was wrong.

Call such polynomial great. We proceed by induction on $n$, where the base case $n=2$ is obvious. Write $$P(x_1, x_2, \cdots, x_n)=x_1^{a_1} Q_1(x_2, \cdots, x_n)+x_1^{a_2} Q_2(x_2, \cdots, x_n)+\cdots +x_1^{a_k} Q_k(x_2, \cdots, x_n)$$where $Q_i$ are nonzero distinct polynomials of $x_2, \cdots, x_n$ and $0 \le a_1<a_2<\cdots<a_k$. Claim. $Q_1, Q_2, \cdots, Q_k$ are great polynomials with $n-1$ variables. Proof. It suffices to prove that $Q_i(x_2, \cdots, x_n)=0$ if $x_i=x_j$ for some $2\le i<j\le n$. Indeed, since $$0=P(r_1, r_2, \cdots, r_n)=r_1^{a_1} Q_1(r_2, \cdots, r_n)+r_1^{a_2} Q_2(r_2, \cdots, r_n)+\cdots +r_1^{a_k} Q_k(r_2, \cdots, r_n)$$holds identically, so the result follows. $\square$ By the induction hypothesis, $Q_i$ can be written as a sum of at least $(n-1)!$ monomials. Since these monomials doesn't overlap, $P$ can be written as a sum of at least $k\times (n-1)!$ monomials. Now it suffices to prove that $k \ge n$. Claim. We have $k \ge n$. Proof. FTSOC suppose that $k<n$. First, note that \[ R(x_2, \cdots, x_n)=\det [ \mathbf{v}_{2}, \mathbf{v}_{3}, \cdots, \mathbf{v}_{k+1}] \times \prod_{j=2}^{n} Q_j ,\]is nonzero(as polynomials), so there exist reals $r_2, \cdots, r_n$ so that $R(r_2, \cdots, r_n) \neq 0$. Then the vectors $\mathbf{v}_2=\begin{bmatrix}r_2^{a_1} \\ r_2^{a_2} \\ \vdots \\ r_2^{a_k} \end{bmatrix}, \cdots, \mathbf{v}_{k+1}=\begin{bmatrix} r_{k+1}^{a_1} \\ r_{k+1}^{a_2} \\ \vdots \\ r_{k+1}^{a_k} \end{bmatrix}$ are linearly independent and $Q_j(r_2, \cdots, r_n) \neq 0$ for each $2\le j \le n$. Now, for each $2\le i \le k+1$, $$0=P(r_i, r_2, \cdots, r_n)=r_i^{a_1} Q_1(r_2, \cdots, r_n)+r_i^{a_2} Q_2(r_2, \cdots, r_n)+\cdots +r_i^{a_k} Q_k(r_2, \cdots, r_n),$$so \[ [ \mathbf{v}_2, \mathbf{v}_3, \cdots, \mathbf{v}_{k+1}]^T \begin{bmatrix}Q_1 \\ Q_2 \\ \vdots \\ Q_n \end{bmatrix} =0 \]which is impossible. This concludes the proof. $\square$

The given condition means that $x_i-x_j$ is a factor of $P$ for all $1\le i<j\le n.$ Let a $n$-variable polynomial be $n$-good if it satisfies this condition. We proceed by induction. The base case $n=2$ is trivial. Now, for the inductive step assume that the statement is true for $1\le n < k$ and consider the case $n=k.$ If $P$ has any factors in the form $x_i^{d_i},$ we can delete them, since they do not affect the number of monomials in the expansion of $P$. Then, we set $x_i$ equal to $0$ for some $i.$ We then obtain a $n-1$-good polynomial, so it must be the sum of at least $(n-1)!$ monomials, specifically the ones that are part of the expansion of $P$ that do not contain a factor of $x_i$. Do this for all $x_i.$ This creates $n!$ not necessarily distinct monomials. However, the only way that some could be overcounted is if some term in the expansion of $P$ does not contain a factor of both $x_i$ and $x_j,$ for some $i\neq j.$ But this is clearly impossible since $x_i-x_j$ is a factor of $P.$ Thus, the $n!$ monomials we formed are distinct, and we are done.

Revenge. The problem statement is equivalent to \[ A(x_1,\ldots,x_n) := \prod_{i<j} (x_j-x_i) \mid P(x_1,\ldots,x_n). \]We first prove some properties about $A$. Remark that these are immediate by citing ``Vandermonde determinant'', but we do not appeal to this. Lemma 1: For any $\pi$ a permutation of $(0,\ldots,n-1)$, the expression \[ \varepsilon x_1^{\pi_1}x_2^{\pi_2} \cdots x_n^{\pi_n}\]is a monomial of $A$ for some $\varepsilon\in \{-1,1\}$. In particular, $A$ has at least $n!$ terms. Proof: Fix $\pi$. It is very easy to see that we can find a monomial in the expansion of $A$ which is of the correct form. (Note that this lemma is trivial since it is not proving that no other kind of term exists.) $\blacksquare$ Lemma 2: Suppose $Cx_1^{a_1}x_2^{a_2}\cdots x_n^{a_n}$ is a monomial of $A$. Then $(n-1,n-2,\ldots,0)$ majorizes $(a_1,a_2,\ldots,a_n)$. Proof: We show that $(n-1)+(n-2)+\cdots+(n-k) \ge a_1+\cdots + a_k$ for all $k\ge 1$. Fix $k$. Consider the polynomial \[ B(x_1,\ldots,x_{n-k}) := A(x_1,\ldots,x_{n-k},100,200,\ldots,100k). \]The degree of the RHS above is $\binom{n}{2} - \binom{k}{2} = (n-1)+\cdots+(n-k)$, so this is $\deg B$. Since $Cx_1^{a_1}\cdots x_n^{a_n}$ is a monomial of $A$, this becomes $C'x_1^{a_1}\cdots x_{n-k}^{a_{n-k}}$ for some other constant $C'$. This expression is a monomial of $B$, so it has degree at most $\deg B$, and our result follows. $\blacksquare$ Suppose $P=A\cdot Q$ for some $Q\in \mathbb{R}[x_1,\ldots,x_n]$. Enumerate the monomials of $A$ as $A_1,\ldots,A_N$, where $N\ge n!$. So we know $A=A_1+\cdots+A_N$. We have \[ P = AQ = A_1Q + A_2Q + \cdots + A_NQ. \]For each $1\le i \le N$, we can expand $A_iQ$ into a sum of $|Q|$ monomials. (Note: we will omit constant scalars.) (Main idea) Fix some $i$. We claim $A_iQ$ has a monomial which does not appear in the expansion of any other $A_jQ$. WLOG suppose $A_i = x_1^0x_2^1\cdots x_n^{n-1}$. Consider the monomial of $Q$ which has maximal exponent of $x_n$. If there are multiple, tiebreak by choosing the one with maximal exponent of $x_{n-1}$. Keep tiebreaking till necessary. Call this monomial of $Q$ as $x_1^{e_0}x_2^{e_1}\cdots x_n^{e_{n-1}}$. So now, one of the monomials of $A_iQ$ is $x_1^{e_0} x_2^{1+e_1} \cdots x_n^{n-1+e_{n-1}}$. Claim: The monomial $x_1^{e_0} x_2^{1+e_1} \cdots x_n^{n-1+e_{n-1}}$ is not a term in the expansion of $A_jQ$ for any $j$. Proof: Suppose it was for some $j$. We show $A_j=A_i$. In particular, we will show that the exponent of $x_k$ in $A_j$ is $k-1$ for $k=0,\ldots,n-1$. Backwards induct on $k$. Base case: Since $n-1$ is the maximum possible exponent of $x_n$ in $A_j$, and $e_{n-1}$ is the maximum possible exponent of $x_n$ in a term of $Q$, the maximum possible exponent of $x_n$ in a monomial in the expansion of $A_jQ$ is $n-1+e_{n-1}$. Equality holds, since we assumed $x^{n-1+e_{n-1}}$ is a part of a monomial in the expansion of $A_jQ$. Therefore, both bounds are tight; in particular, the monomial $A_j$ contains $x_n^{n-1}$, and any monomial of $Q$ which we can multiply to $A_j$ and result with $x_n^{n-1+e_{n-1}}$ must have exponent $e_{n-1}$ of $x_n$. Inductive step: Suppose $A_j$ contains $x_n^{n-1}x_{n-1}^{n-2}\cdots x_{k+1}^{k}x_k^\ell$; we want to show $\ell=k-1$. By Lemma 2, \[ (n-1)+\cdots + k+(k-1) \ge (n-1)+\cdots + k+\ell , \]so $\ell \le k-1$. Consider the subset of the monomials of $Q$ which have exponent $e_{n-1}$ for $x_n$, $e_{n-2}$ for $x_{n-1}$, and so on till exponent $e_{k}$ for $x_{k+1}$. The monomial in $Q$ we are multiplying by must be in this subset by the same equality argument as in the base case. The maximum possible exponent of $x_k$ in this subset of $Q$ is $e_{k-1}$; indeed, this follows by definition from the tiebreaking process. However, we know that $k-1+e_{k-1}$ is the exponent of $x_k$ in a monomial in the expansion of $A_jQ$. Hence we must have equality in the two bounds $\ell \le k-1$ and the exponent of $x_k$ is at most $e_{k-1}$. In particular, $\ell = k-1$, competing the induction. $\blacksquare$ The above Claim finishes since for each $A_i$, we have at least one term not in any other $A_j$ in the expansion of $P = \sum A_iQ$. Since $N\ge n!$, there are at least $n!$ terms in $P$.

MortemEtInteritum wrote: Wow, this solution is so simple, surprised no one else thought of it yet. Isn't this Ankan's solution? And mine, I suppose We use induction on $n$, with the base case of $n=2$ being clear. Call polynomials satisfying the described conditions distinctive. Also, when we refer to a "term" or the "number of terms" in a multivariable polynomial, we assume that all like terms have been combined, so the polynomial $2x-x$ only has one term, namely $x$. We now introduce a key claim. Claim: If $P(x_1,\ldots,x_n)$ is distinctive, then no term of $P$ has degree zero in two variables. Proof: Suppose otherwise, and pick $i,j$ such that $P$ has terms with zero degree in $x_i$ and $x_j$. Then substituting $x_i=x_j=x$ doesn't result in any such terms being cancelled, but this contradicts the fact that the polynomial vanishes in this case. Now, by the multivariable polynomial factor theorem, we find that $\prod_{1\leq i<j\leq n} (r_i-r_j)$ must divide $P$ given that $P$ is distinctive. Hence we can write $P(x_1,\ldots,x_n)=\prod_{1\leq i<j \leq n} (r_i-r_j)Q(x_1,\ldots,x_n)$, where $Q$ is nonzero. WLOG assume that none of $x_1,\ldots,x_n$ divide $Q$, so clearly none of those divide $P$ either. Now let $P_k$ be the polynomial comprised of the terms with degree zero in $x_k$. By the previous assumption, all the $P_k$ are nonzero. Further, $P_k$ is equal to $P(x_1,\ldots,x_{k-1},0,x_{k+1},\ldots,x_n)$, so $\prod_{1\leq i<j\leq n, i,j \neq k} (x_i-x_j)$ divides $P_k$. It therefore follows that $P_k$ is a distinctive polynomial as well, so by inductive hypothesis it must have at least $(n-1)!$ terms. By our claim, none of $P_1,\ldots,P_n$ share terms, so it follows that $P$ contains at least $n(n-1)!=n!$ terms, so we're done. $\blacksquare$

DottedCaculator wrote: Let $n \geq 2$ be an integer. Let $P(x_1, x_2, \ldots, x_n)$ be a nonconstant $n$-variable polynomial with real coefficients. Assume that whenever $r_1, r_2, \ldots , r_n$ are real numbers, at least two of which are equal, we have $P(r_1, r_2, \ldots , r_n) = 0$. Prove that $P(x_1, x_2, \ldots, x_n)$ cannot be written as the sum of fewer than $n!$ monomials. (A monomial is a polynomial of the form $cx^{d_1}_1 x^{d_2}_2\ldots x^{d_n}_n$, where $c$ is a nonzero real number and $d_1$, $d_2$, $\ldots$, $d_n$ are nonnegative integers.) Proposed by Ankan Bhattacharya A bit technical for the USOJMO. We induct on $n$. For the base case $n = 2$, we see that if $P(x)$ is of form $cx_1^mx_2^n$, then $P(2, 2) \implies c2^{m+n} = 0 \implies c = 0$, which contradicts the non-constant condition, Therefore, $P(x)$ has at least two monomial terms, as desired. The $n = 2$ case is our base case. For the induction step, let us assume that for all positive integers $k$ such that $2 \leq k \leq n - 1$, if a non-constant polynomial $P(x_1, x_2 \dots x_k)$ over $k$ variables satisfies problem's propositions, then the irreducible expansion (basically $P$ divided by $\text{gcd}$ of all monomials in the proper expansion of $P$) of $P(x_1, x_2 \dots x_k)$ contains at least $k!$ monomials. Consider a polynomial $P(x_1, x_2 \dots x_n)$ over $n$ variables satisfying the problem's propositions. Let $P_1(x_1, x_2 \dots x_n)$ be the irreducible expansion of $P$. This means that if the proper expansion of $P_1(x_1, x_2 \dots x_n)$ is $m_1 + m_2 \dots m_k$ where $m_i$ and $m_j$ are unlike terms for all distinct $(i, j) \in \{ 1, 2, 3 \dots k \}^2$, so more or less we have to prove that $k \geq n!$. We see that if $\text{deg}_{x_i}(m_i) = \text{deg}_{x_j}(m_i) = 0$ for two distinct variables $x_i, x_j$, then more or less we see that $x_i = x_j = 0$ and $x_k = 1$ $\forall\;$ $k \neq (i, j)$ will give that $P(x_1, x_2 \dots x_n) = \text{co-efficient} \; \text{of} m_i$ which is non-zero to begin with, a contradiction. This means that for each monomial $m_j$ in the proper expansion of $P_1$, there exists at most $1$ variable $x_i$ for which $\text{deg}_(x_i)(P_1) = 0$. But this means that setting $x_i = 0$ for all $i = 1, 2, 3 \dots n$, we get a polynomial $P_2(x_1, x_2 \dots x_{i-1}, x_{i+1} \dots x_n)$ over $n-1$ variables which satisfies problem's propositions and has at least $(n-1)!$ distinct or unlike monomial terms in it due to induction hypothesis, this means that $$k = \text{number} \; \text{of} \; \text{distinct/unlike} \; \text{monomials} \; \text{in} \; P_1 \geq n(n-1)! = n!$$as desired as we end the induction process.

rafayaashary1 wrote: A cute problem imho; break it into the following three natural steps: (I index always from $0$ and identify naturals (of which $0$ is the first) with the set of naturals strictly less than them when appropriate (i.e., $0=\emptyset$).) Given natural $n\colon\mathbb{N}$, Claim 1: For characteristic $0$ integral domain $R$, if polynomial $p\colon R\left[x_{0},x_{1}\right]$ is such that $p\colon\prod_{i\colon 2}R\to R$ vanishes whenever the two inputs agree, then $p$ is divisible by $x_{i_{2}}-x_{i_{1}}$.

Corollary: If polynomial $p\colon\mathbb{R}\left[x_{i}\right]_{i\colon n}$ is such that for any nonidentical $i_{1},i_{2}\colon n$, the function $p\colon\prod_{i\colon n}\mathbb{R}\to\mathbb{R}$ vanishes whenever the inputs in index $i_{1}$ and $i_{2}$ agree, then $p$ is divisible by $\prod_{i_{1}<i_{2},\ i_{1},i_{2}\colon n}x_{i_{2}}-x_{i_{1}}$. Hint: As a ring of polynomials over a UFD, $\mathbb{R}\left[x_{i}\right]_{i\colon n}$ is itself a UFD. Claim 2: Denote by $\text{Aut}\left(n\right)$ the group of permutations $n\to n$, and by $\text{sgn}\colon\text{Aut}\left(n\right)\to\mathbb{Z}^{\times}$ the canonical signature mapping thereof. One has that $$\prod_{i_{1}<i_{2},\ i_{1},i_{2}\colon n}\left(x_{i_{2}}-x_{i_{1}}\right)=\sum_{\sigma\colon\text{Aut}\left(n\right)}\left(-1\right)^{\text{sgn}\left(\sigma\right)}\prod_{i\colon n}x_{i}^{\sigma\left(i\right)}.$$In particular, it follows that the aforementioned polynomial has precisely $n!$ nonzero terms.

Now construct the standard additive lattice $\mathbb{N}^{n}$ generated by the $n$-tuples $$\langle 1,0,\dots,0\rangle,\langle 0,1,\dots,0\rangle,\dots,\langle 0,0,\dots,1\rangle$$and let $$\Lambda=\left\{\langle\sigma\left({i}\right)\rangle_{i\colon n}\right\}_{\sigma\colon\text{Aut}\left(n\right)}.$$ Definition: Given subsets $Q_{1},Q_{2}\subseteq\mathbb{N}^{n}$, define the naïve sum $$Q_{1}+_{N}Q_{2}:\equiv\left\{q_{1}+q_{2}\dashv q_{1}\colon Q_{1}\text{ and }q_{2}\colon Q_{2}\right\}.$$ Definition: Given subsets $Q_{1},Q_{2}\subseteq\mathbb{N}^{n}$, define the pure sum $$Q_{1}+_{P}Q_{2}:\equiv\left\{q_{1}+q_{2}\dashv q_{1}\colon Q_{1}\text{ and }q_{2}\colon Q_{2}\right\}-\left\{q_{1}+q_{2}=q_{1}'+q_{2}'\dashv q_{1}\neq q_{1}'\colon Q_{1}\text{ and }q_{2}\neq q_{2}'\colon Q_{2}\right\}.$$ Definition: Given $\sigma\colon\text{Aut}\left(n\right)$, define over $\mathbb{N}^{n}$ the total order $\leqslant_{\sigma}$ obtained by lexicographically ordering $\mathbb{N}^{n}$, first by the $\sigma^{-1}\left(n-1\right)^{\text{st}}$ entry, then by the $\sigma^{-1}\left(n-2\right)^{\text{nd}}$, etc..., then finally by the $\sigma^{-1}\left(0\right)^{\text{th}}$. For finite subset $Q\subseteq\mathbb{N}^{n}$, define $\text{max}_{\sigma}Q$, termed the $\sigma$-maximal element of $Q$ to be the unique maximal element of $Q$ under $\leqslant_{\sigma}$. Remark: As a concrete example, $$\text{max}_{\sigma}\Lambda=\langle\sigma\left({i}\right)\rangle_{i\colon n}.$$ Remark: If $s_{1}\leqslant_{\sigma}t_{1}$ and $s_{2}\leqslant_{\sigma}s_{2}$, then $s_{1}+s_{2}\leqslant_{\sigma}t_{1}+t_{2}$. If, moreover, either of the summand inequalities is strict, then so too is the sum inequality. It follows that if $Q_{1},Q_{2}\subseteq\mathbb{N}^{n}$ are subsets, then $$\text{max}_{\sigma}\left(Q_{1}+_{N}Q_{2}\right)=\text{max}_{\sigma}\left(Q_{1}\right)+\text{max}_{\sigma}\left(Q_{2}\right)$$$$\text{max}_{\sigma}\left(Q_{1}+_{P}Q_{2}\right)=\text{max}_{\sigma}\left(Q_{1}\right)+\text{max}_{\sigma}\left(Q_{2}\right)$$(and in particular that the latter is nonempty). Claim 3: With $\Lambda$ as above and for $Q$ homogeneous, the map that sends $\langle\sigma\left({i}\right)\rangle_{i\colon n}\colon\Lambda$ to $\langle\sigma\left({i}\right)\rangle_{i\colon n}+\text{max}_{\sigma}Q$ is an injection. In particular, $$\left|\Lambda+_{P}Q\right|\geq\left|\Lambda\right|.$$ Proof: Direct corollary of the above discussion. $\Box$ Corollary: For any nonzero $q\colon\mathbb R\left[x_{i}\right]_{i\colon n}$, the polynomial $$q\prod_{i_{1}<i_{2},\ i_{1},i_{2}\colon n}\left(x_{i_{2}}-x_{i_{1}}\right)$$has at least $n!$ nonzero terms. Isn't this above IMO level proof though, not going to be surprised if some students actually end up knowing whatever all this means, cause I sure don't . The polynomial rings and the canonical maps are linear algebra/abstract algebra right.

edit: rip, i did mess up something, I think I fixed it Due to having a root whenever two variables are equal, we have $$P(x)=(x_1-x_2)(x_1-x_3)\cdots (x_1-x_n)(x_2-x_3)\cdots (x_2-x_n)\cdots\cdots (x_{n-1}-x_n)Q(x).$$Consider when the product of everything other than $Q(x)$ is expanded out. This will contain the term $$x_1^0x_2^1x_3^2\cdots x_n^{n-1}$$and all of its permutations, which is $n!$ permutations. Now, consider multiplying by $Q(x).$ Let's partition $Q(x)$ into nonconstant and constant terms. Note that when performing the final expansion, the product of $$(x_1-x_2)(x_1-x_3)\cdots (x_1-x_n)(x_2-x_3)\cdots (x_2-x_n)\cdots\cdots (x_{n-1}-x_n)$$with nonconstant terms will have degree greater than $n(n-1)/2$, while the product with constant terms will all have degree $n(n-1)/2$. Therefore, the original $n!$ permutation terms of $$x_1^0x_2^1x_3^2\cdots x_n^{n-1}$$will remain with an added constant factor, unless that constant factor is 0. We will now use a seperate case for when there is no constant factor. Factor out all factors of $x_k^m$ away from $Q$ so that no variable $x_k$ occurs in every term of $Q$. Let $R_i$ be the polynomial $P$ but with $x_i=0$. Note that each polynomial $R_i$ satisfies the condition for $n-1$. $R_i$ is also the polynomial consisting of all terms in $P$ for which there is no $x_i$ factor. Claim: The terms of $R_i$ are pairwise distinct. Suppose that there was a term that is in both $R_i$ and $R_j$. Then, that term has neither a $x_i$ nor a $x_j$ factor. If we let $x_i=x_j=0$, due to the condition, the entire polynomial should be 0 no matter the other terms. However, if there is a term with neither a $x_i$ nor a $x_j$ factor, this is clearly not the case. Therefore, by induction, if $R_i$ contains at least $(n-1)!$ terms, then $P$ contains at least $n!$ terms. The base case $n=2$ can be easily verified, so we are done.

Does this solution work? Note that $(x_j - x_i)$ divides P for all $j \ge i$. All terms of the form $(x_a)^n \cdot (x_b)^{n - 1} \cdot \dots$ will be in $\prod (x_j - x_i)$. To get P, we multiply $\prod (x_j - x_i)$ by another polynomial Q. First, note that $(x_1)^n \cdot (x_2)^{n - 1} \cdot \dots$ is the term in $\prod (x_j - x_i)$ with the highest exponent of $x_1$. Of terms with the same exponent of $x_1$, it has the highest exponent of $x_2$, etc for all $x_n$. (In fact, terms of the form $(x_1)^n \cdot (x_2)^{n - 1} \cdot \dots$ are the only such terms in $\prod (x_j - x_i)$ but the proof of this is not necessary in my solution) For $(x_1)^n \cdot (x_2)^{n - 1} \cdot \dots$, consider the terms in Q with the highest exponent of $x_1$. From those, consider the terms with the highest $x_2$ exponent, etc. Multiplying this term with $(x_1)^n \cdot (x_2)^{n - 1} \cdot \dots$ gives a unique, nonzero monomial. Repeating this for all such $(x_a)^n \cdot (x_b)^{n - 1} \cdot \dots$ gives at least $n!$ monomials.

This actually seems super intuitive for J3/6. The natural first step is to note $x_j - x_i \mid P$ for $j > i$. Claim. The polynomial $\prod (x_j - x_i)$ has at least $n!$ nonzero terms. Proof. We find terms of the form $x_1^{n-1}x_2^{n-2} \cdots x_{n-1}$ and cyclic permutations. Notice that such a term appears uniquely in the expansion by taking the numerically lower indexed monomial in each term of the product, thus no such terms cancel. $\blacksquare$ Now write $P = Q \prod (x_j - x_i) = \sum Q x_1^{n-1} x_2^{n-2} \cdots x_{n-1}$. We want to ensure $n!$ monomials in $P$, so we want to get one unique monomial in each term of the sum. Fortunately, this is easy: for the term $Q x_1^{\sigma(0)} x_2^{\sigma(1)} \cdots x_n^{\sigma(n-1)}$ for a permutation $\sigma$ of $[n]$, take the lexicographically first term in $Q$ according to $\sigma$. This creates a unique monomial that does not appear otherwise in the expansion, as needed. This guarantees $P$ has at least $n!$ terms.

Since $x_i=x_j$ implies $P(x_1, \dots, x_n)=0$, $P$ is divisible by the Vandermonde determinant \[ V(x_1, \dots, x_n) := \prod_{i<j} (x_j-x_i) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) x_1^{\sigma(0)} x_2^{\sigma(1)} \dots x_n^{\sigma(n-1)}. \]Let $P = V \cdot Q$, so that \[ P(x_1, \dots, x_n) = \sum_{\sigma \in S_n} \sum_{e_i \ge 0} \operatorname{sgn}(\sigma) x_1^{\sigma(0)+e_1} x_2^{\sigma(1)+e_2} \dots x_n^{\sigma(n-1)+e_n} \cdot \left[\small\prod_j x_j^{e_j}\right] Q(x_1, \dots, x_n). \]Take the monomial of $Q$ with $(e_1, e_2, \dots)$ lexicographically maximal. Then note that each permutation $\sigma \in S_n$, the monomial \[ x_1^{\sigma(0)+e_1} x_2^{\sigma(1)+e_2} \dots x_n^{\sigma(n-1)+e_n} \]appears exactly once in the expansion (and thus its coefficient is nonzero), so $P$ has at least $n!$ terms, as desired.

Solved with happypi31415.

First note that each term has at least $n-1$ variables. FTSOC, assume that some term(s) don't contain variables $x_i$ and $x_j$. Then plug in $(x_i, x_j) = (0, 0)$ and let the other variables be arbitrary. Then let the values not containing $x_i$ and $x_j$ be $Q$. Clearly $Q = 0$ so the rest of $P$ is also $0$ for arbitrary values of variables, contradiction. WLOG $P$ is not divisible by $x_i$ for any $i$(since we can just factor them out). We will do induction on $n$ with $n = 2$ being true. Consider the group of terms that does not contain $x_k$ for some arbitrary $k$. This group of terms is equal to $0$ when two variables that are not $x_k$ are equal to each other, since the rest of the terms in $P$ is divisible by $x_k$(and is thus $0$). So the group of terms that does not contain $x_k$ has at least $(n-1)!$ terms by induction, and varying $k$ gives us $n!$ total terms as desired.