9
$\begingroup$

Suppose that $A$ is a set of 16 distinct natural numbers and that $1\leq p\leq100$ for every $p$ in $A $.

Prove that $A$ contains 4 different numbers $a$, $b$, $c$, and $d$, such that $a+b=c+d$.

  • 0
    Please clarify your question. What is $p$? Are the numbers $a,b,c,d$ supposed to belong to $A$?2012-08-25
  • 0
    How many of $a,b,c,d$ are supposed to be distinct?2012-08-25
  • 0
    all of them are distinct2012-08-25
  • 3
    It would be nice to see some motivation for this, and some evidence that you have put some thought into it yourself.2012-08-25
  • 0
    What do you mean with motivation? I have worked on this problem for 4 hours. But i haven't found anything useful.2012-08-25
  • 1
    I mean, why have you worked on this problem, and not some other? Did you make it up? Did you find it somewhere? Is it part of a homework assignment? Does some other result depend on it? There is no shortage of mathematical problems a person could pose; why this one?2012-08-26
  • 1
    I went to a mathematical olympiad this morning. There where three problems. I solved two out of three, I couldnt solve this one. I want to know how to solve it because I feel like it may be useful in another olympiad2012-08-26
  • 1
    Good! That's what I like to see....2012-08-26

3 Answers 3

5

This is number 17 of the introductory problems section in the book 102 Combinatorial Problems from the training of the USA IMO team by Titu Andreescu and Zuming Feng.

Here is a paraphrase of their solution.

There are ${16\choose 2}=120$ pairs of numbers from $A$. Since the absolute differences range from 1 to 99, there must be two different pairs $\{a,c\}$ and $\{d,b\}$ with $a-c=d-b$ and hence $a+b=c+d$.

The problem is that $\{a,b,c,d\}$ may not be distinct. Well, what could go wrong? We may end up with pairs like $\{7,6\}$ and $\{6,5\}$. In this case, we may call the number 6 "bad". Generally, we call $a\in A$ a bad number if there exist $a_1 with $a_2-a=a-a_1$.

Note that if $a$ is bad for two different pairs of pairs, then we have a solution. That is, if $a_1 so that $a_2-a=a-a_1$ and $a_3 so that $a_4-a=a-a_3$, then we have $a_1+a_2=a_3+a_4$. You can check that $a_1,a_2,a_3,a_4$ really are distinct in this case.

So the only real problem are pairs of numbers in $A$ whose midpoint $a$ also belongs to $A$, such that no other pair has the same midpoint. There are at most 16 such troublesome pairs, so there are $120-16=104$ pairs left. Applying the pigeonhole principle to this reduced set gives the solution.

  • 0
    how do you know that there are only 16 of those troublesome pairs and why is it a problem that $a$ belongs to $A$2012-08-26
  • 0
    There can be at most one "troublesome" pair for every $a\in A$.2012-08-26
  • 0
    It's a problem if $a$ belongs to $A$ because, as in the example, you'd have $7-6=6-5$ and you'd wind up with $7+5=6+6$ and you wouldn't have distinct $a,b,c,d$.2012-08-26
4

Note: This solution is for the problem as originally posed, without the requirement that $a,b,c$, and $d$ be distinct. That requirement makes it significantly harder, and I’ll have to think about it a bit more if I have time.

(I’m assuming that you mean that if $p\in A$, then $1\le p\le 100$.) Here’s an extended hint.

Let $D=\{|a-b|:a,b\in A\text{ and }a\ne b\}$, the set of pair differences.

  1. How many pairs $\{a,b\}\subseteq A$ are there with $a\ne b$?

  2. If $1\le a\le 100$ for every $a\in A$, what numbers could be in $D$? How many such numbers are there?

  3. Use the pigeonhole principle to find $a,b,c,d\in A$ such that $a-c=d-b$.

  • 0
    @Khromonkey: No, I’m asking what the possible values of $|a-b|$ are.2012-08-25
  • 3
    @Khromonkey: It’s conceivable that all of the duplicated distances occur in triples like $4,11,18$ (for distance $7$), in which case you don’t get four distinct numbers. Somehow that possibility has to excluded.2012-08-25
0

a computer search shows that there is a set of 13 numbers between 1 and 100 with no four satisfying a+b=c+d: $$(1, 2, 12, 18, 22, 35, 43, 58, 61, 73, 80, 85, 87)$$ (and 87 is the lowest maximum that is achievable), but that the lowest possible maximum for a set of 14 positive integers with no a+b=c+d is 106: $$(1, 2, 7, 15, 28, 45, 55, 67, 70, 86, 95, 102, 104, 106)$$ so in fact, any set of 14 integers in the range 1 to 100 has repeated sums. (I would have added this as a comment, rather than an answer, but I am new to math.stackexchange, so haven't accumulated the requisite reputation to comment)