Difficulty of EGMO problems this year: P1 < P2 < P3 < P4 < P5 < P6

nice problem

This great problem was proposed by Oleksii Masalitin, who is one of the main problem proposers on Ukrainian olympiads over the last several years, and who has put really much efforts into creating many nice problems. So I'm very happy that his endeavors finally were recognized at the international level.

Wow. After seeing first day with 3 easy problems, I certainly did not expect the second day to be hard(just remember previous year). Note that $(a_i-a_1)+(a_n-a_i)=a_n-a_1$, so if $a_i \neq \frac{a_n+a_1}{2}$, at most $1$ of $a_i-a_1$ and $a_n-a_i$ is interesting. So $a_n-a_1$ is uninteresting and from $n-2$ pairs $(a_n-a_i,a_i-a_1)$ at least $n-3$ have one uninteresting pair. So there are at least $n-2$ uninteresting pairs, so not more than $\frac{n^2-n}{2}-(n-2)=\frac{n^2-3n+4}{2}$ interesting pairs. This can be achieved when $a_2-a_1=1$ and $a_{i+1}-a_i=2^{i-2}$

wrong i guess

rafigamath wrote: Assume that this is true for $n=k$,then for $n=k+1$ we’ll only need to find pairs that include $a_{k+1}$ No, this is not true. Once you add an element, pairs that were previously uninteresting can become interesting pairs.

I hope I do not seem boring

The answer is $\boxed{\binom n2-(n-2)}$, achieved by $a_1=0$ and $a_i=2^i$ for all $i\ge 2$. This clearly works. Let a pair be uninteresting if it is not interesting. We claim that there are at least $n-2$ uninteresting pairs. Let $d=a_n-a_1$. Then for any $k$, $a_n-a_k$ and $a_k-a_1$ add to $d$, so if they are not both $\frac d2$, one of the pairs is uninteresting. The differences being $\frac d2$ happens at most once so we just found $n-3$ uninteresting pairs. The final one is $(1,n)$. $\blacksquare$

The answer is $\frac{n^2-3n+4}{2}$. Let $f(n)$ denote the answer. For $n=3$, let the differences be $a,b,a+b$. The best we can do is set $a=b$ and see that there are 2 interesting differences, which gives $f(3)\geq2$. Note that since the largest difference, precisely $a_n-a_1$ can't be interesting, we can't have $f(n)=\binom{n}{2}$. Hence, $f(n)<\binom{n}{2}$ and in this case $f(n)<\binom32=3$, which forces $f(2)=2$. So, base case is true. Claim: $f(n+1)-f(n)\leq n-1$ for all $n$. Proof. We now induct on $n$ to show that $f(n+1)-f(n)\leq n-1$. Suppose it was possible that $f(n+1)-f(n)\geq n$ for some numbers $a_1, a_2, \ldots, a_n, a_{n+1}$. Clearly, $(a_{n+1},a_1)$ is not interesting. Consider pairs $(a_{n+1},a_2), (a_{n+1},a_3), \ldots, (a_{n+1},a_n)$. Suppose $I$ of them are interesting. Then, $I\leq n-1$. From all pairs $(a_i,a_j)$ with $1\leq i<j\leq n$, there are at most $f(n)$ pairs by definition. These pairs, along with the $I$ others give us at most $I+f(n)\leq f(n)+n-1$ pairs. So, we get at most $f(n)+n-1$ pairs for any $n$, as claimed. $\blacksquare$ Adding up, we get $f(n)\leq f(3)+\sum_{i=3}^{n-1}(i-1) = \frac{n^2-3n+4}{2}$. We now show the equality case. Set $a_1=0$ and $a_{i+1}=2^{i-1}$ for every $1\leq i\leq n-1$. Since $a_n-a_1=2^{n-2}$, while $a_2-a_1, \ldots, a_{n-1}-a_0$ are all smaller powers of 2, we have that $(a_1,a_2),\ldots(a_{n-1},a_1)$ are all interesting. Now, for any $2\leq i<j\leq n$, pair $(a_i,a_j)$ is interesting if $j+1<n$ or $(i,j)=(n-1,n)$. Hence, the only un-interesting pairs are $(a_1,a_n),(a_2,a_n),\ldots,(a_{n-2},a_n)$, which gives $f(n)=\binom{n}2-(n-2)=\frac{n^2-3n+4}{2}$. We are done. $\blacksquare$

interesting The answer is $\binom{n}{2}-(n-2)$. As a construction take $a_i=i$ for $i\in \{1,\dots,n-1\}$ and $a_n=2n-3$. The set of all $a_j-a_i$ is $\{1,\dots,2n-4\}$ thus any of the $\binom{n}{2}-(n-2)$ differences at most $n-2$ will be interesting. The bound is easy: notice that $(a_1,a_n)$ is not interesting and one of $(a_1,a_i)$ and $(a_i,a_n)$ is not interesting unless $2a_i=a_1+a_n$ since one will be more than half of $a_n-a_1$. This yields at least $n-2$ un-interesting pairs. $\blacksquare$

