this was Peru IMO TST

My solution used the fact that $e^2<8$

IAmTheHazard wrote: My solution used the fact that $e^2<8$ Wait, isn't that true? Or im just dumb.

Here's a very different solution: We can assume $x_1, \cdots, x_n\in (0,1]$ because if there are $k$ zeroes, removing them gives a weaker version of the inequality for $n\mapsto n-k$ in the problem. Suppose FTSOC otherwise, that $2^{j-i}x_ix_j\le 2^{s-3}$ for all $i,j$. First, we take logarithms with base 2: $$\log_2(x_i)+\log_2(x_j)\le s-3+i-j$$Now we use a lemma. Lemma: For all $x\in (0,1]$ we have $\log_2(x)\ge \frac{3}{2}\left(1-\frac{1}{x}\right)$ Proof: The inequality $\ln(x)\ge c\left(1-\frac{1}{x}\right)$ is true for all $c$ (well-known). Therefore we have for all $i,j$ with simple simplification, $$\frac{1}{x_i}+\frac{1}{x_j}\ge 4+\frac{2(j-i)-2s}{3}$$Name this equation $(i,j)$. We make use of another lemma: Lemma: For all $x,y\in (0,1]$, if $\frac{1}{x}+\frac{1}{y}\ge c$ where $c\ge 2$, we have $x+y\le \frac{1}{c-1}$. Proof: Just consider how $y$ varies as $x$ varies and we see that $x=1$ is optimal, from which the lemma follows. This lemma will be useful to us when $$4+\frac{2(j-i)-2s}{3}\ge 2\implies j-i\ge s-3$$Now the idea is that when $s=n$ there is nothing to prove. When $n-1\le s<n$, we have that $$\frac{1}{x_1}+\frac{1}{x_n}\ge 4+\frac{2n-2-2s}{3}$$$$x_1+x_n\le \frac{3}{9+2n-2-2s}<1$$Which is a contradiction as $x_2+\cdots+x_{n-1}\le n-2$. This same process works in general, for an $s$ with $n-k\le s<n-k+1$, we take the equations $(1,n-k+1), \cdots, (k,n)$. For each equation, $$\frac{1}{x_i}+\frac{1}{x_j}\ge 4+\frac{2(n-k)-2s}{3}$$$$x_i+x_j\le \frac{3}{9+2(n-k)-2s}<1$$Therefore $$x_1+x_2+\cdots+x_k+x_{n-k+1}+\cdots+x_n<k$$By summing globally. Hence $s<k+(n-2k)=n-k$, which is a contradiction. This last part is a bit different when $s\le \frac{n}{2}$, how you resolve this case is just doing taking the pairs $(1,n/2+1),(2,n/2+1),\cdots,(n/2,n)$ and the same inequalities work. EDIT: See post #9, I've made an error. A similar global approach should still work.

Complete_quadrilateral wrote: IAmTheHazard wrote: My solution used the fact that $e^2<8$ Wait, isn't that true? Or im just going crazy. It is true but I'm sad that I had to use it

yofro wrote: Lemma: For all $x,y\in (0,1]$, if $\frac{1}{x}+\frac{1}{y}\ge c$ where $c\ge 2$, we have $x+y\le \frac{1}{c-1}$. Proof: Just consider how $y$ varies as $x$ varies and we see that $x=1$ is optimal, from which the lemma follows. should be $\frac c{c-1}$ instead of $\frac1{c-1}$

IAmTheHazard wrote: Complete_quadrilateral wrote: IAmTheHazard wrote: My solution used the fact that $e^2<8$ Wait, isn't that true? Or im just going crazy. It is true but I'm sad that I had to use it Maybe post your solution since it turns out that #7 was false, and I suppose that you had the same idea. Although it is kinda cool that my solution is the only one atm.

