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

  • 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 '17 at 8:52
  • $\begingroup$ obviously.is it possible to solve this using the idea of sum-free sets? $\endgroup$ – Shubhrajit Bhattachrya Oct 15 '17 at 8:56

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

  • 1
    $\begingroup$ Nice and easy +1 $\endgroup$ – Maria Mazur Oct 15 '17 at 13:44

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

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

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.