Oh my god,almost trolled by this problem !! Then answer is $\binom{n-1}{2}+1$ Example: $0,1,2,2^2,\dots 2^{n-2}$.All pairs except $(2^{n-2},2^i); i=0,1,2\dots n-4$ and $(2^{n-2},0)$ work so we eliminate $n-2$ pairs and get the desired answer. Now the bound: we need two observations that kill the problem: Claim 1: $(a_n,a_1)$ is not good Proof: obvious since $a_n-a_1$ is the biggest difference and we cannot find a larger one Claim 2: There exist at most one $i$ such that $(a_n,a_i)$ and $(a_i,a_1)$ are both good The idea is that if $(a_i,a_j)$ is a good pair then $a_i-a_j=\frac{a_k-a_l}{2}\le \frac{a_n-a_1}{2}$ so if both pairs are good then we have $a_i-a_1 \le \frac{a_n-a_1}{2}$ and $a_n-a_i \le \frac{a_n-a_1}{2}$; adding them up gives us $a_n-a_1\le a_n-a_1$ so we must have equality meaning $a_i=\frac{a_n+a_1}{2}$ but clearly at most one $i$ can satisfy this so the claim is done. Finish: From the total of $\binom{n}{2}$ pairs we eliminate at least $1+n-2-1=n-2$ pairs so we are done

Solved with ihatemath123 We claim the answer is $\binom{n}{2} - (n-2)$. This can be constructed with $a_1 = 0$ and $a_k = 2^{k-2}$ for $2 \leq k \leq n$. We will show there are at least $n-2$ non-interesting pairs. Let $d = a_n - a_1$. For any $2 \leq k \leq n-1$, consider the values of $a_k - a_1$ and $a_n - a_k$. There is at most one value of $k$ where both values are equal to $\frac{d}{2}$; otherwise, we have at least one pair that doesn't work (one of $a_k - a_1, a_n - a_k$ is greater than $\frac{d}{2}$ ). This gives us $n-3$ non-interesting pairs. Finally, $(a_1, a_n)$ clearly fails, and we are done.

Pyramix wrote: The answer is $\frac{n^2-3n+4}{2}$. Let $f(n)$ denote the answer. For $n=3$, let the differences be $a,b,a+b$. The best we can do is set $a=b$ and see that there are 2 interesting differences, which gives $f(3)\geq2$. Note that since the largest difference, precisely $a_n-a_1$ can't be interesting, we can't have $f(n)=\binom{n}{2}$. Hence, $f(n)<\binom{n}{2}$ and in this case $f(n)<\binom32=3$, which forces $f(2)=2$. So, base case is true. Claim: $f(n+1)-f(n)\leq n-1$ for all $n$. Proof. We now induct on $n$ to show that $f(n+1)-f(n)\leq n-1$. Suppose it was possible that $f(n+1)-f(n)\geq n$ for some numbers $a_1, a_2, \ldots, a_n, a_{n+1}$. Clearly, $(a_{n+1},a_1)$ is not interesting. Consider pairs $(a_{n+1},a_2), (a_{n+1},a_3), \ldots, (a_{n+1},a_n)$. Suppose $I$ of them are interesting. Then, $I\leq n-1$. From all pairs $(a_i,a_j)$ with $1\leq i<j\leq n$, there are at most $f(n)$ pairs by definition. These pairs, along with the $I$ others give us at most $I+f(n)\leq f(n)+n-1$ pairs. So, we get at most $f(n)+n-1$ pairs for any $n$, as claimed. $\blacksquare$ Adding up, we get $f(n)\leq f(3)+\sum_{i=3}^{n-1}(i-1) = \frac{n^2-3n+4}{2}$. We now show the equality case. Set $a_1=0$ and $a_{i+1}=2^{i-1}$ for every $1\leq i\leq n-1$. Since $a_n-a_1=2^{n-2}$, while $a_2-a_1, \ldots, a_{n-1}-a_0$ are all smaller powers of 2, we have that $(a_1,a_2),\ldots(a_{n-1},a_1)$ are all interesting. Now, for any $2\leq i<j\leq n$, pair $(a_i,a_j)$ is interesting if $j+1<n$ or $(i,j)=(n-1,n)$. Hence, the only un-interesting pairs are $(a_1,a_n),(a_2,a_n),\ldots,(a_{n-2},a_n)$, which gives $f(n)=\binom{n}2-(n-2)=\frac{n^2-3n+4}{2}$. We are done. $\blacksquare$ Unfortunately the induction doesn't work, as adding an element can make 'old' pairs interesting. Take for example $a_{n+1}=2a_n-a_i$; you then have $\frac{a_{n+1}-a_1}{a_n-a_1}=2$, making $(a_n, a_1)$ interesting, while it was obviously not counted in $f(n)$.

