# For any $18$ distinct two-digit numbers, are there four distinct numbers $a,b,c,d$ such that $a+b=c+d$ ? Can we make $18$ small?

I've known that the following proposition is true for $n=20$.

Proposition : For any $n$ distinct two-digit numbers, there exists a set of four distinct numbers $a,b,c,d$ such that $a+b=c+d$.

Then, I began to try to find the minimum of $n$ such that the proposition is true. Then, I've got that the proposition is true for $\color{red}{n=19}$.

Proof that the proposition is true for $n=19$ :

Let the given $19$ numbers be $a_1\lt a_2\lt \cdots\lt a_{19}$. Also, let $\{a_2-a_1,a_3-a_2,\cdots, a_{19}-a_{18}\}=\{b_1,b_2,\cdots, b_{18}\}$ where $b_1\le b_2\le\cdots\le b_{18}$.

Suppose that there exists no set of four distinct numbers $a,b,c,d$ such that $a-c=d-b$.

If $b_n=b_{n+1}$, then there exist $p,q\ (p\lt q)$ such that $a_{p+1}-a_p=a_{q+1}-a_q$, but from the supposition, $q=p+1$ has to hold. It follows from this that there are no three same numbers in $b_n$ and that $\sum_{k=1}^{18}b_k\ge 1+1+2+2+\cdots +9+9=90$, which contradicts that we have $\sum_{k=1}^{18}b_k=a_{19}-a_1\le 99-10=89$. QED

This is all I've been able to get so far. So, my question is the following :

Question : How can we find the minimum of $n$ such that the proposition is true?

Added : Byron Schmuland proves that the proposition is true for $n=14$ under the condition that $a,b,c,d$ are not necessarily distinct. Also, he comments that we can prove that the proposition is true for $n=15$ under the condition that $a,b,c,d$ are distinct according to the solution for a related question.

What I mean in this question is that $a,b,c,d$ are distinct. (sorry, this might not be obvious. So, I add the word "distinct")

We now know that the minimum of $n$ has to be less than or equal to $15$.

Here, I'm going to write the proof for $n=15$ by getting the key idea from the above solution.

Proof that the proposition is true for $n=15$ where $a,b,c,d$ are distinct :

Suppose that there exists no set of four numbers $a,b,c,d$ such that $a-c=d-b$. There are $\binom{15}{2}=105$ ways to choose $2$ numbers from the given $15$ numbers. From the supposition, each difference of their $2$ numbers are distinct except the case when $$i-j=j-k\tag1$$ where $i\gt j\gt k$. Here, for every $j$, there exists at most one $(i,k)$ satisfying $(1)$. This is because if there were distinct $(i,k),(i',k')$ such that $i-j=j-k,i'-j=j-k'$, then the four numbers $i,k,i',k'$ would be distinct and would satisfy $i-i'=k'-k$, which contradicts the supposition. Since $j$ can neither the maximum number nor the minimum number, the number of the patterns where $(1)$ happens is at most $15-2=13$.

Hence, if we eliminate at most $13$ sets of $2$ numbers, then each difference of the $2$ numbers from the remaining $105-13=92$ is distinct. However, the difference of $2$ numbers is either $1,2,\cdots, 88,89(=99-10)$, which is a contradiction. QED

Added : Byron Schmuland and Ross Millikan independently show eleven 2-digit numbers so that every pair has a different sum. So, we now know that the minimum $n_{\text{min}}$ of $n$ has to satisfy $\color{red}{12\le n_{\text{min}}\le 15}$.

• I use the pigeon-hole-principle very rarely, but here it could be useful. – Peter Oct 14 '15 at 18:14
• @Peter: Thank you for the comment. I used the pigeon-hole-principle for $n=20$. (sorry I didn't write about that). We can make 177 nests and $\binom{20}{2}=190\gt 177$. But we have $\binom{19}{2}=171\lt 177$, so I couldn't find a way to use the principle for $n\le 19$. Maybe I'm missing something. – mathlove Oct 14 '15 at 18:25
• Related, but not a duplicate: math.stackexchange.com/questions/186866/… – user940 Oct 14 '15 at 18:30
• What does 177 count? I get 89 "nests" so even $n=14$ should work, because ${14\choose 2}=91>89.$ – user940 Oct 14 '15 at 18:32
• You can improve your approach to lower $n$ somewhat. If you have two $1$'s in the series of $b_i$ you can't have two $2$'s. That is because the two $1$'s have to come from $a_k, a_{k+1}=a_k+1, a_{k+2}=a_k+2$ Now you might have a single $2$ if $a_{k+3}=a_k+4$, but you can't have another one. Similarly, if you have two $3$'s you can only have one $6$. This will drive the minimum sum of the $b_i$'s upward, so it takes fewer of them to exceed $89$. I haven't figured out how much better you can do. – Ross Millikan Oct 14 '15 at 18:40

Update: The following solution and example are for a different problem where we don't insist that $a,b,c,d$ are distinct.

Proof for $n=14$

Let $A$ be a set of 14 distinct 2-digit numbers. There are ${14\choose 2}=91$ pairs of numbers from $A$. Since the absolute differences range from 1 to 89, there must be two different pairs $\{a,c\}$ and $\{d,b\}$ with $a-c=d-b$ and hence $a+b=c+d$.

On the other hand, here are eleven 2-digit numbers so that every pair has a different sum: {18, 35, 37, 39, 59, 71, 83, 86, 89, 94, 99}.

• Thanks. My understanding is that your solution supposes that there can be the same number in $a,b,c,d$. Is this correct? – mathlove Oct 14 '15 at 19:02
• @mathlove Yes, that is possible. For distinct numbers, I get only get down to $n=15$. See the solution that I linked to above. – user940 Oct 14 '15 at 19:03
• Thank you very much. I think I can understand that the proposition is true for $n=15$ under the condition that $a,b,c,d$ are distinct. So, I edited the question to add your result. (please let me know if what I added has something wrong.) – mathlove Oct 14 '15 at 19:37
• I tried a greedy approach, always adding the smallest number that didn't create a problem, which gave $\{10,11,12,14,17,22,30,39,48,62,81\}$ for eleven I suspect that is the size of the largest set with distinct sums, but do not have a proof – Ross Millikan Oct 14 '15 at 19:38
• @ByronSchmuland: I added the proof that the proposition is true for $n=15$ where $a,b,c,d$ are distinct. Thank you. Also, thank you for adding the eleven numbers. – mathlove Oct 14 '15 at 20:01

a computer search shows that there is a set of 13 numbers between 10 and 99 with no four satisfying a+b=c+d: $$(10, 11, 21, 27, 31, 44, 52, 67, 70, 82, 89, 94, 96)$$ but that the lowest possible maximum for a set of 14 integers >= 10 with no $a+b=c+d$ is 115: $$(10, 11, 16, 24, 37, 54, 64, 76, 79, 95, 104, 111, 113, 115)$$ so in fact, the optimum result is that any set of 14 two digit integers contains distinct $a, b, c, d$ with $a+b=c+d$.

• Please elaborate – QuIcKmAtHs Jan 20 '18 at 13:55
• @XcoderX are you asking for the C code for the search or a description of the logic? (I wrote it in Perl, but it was rather slow, so I manually translated the Perl to C to get better performance, so as a C program it's not well structured, but the logic is fine). A comment is too short for either, so whichever you are looking for I will need to add another answer to provide it. – Clive Bach Jan 22 '18 at 14:00
• oh. no. i wasn't looking for a code. I think i understand now. – QuIcKmAtHs Jan 22 '18 at 14:03