Well at MOP I did get a 7 on my solution so it's probably right, but the idea is the following: Suppose that $2^{j-i}x_ix_j \leq 2^{s-3}$. Prove that if $x_i<1$ for all $i$, we can scale all the terms by some $r>1$ (such that the conditions are still true) and the inequalities get stronger. I did this by taking a derivative twice, which is where I used $e^2<8$. Then for any $1<k \leq n$, if $x_k>2x_{k-1}$, I prove that we may increase $x_{k-1}$ to $\tfrac{1}{2}x_k$ (only making the inequalities stronger). This is not that hard by considering some cases and analyzing how $x_ix_j$ changes but there is a slippery edge case. After this, I prove that for any $1<k<n$, if $x_k \leq 2x_{k-1},2x_{k+1}$, and $x_k<1$, we may increase $x_k$ to $\max \{2\min\{x_{k-1},x_{k+1}\},1\}$. Then given any $n$ reals according to the problem statement, we first smooth to get some terms equalling $1$, and then repeatedly apply claims $2$ and $3$ as long as we can (i.e. the claims actually do something). Once we get stuck, the resulting sequence has some $1 \leq l \leq r \leq n$ such that $a_i=1$ for all $l \leq i \leq r$, but $a_{l-1},a_{r+1} \neq 1$ (if they exist), and also has $a_{l-i}=\frac{1}{2}a_{l-i+1}$ and $a_{r+i}=\frac{1}{2}a_{r+i-1}$ for all $i>1$, provided they exist. The rest is just some computation which essentially reduces the problem to proving that $16a_{l-1}a_{r+1}<4^{a_{l-1}+a_{r+1}}$, so it suffices to show that $4x\leq 4^x$ for $\tfrac{1}{2} \leq x \leq 1$, which is calculus again. This should be basically the same as your solution

Let $a$ be the maximum value of $2^{-i}x_i$ over all $1\leq i\leq n$ and let $b$ be the maximum value of $2^jx_j$ over all $1\leq j\leq n$. Then, we claim there exists $i$, $j$ such that $2^{j-i}x_ix_j>2^{s-3}$ if and only if $ab>2^{s-3}$. If $2^{j-i}x_ix_j>2^{s-3}$, then $ab\geq2^{j-i}x_ix_j>2^{s-3}$. If $ab>2^{s-3}$, then there exists $i$ and $j$ such that $a=2^{-i}x_i$ and $b=2^jx_j$, so $2^{|j-i|}x_ix_j\geq2^{j-i}x_ix_j=ab>2^{s-3}$. Now, suppose $ab\leq2^{s-3}$. Replacing $x_i$ with $\min(1,2^ia,2^{-i}b)$ increases $s$ and keeps $a$ and $b$ the same, so $ab\leq2^{s-3}$ after this operation. Suppose $x_i=2^ia$ for all $i<p$, $x_i=2^{-i}b$ for all $i>q$, and $x_i=1$ for all $p\leq i\leq q$. Then, we get \begin{align*} s&=\sum_{i=1}^{p-1}x_i+\sum_{i=q+1}^nx_i+(q-p+1)\\ &=a\left(2+4+\ldots+2^{p-1}\right)+b\left(\frac1{2^{q+1}}+\ldots+\frac1{2^n}\right)+(q-p+1)\\ &=\left(2^p-2\right)a+\left(\frac1{2^q}-\frac1{2^n}\right)b+(q-p+1)\\ &<2^pa+\frac1{2^q}b+(q-p+1) \end{align*} If $p\leq q$, then we have $1\leq2^pa,2^{-q}b\leq2$. Otherwise, $3\leq2^pa+\frac1{2^q}b$, so since $2^pa,2^{-q}b\leq2$, we get $2^pa,2^{-q}b\geq1$. Since $2^{x-1}-x$ is convex and has roots at $x=1$ and $x=2$, we get $2^{x-1}\leq x$ for all $1\leq x\leq2$, so \begin{align*} 2^{s-3+p-q}\geq2^{p-q}ab\\ &=\left(2^pa\right)\left(2^{-q}b\right)\\ &\geq2^{2^pa-1}2^{2^{-q}b-1}\\ &=2^{2^pa+2^{-q}b-2}\\ &=2^{2^pa+2^{-q}b+(q-p+1)+(p-q-3)}\\ &>2^{s+p-q-3}, \end{align*} contradiction. Therefore, we cannot have $ab\leq2^{s-3}$, so there must exist $i$ and $j$ such that $2^{j-i}x_ix_j>2^{s-3}$.