To my knowledge, currently nobody is aware of a correct inductive solution.

@above you're right, induction is very hard to work with because old pairs can become interesting by adding new pairs. Sadly I did not realize this while writing the solution (I also felt my inductive approach was just too easy to be correct) Here's a proper idea: Construction remains same as before. We show that there are at least $n-2$ un-interesting pairs (and then the bound will be proven). Note that $(n,1)$ cannot be interesting. Note for any $k<l$ if $a_l-a_k>\frac{a_n-a_1}2$, then $(l,k)$ cannot be interesting. We need to ensure to find at least $n-2$ such pairs. Note that $(a_n-a_i)+(a_i-a_1)=(a_n-a_1)$. So, we the maximum of $a_n-a_i$ and $a_i-a_1$ is at least $\frac{a_n-a_1}{2}$ and equality will hold for at most one $i$. Ignoring that $i$, we get our required $n-2$ un-interesting pairs, which means we're done.

Very happy to see my problem on the actual contest Actually, I find it quite tricky for P4 comparing with a difficulty of day 1..

Kifli wrote: Very happy to see my problem on the actual contest Actually, I find it quite tricky for P4 comparing with a difficulty of day 1.. Congrats! The problem is very nice. Definitely my favorite out of the six.

Solution from Twitch Solves ISL: The answer is $\binom{n}{2} - (n-2)$. Construction. We take $a_1 = 0$ and $a_i = 2^{i-2}$ for $i \ge 2$. For example, when $n=5$ we get the following figure: [asy][asy] draw( (0,0)--(8,0), blue ); real e = 0.2; draw( (0,-e)--(0,e), blue ); draw( (1,-e)--(1,e), blue ); draw( (2,-e)--(2,e), blue ); draw( (4,-e)--(4,e), blue ); draw( (8,-e)--(8,e), blue ); label("$0$", (0,e), dir(90), blue); label("$1$", (1,e), dir(90), blue); label("$2$", (2,e), dir(90), blue); label("$4$", (4,e), dir(90), blue); label("$8$", (8,e), dir(90), blue); label("$a_1$", (0,-e), dir(-90), black); label("$a_2$", (1,-e), dir(-90), black); label("$a_3$", (2,-e), dir(-90), black); label("$a_4$", (4,-e), dir(-90), black); label("$a_5$", (8,-e), dir(-90), black); [/asy][/asy] We see that all the pairs $(i,j)$ are interesting except for the cases where $j = n$ and $i \in \{1,2,\dots,n-2\}$. Indeed: If $i=1$ and $j<n$, then $a_j - a_i = 2^{j-2} = \frac{a_{j+1}-a_j}{2}$. If $i>1$ and $j<n$, then $a_j - a_i = \frac{2a_j-2a_i}{2} = \frac{a_{j+1}-a_{i+1}}{2}$. If $i=n-1$ and $j=n$, then $a_j - a_i = 2^{n-3} = \frac{a_n - a_1}{2}$. Proof of bound. Let $m = \frac{a_1 + a_n}{2}$. Notice that If $a_j > m$, then $(1,j)$ is never interesting. If $a_i < m$, then $(i,n)$ is never interesting. This eliminates at least $(n-1)-1$ pairs, one for each index $k$ with $a_k \neq m$. (The pair $(1,n)$ is counted twice here.) This gives the claimed bound.

Same construction. $a_1=0, a_2=2, a_3=2, a_4=4$ For a generalization; $ a_t=2^{t-2}$ for every $t$, $t\ge2$ Let $l=k+1$, then ; $\frac{a_{k+1}-a_{k}}{a_j-a_i}=2=\frac{2^{k-1}-2^{k-2}}{a_j-a_i}=\frac{2^{k-2}}{a_j-a_i}$ Then we get ; $a_j-a_i=2^{k-3}$ $a_{k+1}>a_k>a_j>a_i$ So, $a_k=2^{k-2}>a_j>a_i$ $max(a_j)=2^{k-3}$ Also it is the only case that pays the condition. Because if it is not; $a_j\leq 2^{k-4}$ and $2^{k-4}-a_i=2^{k-3}$ which is wrong. So, if $a_j=2^{k-3}$ then, $a_i=0=a_1$. One pair comes from here. Then accepting $l \neq k+1$ The size is $n$. In that case there is always an interesting integer for each pair. The possibility is $\binom{n-1}{2}$ Answer is; $\binom{n-1}{2}+1$