18
$\begingroup$

I have a question on combinatorics, related to the pigeonhole principle:

Consider the set $S= \{1,2,3,...,100\}$. Let $T$ be any subset of $S$ with $69$ elements. Then prove that one can find four distinct integers $a,b,c,d$ from $T$ such that $a+b+c=d$. Is it possible for subsets of size $68$?

$\endgroup$
2
  • 2
    $\begingroup$ The answer to the last question is No. A counter-example would be the subset of numbers from 33 to 100. Adding the 3 smallest numbers gives a sum larger than 100. $\endgroup$
    – Jens
    Oct 15, 2017 at 8:52
  • $\begingroup$ obviously.is it possible to solve this using the idea of sum-free sets? $\endgroup$
    – ShBh
    Oct 15, 2017 at 8:56

2 Answers 2

19
$\begingroup$

Well, I just realized that I’ve seen this problem days ago... the solution goes like this:

Let the numbers in $T$ be $1\le a_1<a_2<...<a_{69}\le 100$. Clearly, $a_1\le 32$.

Now, consider the sequences $$b_n:=a_n+a_1, 3\le n\le 69$$ $$c_n:=a_n-a_2, 3\le n\le 69 $$

Apparently, $1 \le b_i,c_i\le 132$. Since the two sequences have totally $134$ elements (greater than $132$), there is some number in both sequences, i.e. $\exists i,j\in \{3,4,\ldots,69\}$ such that $a_i+a_1=a_j-a_2$. Then $a_1+a_2+a_i=a_j$, as desired.

The second question has an answer “false”. Counterexample is the set $\{33,34,\ldots,100\}$

$\endgroup$
1
  • 1
    $\begingroup$ Nice and easy +1 $\endgroup$
    – nonuser
    Oct 15, 2017 at 13:44
1
$\begingroup$

Just an idea.

Divide the set $T=\{a_1<a_2<...<a_{69}\}$ in to two parts. With first $k$ numbers (set $A$) we make all sums (set $A'$) and with the rest of the numbers (set $B$) we make positive differences (set $B'$).

Say $A= \{a_1,a_2,...a_k\}$ (so $a_k\leq 100-(69-k) = 31+k$) and $$A' = \{a_i+a_j|\, i\ne j; i,j\leq k\}$$

Since we have: $$a_1+a_2<a_1+a_3<...<a_1+a_k<a_2+a_k<...<a_{k-1}+a_k$$

then $|A'|\geq 2k-3$ and $A'\subseteq \{3,4,...61+2k\}$

Say $B= \{a_{k+1},a_{k+2},...a_{69}\}$ (so $a_{k+1}\geq k$) and $$B' = \{a_i-a_j|\, i> j\geq k+1\}$$

Since we have: $$a_{69}-a_{68}<a_{69}-a_{67}<...<a_{69}-a_{k+1}$$

then $|B'|\geq 68-k$ and $B'\subseteq \{1,2,3,4,...99-k\}$

Now we have to chose apropriate $k$ such that $|A'\cap B'|\geq 1$.

Say there is no such $k$. Then $|A'\cap B'| =0$ and thus: $$ |A'\cup B'| = |A'|+|B'|\geq 65+k$$

and $|A'\cup B'|\leq \max\{99-k,61+2k\}$. ...

$\endgroup$
2
  • $\begingroup$ kindly explain the bounds of |B'| and |A'| $\endgroup$
    – ShBh
    Oct 15, 2017 at 10:06
  • 1
    $\begingroup$ I did, but true solution now appear and thus no need to read this. $\endgroup$
    – nonuser
    Oct 15, 2017 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .