Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

I think it should be $9$. Let's work $\pmod{20}$, so when I say distinct, for example, I mean distinct $\pmod{20}$. If we look at systems consisting of distinct numbers, then we see that $7$ suffice, because they form $21$ pairs, so there must be two pairs with the same sum, and two such pairs cannot share one of the members. If a number appears more than once, then no other number can appear more than once, and a certain number cannot appear more than three times, so the number we're looking for is at most $9$ (in the case $a,a,a,b,c,d,e,f,g$). If we find a counterexample for $8$, we will have shown that the answer is $9$. Here are $8$ numbers for which $a+b-(c+d)\ne 0,\ \forall a,b,c,d$ distinct: $0,0,0,1,2,4,7,12$. This shows that the answer is $9$.

Sorry to revive such an old post, but I don't see why the answer can't be seven. I also don't understand what you mean in this part: Quote: If a number appears more than once, then no other number can appear more than once, and a certain number cannot appear more than three times, so the number we're looking for is at most 9 (in the case a,a,a,b,c,d,e,f,g).

This solution was found in collaboration with yugrey, SkinnySanta, antimonyarsenide. First, remark that $8$ fails due to $1,21,41,2,3,5,8,13$. Now to prove given $9$ elements we can find the four $a,b,c,d$. First suppose there are four elements in the set $a,b,c,d$ such that $a \equiv b \pmod{20}$ and $c \equiv d \pmod{20}$. But then $20|(a+c - b - d)$, so we can assume at most one element is repeated modulo $20$. It is clear this repeated residue modulo $20$ can appear at most $3$ times. Thus remove repeats in our set and we are left with at least $7$ elements. Now consider all sums $a+b$ modulo $20$ for $a,b$ in our modified set. Note that if $a+b \equiv c+d \pmod{20}$ for distinct sets $\{a,b\}, \{c,d\}$, then $20|(a+b-c-d)$, contradiction (note that we cannot have $a \equiv c \pmod{20}$ or $a \equiv d \pmod{20}$ because then it would follow $\{a,b\} = \{c,d\}$ due to us taking out repeated elements modulo $20$), so it follows the pairs are distinct modulo $20$. But there are at least $\dbinom{7}{2} = 21 > 20$, so two must be equal and therefore we are done as any $9$ element set then has $4$ $a,b,c,d$ satisfying the problem condition.

Well, we can shorten the solution as follow: First, we list 8 "failed" number (mod $ 20 $ ): $ 1,1,1,2,3,5,8,13 $ Second, we count how many sums of the form $ a+b (\mod 20) $ there are in $n $ given numbers, it is $ n \choose 2 $ if $ n\geq 7 $ then $ {n\choose 2} \geq {7\choose 2} =21>20 $ then by the Pigeonhole Principle we get the answer is $ 9 $ Editted

You forgot about duplicates modulo $20$ That makes the answer $9$.

dinoboy wrote: You forgot about duplicates modulo $20$ That makes the answer $9$. Oops, I forgot it

You still haven't justified why when there are $9$ numbers we can find at least $7$ distinct ones.

For $n=8$; the example set(s) are already given. For $n=9$, let the set be $S=\{a_1,\dots,a_9\}$; there are $\binom{9}{2}=36$ distinct pairs. Clearly; two of them must occupy the same congruence class in modulo $20$. Now, if those pairs share no common elements; we are done. If not, they share exactly one element (since they are distinct pairs). Without loss of generality, let $p_1=(a_1,a_2)$, and $p_2=(a_1,a_3)$. We have $a_2\equiv a_3\pmod{20}$. Now, erase $a_2$ and $a_3$; and consider $S'=\{a_1,a_4,a_5,\dots,a_9\}$. Since $|S'|=7$; there are $\binom{7}{2}=21$ pairs, two of which are congruent in modulo $20$. If, again, they are distinct, we are done. If not, there are $a_i$ and $a_j$ (as above), such that, $a_i\equiv a_j\pmod{20}$. Hence, it suffices to take, $(a,b,c,d)=(a_i,a_2,a_j,a_3)$.

