6
$\begingroup$

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}$.

$\endgroup$
  • 3
    $\begingroup$ I use the pigeon-hole-principle very rarely, but here it could be useful. $\endgroup$ – Peter Oct 14 '15 at 18:14
  • $\begingroup$ @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. $\endgroup$ – mathlove Oct 14 '15 at 18:25
  • $\begingroup$ Related, but not a duplicate: math.stackexchange.com/questions/186866/… $\endgroup$ – user940 Oct 14 '15 at 18:30
  • $\begingroup$ What does 177 count? I get 89 "nests" so even $n=14$ should work, because ${14\choose 2}=91>89.$ $\endgroup$ – user940 Oct 14 '15 at 18:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Oct 14 '15 at 18:40
3
$\begingroup$

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}.

$\endgroup$
  • $\begingroup$ Thanks. My understanding is that your solution supposes that there can be the same number in $a,b,c,d$. Is this correct? $\endgroup$ – mathlove Oct 14 '15 at 19:02
  • $\begingroup$ @mathlove Yes, that is possible. For distinct numbers, I get only get down to $n=15$. See the solution that I linked to above. $\endgroup$ – user940 Oct 14 '15 at 19:03
  • $\begingroup$ 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.) $\endgroup$ – mathlove Oct 14 '15 at 19:37
  • $\begingroup$ 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 $\endgroup$ – Ross Millikan Oct 14 '15 at 19:38
  • $\begingroup$ @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. $\endgroup$ – mathlove Oct 14 '15 at 20:01
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Please elaborate $\endgroup$ – QuIcKmAtHs Jan 20 '18 at 13:55
  • $\begingroup$ @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. $\endgroup$ – Clive Bach Jan 22 '18 at 14:00
  • $\begingroup$ oh. no. i wasn't looking for a code. I think i understand now. $\endgroup$ – QuIcKmAtHs Jan 22 '18 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.