Cookie Monster says a positive integer $n$ is $crunchy$ if there exist $2n$ real numbers $x_1,x_2,\ldots,x_{2n}$, not all equal, such that the sum of any $n$ of the $x_i$'s is equal to the product of the other $n$ of the $x_i$'s. Help Cookie Monster determine all crunchy integers. Yannick Yao
Problem
Source: 2016 ELMO Problem 1
Tags: algebra, number theory
24.06.2016 17:13
My solution: We claim that the crunchy integers are precisely the even integers. First of all, it is obvious that $1$ is not crunchy; since if there existed $x_1,x_2$ satisfying the conditions, then $x_1=x_2$, contradicting the given condition that not all of the $x_i$'s are equal. The fact that $2k$ is crunchy follows from the example $(x_1,x_2,x_3,\cdots , x_{4k})=(-1,-1,-1,\cdots, -1,2k).$ Now suppose there is a odd crunchy integer $n> 2$, and $x_1,x_2,\cdots ,x_{2n}$ satisfy the conditions. First of all we prove the following result: For any $n+1$ numbers among the $x_i$'s, either they are all equal or their sum is $0$. Proof. Choose any $n+1$ numbers among the $x_i$'s; without loss of generality (WLOG) assume that they are $x_1,x_2,\cdots x_{n+1}.$ If they are all equal, then we are done; otherwise there exist two among these which are not equal; assume WLOG $x_1\neq n_{n+1}$. Also, at least one of these two is not equal to $S=\sum_{1\le i\le n+1}x_i$; say it is $x_1$. Then applying the given condition we have: \begin{align*}&x_1+x_2+\cdots +x_n=x_{n+1}x_{n+2}\cdots x_{2n}\implies S-x_{n+1}=x_{n+1}x_{n+2}\cdots x_{2n}\\ &x_2+x_3+\cdots+x_{n+1}=x_{n+2}x_{n+3}\cdots x_{2n}x_{1}\implies S-x_1=x_{n+2}x_{n+3}\cdots x_{2n}x_{1}\end{align*}Dividing the first equation by the second gives (note that the LHS and hence the RHS of the 2nd equation is non-zero, making such division valid): $$\frac{S-x_{n+1}}{S-x_1}=\frac{x_{n+1}}{x_{1}}.$$If $S=0$ then we are done; otherwise using componendo, we get from the above equation: $$\frac{S-x_{n+1}}{S-x_1}=\frac{x_{n+1}}{x_{1}}=\frac{S}{S}=1\implies x_1=x_{n+1}$$contradicting the choice of $x_1,x_{n+1}$. Hence the claim. $\square$ Now since not all the $x_i'$s are equal, there are two distinct numbers among them, say $x_1\neq x_2$. We claim that all the rest $x_i$'s must be equal. If not, suppose there exist two other numbers not equal, WLOG say $x_3\ne x_4$. Then for any group of $n+1$ $x_i$'s containing $x_1$ and $x_2$, their sum must be zero, since they can't be all equal. Therefore choose a $n+1$-tuple of $x_i$'s containing $x_1,x_2,x_3$ but not $x_4$, (this is possible because $n>2$), and their sum must be zero. Replace $x_3$ by $x_4$, and the sum still must be zero. This forces $x_3=x_4$, a contradiction. So all the other numbers are equal. If they are different from both of $x_1$, then using the same logic with distinct numbers $x_1,x_3$, yields $x_2=x_3=\cdots =x_{2n}\ne x_1$. Now because of the lemma, $nx_2+x_1=0\implies x_1=-nx_2$ and by the condition, we get $x_2^{n-1}x_1=nx_2$. Now $x_2=0$ quickly yields a contradiction, so the second equation gives $x_2^{n-2}(-nx_2)=n\implies x_2^{n-1}=-1$, which is impossible since $n-1$ is even. Thus our claim is proved. $\blacksquare$
24.06.2016 17:42
Since $2n$ numbers are not all equal so there exists two numbers that is different from each other. Assume that two number is $x_1 \ne x_2$. Let $a_1,a_2, \cdots , a_{2n-2}$ is an arbitrary permutation of $x_3,x_4, \cdots , x_{2n}$ then from the given condition, we have $$x_1 \cdot a_1a_2 \cdots a_{n-1}=x_2+a_{n}+ a_{n+1}+ \cdots + a_{2n},$$and $$x_2 \cdot a_1a_2 \cdots a_{n-1}=x_1+a_n+a_{n+1} + \cdots +a_{2n},$$which follows $(x_1-x_2)(a_1a_2 \cdots a_{n-1}+1)=0$. Hence, $a_1a_2 \cdots a_{n-1}=-1$ since $x_1 \ne x_2$. This implies that the product of any $n-1$ numbers of $x_3,x_4, \cdots , x_{2n}$ is equal to $-1$. Therefore, $x_3 \cdot x_5 \cdots x_{n+1}x_{n+2}=x_4 \cdot x_5 \cdots x_{n+2}=-1$ implies $x_3=x_4$. Similarly, we will find that $x_3=x_4= x_5= \cdots = x_{2n}=a$. We have $x_3x_4 \cdots x_{n+1}=a^{n-1}=-1$ implies $a=-1$ and $n$ is even. Now, we will prove that all $n$ even are crunchy numbers. From the given condition, we will have $$1=x_3x_4 \cdots x_{n+2}=x_1+x_2+(x_{n+3}+ \cdots + x_{2n})=x_1+x_2+2-n.$$This follows $x_1+x_2=n-1$. We pick $x_1=n, x_2=-1$ and we need to show that for all $n$ even, the $2n$ real numbers $(n,-1,-1, \cdots , -1)$ satisfies the condition. Indeed, from above, it's already true for the case where we pick $n$ numbers that are equal to $-1$ and take its product. Now, we only need to check where we take the product of $n$ numbers such that one of them is equal to $n$. This case is true since $(-1)^{n-1} \cdot n=-n=(-1)+(-1)+ \cdots +(-1)$ ($n$ numbers $-1$). Thus, all even positive integer $n$ are crunchy integers.
24.06.2016 17:43
What about n=1?
24.06.2016 17:48
24.06.2016 18:02
jeff10 wrote: What about n=1? This fails? If we have two real numbers $x_1$ and $x_2$ which are distinct then $x_1=x_2$ does not hold.
24.06.2016 18:07
sorry what is ELMO?!
24.06.2016 18:33
Elmo Lives Mostly Outside https://en.wikipedia.org/wiki/Elmo
24.06.2016 21:16
25.06.2016 02:17
My solution $n$ is an even number. First of all it's easy to check that if $n$ is a crunchy number then $x_{1}*x_{2}*\ldots*x_{2n}$ can't be zero. Next,when $n$ is bigger than $1$,as $x_{1}+x_{2}+\ldots+x_{n}=x_{n+1}*x_{n+2}*\ldots*x_{2n}$ and $x_{1}+x_{2}+\ldots+x_{n-1}+x_{n+1}=x_{n}*x_{n+2}*x_{n+3}*\ldots*x_{2n}$ Subtracting them we get $(x_{n}-x_{n+1})(x_{n+2}*x_{n+3}*\ldots*x_{2n}+1)=0$ As $x_{1},x_{2},\ldots,x_{2n}$ are not all equal,there exists at least one pair of $(i,j)$ such that $x_{i}-x_{j}$ is not $0$.WLOG it's $x_{1},x_{2}$ So with the same method up (subtracting),we can get $x_{n+2}*x_{n+3}*\ldots*x_{2n}=-1,x_{n+1}*x_{n+3}*x_{n+4}*\ldots*x_{2n}=-1$,with $x_{1}*x_{2}*\ldots*x_{2n}$ can't be zero we get $x_{n+1}=x_{n+2}$ Hence we get $x_{3}=x_{4}=\ldots=x_{2n}=-1$,so $n$ must be even,and also $x_{1}+x_{2}=n-1,x_{1}*x_{2}=-n$,so $x_{1}=-1,x_{2}=-n$,and we can see immediately that it is right. Your sincerely CeuAzul
25.01.2020 23:56
We claim the answer is $n$ even. If $n$ is even, take $(x_1,\ldots,x_{2n}) = (n,-1,-1,\ldots,-1)$, which clearly works. Now suppose $n$ is odd. Suppose some there existed some $i,j$ such that $x_i \not= x_j$. Then \begin{align*} x_1+x_2+\ldots+x_{n-1} + x_i &= \tfrac{P}{x_1x_2\cdots x_{n-1} x_i} \\ x_1+x_2+\ldots+x_{n-1} + x_j &= \tfrac{P}{x_1x_2\cdots x_{n-1} x_j}, \end{align*}where $P$ is the product of all $x_i$'s. It is not hard to see that subtracting the equations gives that either $x_i=x_j$ or $\prod_{i\in A} x_i = -1$ for any subset $A \subseteq \{1,\ldots,2n\} \setminus \{i,j\}$ of size $n-1$. This clearly means all the $x_k$'s except for $x_i$ and $x_j$ are equal. Say this value is $x$. Then $(n-1)x+x_i=x^{n-1}x_j$, so $x_i=x^{n-1}x_j-(n-1)x$. Similarly, $x_j=x^{n-1}x_i-(n-1)x$. Subtracting gives $x_i-x_j=x^{n-1}(x_j-x_i)$, so $x^{n-1}=-1$, so $x=-1$. Therefore, $x_j=x_i +(n-1)$ and $x_i=x_j + (n-1)$, contradiction.
02.02.2020 16:43
I claim the answer is $n$ even. To see this, take the construction $(x_1,x_2,\ldots,x_{2n})=(-1,-1,\ldots,-1,n)$. It is easily checked that this construction suffices. Now we show that $n$ cannot be odd. Since not all $x_i$ are equal, say WLOG that $x_1 \neq x_2$. Now, take the two equations $x_1+\sum_{i=3}^{n+1} x_i = x_2 \cdot \prod_{i=n+2}^{2n} x_i$ and $x_2+\sum_{i=3}^{n+1} x_i = x_1 \cdot \prod_{i=n+2}^{2n} x_i$. Subtracting the second from the first gives $x_1-x_2 = (x_2-x_1)(\prod_{i=n+2}^{2n} x_i)$. Since $x_1 \neq x_2$, we can divide both sides by $x_1-x_2$ to get $\prod_{i=n+2}^{2n} x_i=-1$. We can repeat this for each subset of size $n-1$ from the set $\{3,4,5,\ldots,2n\}$ to get that the product of all elements of that subset is $-1$. Take the two products $x_3x_4 \ldots x_{n+1}$ and $x_{n+2}x_4 \ldots x_{n+1}$. Since every element of the product is nonzero, this gives $x_3=x_{n+2}$. Repeating this for every pair of products eventually gives that $x_3=x_4=\ldots=x_{2n}$. This means that $x_3x_4 \ldots x_{n+1}=(x_3)^{n-1}=-1$, which is impossible since $n-1$ is even and $x_3$ is real. Thus, this completes the proof, as required.
18.03.2023 19:44
This showed up in today's codeforces contest https://codeforces.com/contest/1806/problem/C
19.03.2023 02:33
MathWizard10 wrote: This showed up in today's codeforces contest https://codeforces.com/contest/1806/problem/C lol yeah. It was fun.
27.10.2023 18:48
The construction of evens is obvious. It's easy to see that if $n$ is a crunchy number then $x_{1} x_{2}\cdots x_{2n}$ can't be zero. Now we have the following 2 equations: $x_{1}+x_{2}+\ldots+x_{n}=x_{n+1}x_{n+2}\ldots x_{2n}$ $x_{1}+x_{2}+\ldots+x_{n-1}+x_{n+1}=x_{n}x_{n+2}x_{n+3}\cdots x_{2n}$ This means that $(x_{n}-x_{n+1})(x_{n+2}\ldots x_{2n}+1)=0$. Now let's assume that $x_1\neq x_2$. applying the above argument we have that: $x_{n+2}x_{n+3}\ldots x_{2n}=-1$ $ x_{n+1}x_{n+3}x_{n+4}\ldots x_{2n}=-1$ Which means $x_{n+1}=x_{n+2}$. Now since $x_1\cdots x_{2n} \neq 0$. $x_{3}=x_{4}=\ldots=x_{2n}=-1$ We have that $x_1=-1$ and $x_2=-n$ Which consequently means that $n $ must be even. And we are done.
17.05.2024 16:49
Answer: $n$ must be even with construction $x_{2n}=n$ and all other $X_i$ are $-1$. We now make the following key claim. Claim: There do not exist $X_i,x_j,x_k$ all pairwise unequal. Proof. Consider a subset $S'$ of $S=\{1,2,\dots,2n\}$ with $n$ elements. Also, set $P=\prod x_i$ and $s=\sum x_i$. Then multiplying the problem condition on $S'$ and $S \setminus S'$ we get $P=\left(\sum_{i \in S'}x_i\right)\left(s-\sum_{i \in S'}x_i\right)$. By say the quadratic formula this implies $\sum_{i \in s}x_i$ can only take at most $2$ distinct values, If the claim was false then we take any set of $n-1$ values in $S$ not containing $i,j,k$ and append $i,j,k$ to this set to get $3$ distinct values. $\blacksquare$ Thus there exist exactly $2$ distinct numbers among that $x_i$, say $a,b$. WLOG that $a$ appears $\geq n$ times in the list. \[a^n = (n-1) a + b = z, \qquad a^{n-1} = na = z+a-b\]so $z+a-b= z\cdot \frac ba$ so $z=-a$. Thus $a^n=-a$, which when $n$ is odd forces $a=0$. This then forces $b=0$ by taking a set of $n-1$ zeros and $b$, implying no list exists when $n$ is odd.
27.07.2024 09:06
Note that $x_{1}, x_{2},\dotsc, x_{2n}$ can't be zero. Now because all the elements cannot be equal, so WLOG assume $x_n\neq x_{n+1}$ and the rest are all equal. So we have $x_{1}+x_{2}+\ldots+x_{n}=x_{n+1}x_{n+2}\ldots x_{2n}$ and we consider the following polynomial as well $x_{1}+x_{2}+\ldots+x_{n-1}+x_{n+1}=x_{n}x_{n+2}x_{n+3}\cdots x_{2n}$ After subtracting we get: $$x_{n+1}-x_n=(x_n-x_{n+1})\biggl(\prod_{i=n+2}^{2n}{x_i}\biggr)$$This gives us $\biggl(\prod_{i=n+2}^{2n}{x_i}\biggr)=-1$ Note that this works for all subsets of $(x_{1}, \cdots, x_{n-1}, x_{n+2}, \cdots, x_{2n})$ Now we let all other $x_i$'s except $x_n$ and $x_{n+1}$ be $t$. So we have: \begin{align*} &x_n+(n-1)t=t^{n-1}x_{n+1} \\ &x_{n+1}+(n-1)t=t^{n-1}x_{n}. \implies t^{n-1}=-1 \end{align*}This is true for $n$ even and not when $n$ is odd. Examples: $(1,1,\cdots, n,1,\cdots,1)$ and $(-1,-1,\cdots,n,\cdots,-1)$. Here $n$ is $x_{n+1}.$
17.09.2024 01:11
We want stuff to cancel idea lets gooo. Trivially $n=1$ fails as it gives $x_1=x_2$. So WLOG suppose that $x_1 \ne x_2$ then let $y_1, \cdots y_{2n-2}$ be any permutation of $(x_3,x_4, \cdots x_{2n})$ then notice that we have that $x_1 \cdot y_1 \cdots y_{n-1}=x_2+y_n+\cdots y_{2n-2}$ and $x_2 \cdot y_1 \cdots y_{n-1}=x_1+y_n+\cdots+y_{2n-2}$ then subtracting both and canceling $x_1-x_2$ from both aides we get that $y_1 \cdots y_{n-1}=-1$ so the product of any $n-1$ reals among $x_3, \cdots x_{2n}=-1$, this means none of the them can be zero and therefore if you consider two products that differ by only one term, them those terms are equal so we have that $x_3=x_4 \cdots =x_{2n}$ so we have that $x_3^{n-1}=-1$ which means that $n$ must be even. Now for a construct for $n$ even just consider $(x_1,x_2 \cdots, x_{2n})=(n, -1, \cdots -1)$ which trivially work thus we are done .