I can give a proof like this . Let there are \(n,n\geq 4\) numbers \(a_1,a_2,.....a_{n-1},a_n\), all are distinct. Now if for four distinct numbers \(a+c-b-d\) is divisible by 20 then \(|(a-b)(mod 20)|=|(c-d)(mod20)|\). Where the modulos vary from -9 to 10 over the integers. So, in sake of simplification we say that the order pair of two elements, let \((a_i,a_j)=|(a_i-a_j)(mod 20)|\). And we shall work with this pairs from now on. So, our goal is to prevent four numbers from satisfying the given condition (\(20|a-b+c-d)\) . So to do that we have put our maximum effort not to give any of those disjoint pairs (\((a_p,a_q)=(a_k,a_l)\), p,q,k,l all are distinct) to be equal, namely . Intersecting pairs may be equal because we are asked for four distinct numbers. So, to do this we will proceed like this. Let,\(0\leq (a_p,a_k)=r\leq 10\). And let, all \(r\)'s are used to prevent equality with the best effort. Without loss of generality we take \((a_1,a_2)=0\). Now, if any of the values \((a_p,a_q)=0;p,q=3,4,....n-1,n\), then we are failed (we will have for distinct numbers \(a_1,a_2,a_k,a_l;k,l \in\){\(3,4,...n-1,n\)} such that \(20|a_1-a_2+a_k-a_l\) ). So, to prevent them from being \(0\) we should give them other \(9\) values (\(1,2...10\)). Now, there are \(A=\)\(\frac{(n-2)(n-3)}{2}\) numbers of pairs with no \(a_1\),\(a_2\) . Now, if we have two equal-valued disjoint pairs in \(S=\) {\((a_p,a_q) ;p,q=3,4,....n-1,n\)} then we are failed. But if two intersecting \((a-p,a_q)=(a_p,a_k)\) pair with a common element \(a_p\) are of equal values then \((a_p,a_q)~(a_p,a_k)=(a-q,a_k)=0\) or \( 2r\); as we had taken modulus ;\((a-q,a_k)\) surely may not be only \(0\) but \(2r or 2r(mod 20)\). Then we will be failed again. So, we have \(\frac{(n-2)(n-3)}{2} > 2*10 \geq 21 \Rightarrow n-2 \geq 7 \Rightarrow n\geq 9 \). We can take two non-disjointpairs equal \(\rightarrow\) at most "twice" because the equality of pairs does not imply the fail of our prevention. But an extra equality fails our prevention. So, the least such \(n\) is equal to \(9\).

The answer is $n=9.$ When $n=8$, we have $(0,1,2,4,7,12,20,40)$ Clearly, if we have from these $9$ numbers, at least $7$ distinct residues $\pmod 20$, then we are done, because from these $7$ distinct residues, there are $21$ sums, so we can find two such that $a+b\equiv c+d\pmod 20.$ If the seven numbers are distinct $\pmod 20$ then $a,b,c,d$ must be four different numbers. Now, if we have $a,b,c,d$ all equivalent $\pmod 20$, then $a+b-c-d\equiv 0\pmod 20$, we're done. If $a,b$ are equivalent and $c,d$ also are, then $a+c-b-d\equiv 0\pmod 20$, and we're also done. Thus, at most one residue is repeated, and each residue is repeated at most thrice, so we can find $7$ distinct residues, as desired.

Excellent! Surprised little posts, it's a straightforward problem... The answer is 9. Indeed, our problem rephrased is that a+b=c+d mod 20, and if they're all distinct, 7 numbers suffices with 21 pairs. On the other hand, if some number is repeated, no other numbers can be repeated otherwise we take that a_1+b_1=a_2+b_2 where a_1=a_2 and b_1=b_2. To find a lower bound the "worst" case scenario is when there's three of one number, with the rest distinct, this means our answer is 9. Finally, it is easily seen that 0,0,0,1,2,4,7,12 that has 8 numbers does not work (it is easy to find a counterexample since for simplicity and trial just start with 3 0s, then, place as many small numbers as you can without satisfying the problem, namely 3 doesnt work since 3+0=2+1, 5,6,8,9,11 similarly, and 10+1=7+4). $\blacksquare$ In contest, do we have to give a counterexample? A friend told me that I should to be safe but I'm not sure..