Weird problem. Tastes mid. Just color each $x_i$ based on $2^{\lfloor \log_2 x_i \rfloor}$, then characterize the color space by weakening the inequality to deal with only the worst case bound for each color. Assume the inequalities all fail. Then freely assume using weaker condition's freedom that $s$ is an integer to obtain conditions on the spacing of the colors. Then we have that $\min_{k \geq 0} \frac{s+k}{2^k} = s$ because $s \geq 3$, so it follows that the total sum of $x_i$ is strictly smaller than the integer floor of $s$, giving contradiction.

This problem has such a unique taste. Suppose the contrary, $2^{j-i}x_ix_j\leq 2^{s-3}$ for any $1\leq i< j\leq n$. Assume that $$a:=\sum\limits_{i=1}^lx_i\geq 1>\sum\limits_{i=1}^{l-1}x_i$$$$b:=\sum\limits_{j=n-k+1}^nx_j\geq1>\sum\limits_{j=n-k+2}^nx_j$$Then $a,b\in [1,2)$. Because $x_i\in [0,1]$, and $\sum\limits_{i=l+1}^{n-k}x_i=s-a-b$, we know that $n-k-l\geq \lceil s-a-b \rceil$. Let $y_i=x_i\cdot 2^{l-i}$ for $1\leq i\leq l$, $z_j=x_{n+1-j}\cdot 2^{k-j}$ for $1\leq j\leq k$. Set $p=\max\{y_i\}$, $q=\max\{z_j\}$. From the hypothesis we claim that $pq\cdot 2^{n-k-l+1}\leq 2^{s-3}$, therefore $$pq\leq 2^{s-4-(n-k-l)}\leq 2^{s-4-(s-a-b)}=2^{a+b-4} $$Note that $$a=\sum\limits_{i=1}^lx_i=\sum\limits_{i=1}^l\frac{y_i}{2^{k-l}}\leq p\sum\limits_{i=1}^l\frac{1}{2^{k-l}}<2p$$Analogously $b<2q$. Hence $$ab<4pq\leq 4\cdot 2^{a+b-4}=2^{a-1}\cdot 2^{b-1}$$However due to the convexity of $f=2^{x-1}-x$ and $f(1)=f(2)=0$ we know that $f$ is nonpositive on $[1,2)$, thus $2^{a-1}\leq a$ and $2^{b-1}\leq b$. Contradiction.

Is the solution on the shortlist correct? Don't you need both $u$ and $v$ to be at most $b-a$ for the first sums?

Complete_quadrilateral wrote: \ Claim: Let $x_1+x_2+\dots x_{M-1}=s_1$. We claim that this sequence is the strongest when the largest $\left \lfloor s_1\right \rfloor-1$ elements in that sum are $1$.(that is $x_{M-\left \lfloor s_1\right \rfloor+1},\dots x_{M-1}$)

Sorry, I fail to understand why this claim is true. If I understand correctly, in your proof you assumed i, j are the indices that works given that $x_1+x_2+\dots x_{M-1}=s_1$, then construct a sequence as well as i, j such that the claim works with the additional requirement that "the largest $\left \lfloor s_1\right \rfloor-1$ elements in that sum are $1$" (call this * condition). Now if you shall prove that (given with $x_1+x_2+\dots x_{M-1}=s_1$) sequences with the * condition is the strongest among all sequence, you should prove the other way around (i.e. if such sequence with * condition with has working i, j indices, then so does any other sequence). No?

Acclab wrote: Complete_quadrilateral wrote: \ Claim: Let $x_1+x_2+\dots x_{M-1}=s_1$. We claim that this sequence is the strongest when the largest $\left \lfloor s_1\right \rfloor-1$ elements in that sum are $1$.(that is $x_{M-\left \lfloor s_1\right \rfloor+1},\dots x_{M-1}$)

Sorry, I fail to understand why this claim is true. If I understand correctly, in your proof you assumed i, j are the indices that works given that $x_1+x_2+\dots x_{M-1}=s_1$, then construct a sequence as well as i, j such that the claim works with the additional requirement that "the largest $\left \lfloor s_1\right \rfloor-1$ elements in that sum are $1$" (call this * condition). Now if you shall prove that (given with $x_1+x_2+\dots x_{M-1}=s_1$) sequences with the * condition is the strongest among all sequence, you should prove the other way around (i.e. if such sequence with * condition with has working i, j indices, then so does any other sequence). No? I re-read my proof and it shouldn't have any flaws, but I kind of glossed over some important steps I had idk why, I'll rewrite that part so it is easier to understand when I get home

Complete_quadrilateral wrote: Acclab wrote: Complete_quadrilateral wrote: \ Claim: Let $x_1+x_2+\dots x_{M-1}=s_1$. We claim that this sequence is the strongest when the largest $\left \lfloor s_1\right \rfloor-1$ elements in that sum are $1$.(that is $x_{M-\left \lfloor s_1\right \rfloor+1},\dots x_{M-1}$)

Sorry, I fail to understand why this claim is true. If I understand correctly, in your proof you assumed i, j are the indices that works given that $x_1+x_2+\dots x_{M-1}=s_1$, then construct a sequence as well as i, j such that the claim works with the additional requirement that "the largest $\left \lfloor s_1\right \rfloor-1$ elements in that sum are $1$" (call this * condition). Now if you shall prove that (given with $x_1+x_2+\dots x_{M-1}=s_1$) sequences with the * condition is the strongest among all sequence, you should prove the other way around (i.e. if such sequence with * condition with has working i, j indices, then so does any other sequence). No? I re-read my proof and it shouldn't have any flaws, but I kind of glossed over some important steps I had idk why, I'll rewrite that part so it is easier to understand when I get home Great, but, have you got home yet

Acclab wrote: Great, but, have you got home yet Oops here I am, sry Edit: meh I got kinda lazy it should be a little bit better now, at least u can get the idea, I hope. I was kinda bad at write ups when i wrote that, and if I had to i would just completely rewrite it but idh the energy for that rn

Choose $M$ and $m$ which are the maximal values of $2^jx_j$ and $2^{-j}x_j$. If there is a unique index $j$ where these values are reached, then \[\frac{x_j}{x_i}\ge 2^{|j-i|}\]which implies $s<3x_j\le 3$, a contradiction. Assume now that there are indices $i$ and $j$ at which \[1\le \frac{M}{2^j}<2\]\[1\le m\cdot 2^{i+1}<2\]and now I claim that for $i\le j$ we have \[s<\frac{M}{2^j}+m\cdot 2^{i+1}+(j-i).\]This isn't actually very hard, just realize that \[s\le m(2^1+\dots+2^i)+(j-i)+M\left(\frac{1}{2^{j+1}}+\dots+\frac{1}{2^n}\right)\]which gives the conclusion. When $i>j$ it turns out that we have, say, \[s\le m(2^1+\dots+2^{i-1})+M\left(\frac{1}{2^{j+1}}+\dots+\frac{1}{2^n}\right)<3\]which is a contradiction. Write $x=\frac{M}{2^j}$ and $y=m\cdot 2^{i+1}$ for convenience. We just need \[xy\cdot 2^{j-i-1}\ge 2^{x+y+(j-i)-3}\]by direct substitution. This reduces to \[xy\ge 2^{x+y-2}\]and now we can just prove $x\ge 2^{x-1}$ for $x\in [1,2)$ to finish, which is direct Bernoulli. final notes: not exactly very hard, it's extremely rigid and thus straightforward. you don't have a lot of options for proceeding and it is essentially all a smoothing argument.