huashiliao2020 wrote: Excellent! Surprised little posts, it's a straightforward problem... The answer is 9. Indeed, our problem rephrased is that a+b=c+d mod 20, and if they're all distinct, 7 numbers suffices with 21 pairs. On the other hand, if some number is repeated, no other numbers can be repeated otherwise we take that a_1+b_1=a_2+b_2 where a_1=a_2 and b_1=b_2. To find a lower bound the "worst" case scenario is when there's three of one number, with the rest distinct, this means our answer is 9. Finally, it is easily seen that 0,0,0,1,2,4,7,12 that has 8 numbers does not work (it is easy to find a counterexample since for simplicity and trial just start with 3 0s, then, place as many small numbers as you can without satisfying the problem, namely 3 doesnt work since 3+0=2+1, 5,6,8,9,11 similarly, and 10+1=7+4). $\blacksquare$ In contest, do we have to give a counterexample? A friend told me that I should to be safe but I'm not sure.. This is a correct proof. In contest you must give a counterexample for full credit as the counterexample is part of the proof that that is indeed the smallest value. If it said instead 'prove there exists n' then there is no need.

$\color{magenta}\boxed{\textbf{SOLUTION N3}}$ Let, $S={a_1,a_2,....a_n}$ If we have $a_i\equiv a_j \pmod {20}$ and $a_k\equiv a_l \pmod {20}$ for $i \ne j \ne k \ne l$ Then set, $a=a_i,b=a_k,c=a_j,d=a_l$ and we are done So, Assume we don't have this case, Then we can have atmost $3$ elements having same residue module $20$ call $a_x,a_y,a_z$ Remove any two of them to get $S'={a_1,a_2,...a_x,...a_n}, |S'|=n-2$ Now consider all of the numbers of the form $(a_i+a_j)$ for $i\ne j$ If we get $a_i+a_j\equiv a_k+a_l \pmod {20}$ we are done again So, Assume all of the sums have different residues modulo $20$ There are $\binom{n-2}{2}$ sums We always get $a_i,a_j,a_k,a_l \in S'$ such that $a_i+a_j\equiv a_k+a_l \pmod {20}$ if $\binom{n-2}{2} \ge 20$ Gives, $n\ge 9$ So, $n_{min}=9 \blacksquare$

We claim that $n=9$, the counter example for $n=8$ is $\{0,0,0,1,2,4,7,12\}$. If $n=9$, then if there exists elemnts s.t. $a \equiv b$ and $c \equiv d$ (all in mod $20$) then we're done, so assume this does not happen, similarly a number cannot repeat more than 3 times. Since $\binom{7}{2} = 21 > 20$, we're done.

Obviously reduce to numbers in $\{1,\dots,20\}$. If $n=8$ take $(1,1,1,2,3,5,8,13)$. Now consider the frequency multiset. Only one number can be greater than $1$; otherwise write $a+b-a-b$ to yield a contradiction. This number is either $2$ or $3$, otherwise $a+a-a-a$ is a contradiction. If $n\ge 9$ then the multiset has at least seven values. It suffices to show that for any seven distinct $a_1,\dots,a_7\in \{1,\dots,20\}$ there are four where \[a_x+a_y\equiv a_i+a_j\pmod {20}.\] Using variables above, first only assume $(x,y)$ and $(i,j)$ are distinct. Then as $\binom{7}{2}=21>20$ we know there exist distinct $a_x$, $a_y$ and $a_i$, $a_j$ satisfying the condition. However $a_x=a_i$ for example is not possible as it implies $a_y=a_j$, a contradiction to the implicit requirement that pair $(a_x,a_y)$ is distinct from $(a_i,a_j)$. $\blacksquare$