It's been a while since I posted on AoPS, but I thought that some of you might be interested in knowing the origins of this problem. It came out of a research project in extremal combinatorics that I was working on for my undergraduate thesis a few years ago with my friend Nitya (and advised by Jacob Fox). Very roughly, we were interested in understanding the properties of a certain type of graph that comes out in the study of partially ordered sets called a Hasse diagram. These graphs tend to be very sparse (few edges), and so one should expect them to generally have pretty large independent sets (sets of vertices with no edges between them). But is that really the case? Do there exist Hasse diagrams where all of the independent sets are quite small? We had a certain probabilistic construction in mind that seemed likely to show that there are some Hasse diagrams where all the independent sets are have size at most roughly $n/\log n$ (where $n$ is the number of vertices), a modest improvement over what was previously known. The inequality in this problem turned out to be a crucial step in proving this (at a very high level, it implies that the construction fails with probability strictly less than 1). We didn't end up publishing it because coincidentally another group got the same result with a completely different proof and they published it first. That bound has since been improved, but last I checked the right answer is still open, somewhere between roughly $\sqrt{n \log n}$ and $n^{3/4}$. Maybe one of you will close the gap . If you want to read more, I very recently put up my thesis here (this problem is a modified version of Lemma 3.10). I proposed the problem because I thought was sort of interesting and unique; an inequality with a distinctly combinatorial flavor, which I had never seen before in olympiads. It's probably not that surprising when you realize it came from a combinatorics problem, but I think the original problem would be impossible to guess from this one. At the same time, like many of you I thought it would be a super weird olympiad problem. Among the problems I proposed, I would have thought it was almost the least likely to be on the shortlist, but sometimes that's how the PSC rolls. As final observation, I will say that while the emergence of these kinds of rigid structures can be off-putting in olympiads, it's super exciting in research -- it means that you can understand something deeply and fully. I hope that can be a helpful perspective as you all go forward on your mathematical journey, wherever it takes you. Happy solving!

Revenge. Enjoyed this problem a lot! Let $i$ and $j$ be the positive integers such that $2^{-i}x_i = \max\{2^{-k}x_k \mid 1 \leq k \leq n\}$ and $2^{j}x_j = \max\{2^kx_k \mid 1 \leq k \leq n\}$. It is clear that $2^{j-i}x_ix_j$ is the largest value our expression can take. This implies that $j \geq i$. Let $\alpha$ and $\beta$ be the largest positive integers such that $2^{\alpha}x_i \leq 1$ and $2^{\beta}x_j \leq 1$. Observe that $2^{j}x_j \geq 2^kx_k \implies 2^{j-k}x_j \geq x_k$ and hence $x_{j- \beta} + x_{j -\beta + 1} + \dots + x_n < 2^{\beta+1}x_j$. Similarly, $x_{i+ \alpha} + x_{i + \alpha - 1} + \dots + x_1 < 2^{\alpha+1}x_i$. If $j - \beta \leq i + \alpha$, we get $s \leq (x_1 + x_2 + \dots x_{i+\alpha}) + (x_{j-\beta+1}+ x_{j-\beta+2} + \dots + x_n) < 2^{\alpha+1}x_i + 2^{\beta}x_j \leq 3$, a contradiction. So, assume that $j - \beta > i + \alpha$. Note that this implies $j > i$. Then $s-3 = x_1 + x_2 + \dots + x_n - 3 < 2^{\alpha+1}x_i + 2^{\beta+1}x_j + j-i-\alpha - \beta -4$. Plugging this into our inequality, it suffices to show that $2^{j-i}x_ix_j \geq 2^{2^{\alpha+1}x_i + 2^{\beta+1}x_j + j-i-\alpha - \beta -4} > 2^{s-3}$ which is equivelant to $ab \geq 2^{2a+2b-4}$ where $a=2^{\alpha}x_i$ and $b=2^{\beta}x_j$. Recall that $a, b \in [\frac{1}{2}, 1]$. Therefore, it suffices to prove that $x \geq 2^{2x-2}$, for all $x \in [\frac{1}{2}, 1]$. Letting $2^y=x$, this is equivelant to $2^y \geq 2^{2^{y+1}-2} \Leftrightarrow y \geq 2^{y+1}-2$ for all $y \in [-1, 0]$ which is trivial by Bernoulli's inequality. $\blacksquare$

Select $b>a$ such that $2^{b-a}x_ax_b$ is the maximal term of the form $2^{j-i} x_i x_j$. Then, by definition, $2^{b-i} x_i x_b \leq 2^{b-a} x_a x_b$ and $2^{i-a} x_i x_a \leq 2^{b-a} x_a x_b$. This means a few things: $x_{a-k} \leq \frac 1{2^k} x_a$ and $x_{b+k} \leq \frac 1{2^k} x_b$, and $x_i \leq 1$ for all $a \leq i \leq b$. Let $A = 2^\alpha x_a \leq 1 < 2^{\alpha + 1} x_a$ and define $\beta$ similarly. If $\alpha + \beta \geq b-a$, then \[S < A\left(1+\frac 12+\frac 14+\cdots\right) + \frac 12B\left(1+\frac 12+\frac 14+\cdots\right) = 2A+B \leq 3.\]This is a contradiction. So let $b-a-(\alpha+\beta) = k$. Then \[s < (k-1) + A\left(1+\frac 12+\frac 14+\cdots\right) + B\left(1+\frac 12+\frac 14+\cdots\right) < 2A+2B+k-1.\]Also, \[2^{(b-a)x_ax_b} = 2^{\alpha} x_a \cdot 2^{\beta} x_b \cdot 2^{b-a-\alpha-\beta} = 2^k \cdot AB.\]Thus we just need to show that $AB \geq 4^{A-1} \cdot 4^{B-1}$. This is easy as $A-4^{A-1} \geq 0$ for all $A \in \left[\frac 12, 1\right]$.

think of the solution and write it down Well, let's take the $i$ and $j$ that maximize the LHS then. (If there is a tie, tiebreak arbitrarily.) Note that the parts for $i$ and $j$ are separate so they are separately optimal. We are first going to show an example that will illustrate the main idea. \begin{align*} \color{red} \dots \qquad \le 0.15 \qquad \le 0.3 \qquad x_i & \color{red} = 0.6 \qquad \color{green} \le 1 \qquad \le 1 \qquad \\ \color{green} \dots \qquad \le 1 \qquad \color{blue} \le 0.8 \qquad x_j & \color{blue} = 0.4 \qquad \le 0.2 \qquad \le 0.1 \qquad \dots \end{align*} The idea is that: The red and blue $\le 2^k x$'s are there because we took $i$ and $j$ to be optimal. The green $\le 1$s are there because, well, each term is $\le 1$. The red and blue dots can extend as far as you want. The idea is just that the sum of the entire tail before $x_i$ will be less than $x_i$, and similarly for $x_j$. The blue part has an extra $\le 0.8$ because we will need a tighter bound than $1$. Now the first thing to note is that the sum of the red and blue parts besides their heads (the number closest to the green) will always be less than $2$. In particular, this implies that we will never get "scammed" out of a red or blue number, since even if we add one of the two heads, we will still have $s<3$. Great, so that's all the setup we will need. Now just note that \[s< \color{green} j-i-1 \color{black}+ \color{red} 2x_i+\left(\sum_{k=1}^{\infty}\underbrace{\min(2^k x_i-1,0)} _{\text{correction term for if $\le 2^k x_i$ exists}}\right) \color{black}+ \color{blue} 2x_j+\left(\sum_{k=1}^{\infty}\underbrace{\min(2^k x_j-1,0)}_{\text{similar}}\right) \color{black}. \]Define $f_k(x)=\min(2^k x_i-1,0)$ and $f(x)=\sum_{k=1}^{\infty}f_k(x)$. Then the inequality we want to prove reduces to \[x_ix_j\ge 4^{-2+x_i+x_j}\cdot 2^{f(x)}.\]We claim that the following is just true for all $x\in[0,1]$: \[4x\ge 2^{2x+f(x)}.\]Indeed, let $x=2^{-m}\cdot t$ where $m$ is a positive integer and $1\le t<2$. (Manually check $x=1$ works.) Then $2^k x_i-1<0$ when $k<m$, so \[2x+f(x)=2x+\sum_{k=1}^{m-1}(2^k x-1)=2^m x-(m-1)=t-m+1.\]Thus we want to show \[4\cdot 2^{-m}\cdot t\ge 2^{t-m+1}\longleftrightarrow t\ge 2^{t-1}.\]This is just straightforward calculus: if $f(t)=t-2^{t-1}$, then $f''(t)=-(\ln 2)^2 2^{t-1}<0$, so $f$ is concave. Then since $f(1)=f(2)=0$, we get $f(t)>0$ when $1<t<2$. $\blacksquare$ Remark. Graphing the function $x\cdot 2^{-2x-f(x)}$ on Desmos and seeing the equality cases magically line up is quite satisfying, especially if you put it on a logarithmic scale. Here's a link: https://www.desmos.com/calculator/0zduz5xfwn