1
$\begingroup$

A set $M = \{1,2,\ldots,100\}$ is divided into seven subsets with no number in $2$ or more subsets. How do you prove that one subset either contains four numbers $a$, $b$, $c$, and $d$ such that $$a + b = c + d$$ or three numbers $p$, $q$, and $r$ such that $$p + q = 2r\,?$$ I am having some issues with this question whether I don't fully understand the question or my arithmetic is wrong. Grateful for any help.

$\endgroup$
1

3 Answers 3

9
$\begingroup$

By pigeonhole principle some subset $S$ must have at least $15$ members, say $$S=\{a_1,a_2,....a_k\}$$ where $k\geq 15.$

Let $$A:=\{(x,y),\;x,y\in S, x<y\}$$

Now observe a function $$f:A\longrightarrow \{1,2,...,99\}$$ which is (well) defined with $$f(x,y) = y-x$$

Clearly, since $|A|= {k\choose 2} \geq {15\choose 2} = 105$ this function is not injective. So there are $a,b,c,d$ such that $$f(a,b)= f(c,d)\implies b-a=d-c\implies b+c=a+d$$

$\endgroup$
3
  • $\begingroup$ Did you mean $f: A \to \{1, 2, \ldots, 100\}$? $\endgroup$ Aug 11, 2018 at 11:07
  • $\begingroup$ Why did you include 100? @N.F.Taussig $\endgroup$
    – Aqua
    Aug 11, 2018 at 14:28
  • 1
    $\begingroup$ After rereading your solution, I now realize that $\{1, 2, 3, \ldots, 99\}$ is the set of possible differences between elements of $S$, so everything makes sense. $\endgroup$ Aug 11, 2018 at 14:54
0
$\begingroup$

Suppose, without loss of generality, that $a<c$ and $p<r$. Given conditions are equivalent to:

$$b-d=c-a\quad\lor\quad q-r=r-p\tag{1}$$

So if you have a set of numbers and if in that set you have two distinct pairs of numbers with the same difference between pair members, condition (1) will be satisfied.

In other words, if you want to create a set of numbers with condition (1) not met, differencies calculated from all possible pairs of set members must be different.

Now suppose that you have a set with condition (1) not met. With 100 numbers and 7 sets at least one set will have 15 numbers, according to Pigeonhole principle. Denote the smallest set member with $x$. The next smallest set member is no less than $x+1$. The third smallest set member is no less than $x+1+2$. It cannot be $x+1+1$ because the first 3 numbers would satisfy (1). Continue in the same way and you'll conclude that the smallest possible value of the 15th set member is:

$$x+1+2+...+14=x + 105\ge106>100$$

Obviously a contradiction.

$\endgroup$
0
$\begingroup$

As you have understood the pigeon hole principle(PHP), and assuming in discrete math you have already studied functions and there types, you can see by PHP at least one subset $S$ must have at least $15$ numbers. Let, $S=\{p_1,p_2,\cdots,p_k\},k\ge 15$.

Now, consider this set :$$S'= \{ (x,y):x,y\in S~~ \& ~~x<y \}$$ Then due to non injectiveness of the function:$$f=y-x$$ with domain $S'$ and range $\{1,2,\cdots ,100\}$. We can find $a,b,c,d$ such that $f(a,b)=f(c,d)$ or, $b-a = d-c$ or, $b+c =a+d$. Now, if two of them are same,means $f(q,r)=f(r,p)$ or, $f(r,q)=f(p,r)$(observe that, in case when you consider $f(r,q)=f(r,p)$, then $p=q$, as the function is well defined) then we will have $q-r=r-p$ which gives $q+p=2r$.

$\endgroup$
5
  • 1
    $\begingroup$ This is exact solution as here: math.stackexchange.com/questions/2865068/… $\endgroup$
    – user582949
    Aug 11, 2018 at 6:10
  • $\begingroup$ Oops, snipped :( $\endgroup$ Aug 11, 2018 at 6:11
  • $\begingroup$ But, that solution is not complete, so I will not delete it. $\endgroup$ Aug 11, 2018 at 6:13
  • 1
    $\begingroup$ It is not true that any subset must have at least $15$ members. What you mean is that at least one subset has at least $15$ elements. $\endgroup$ Aug 11, 2018 at 8:24
  • $\begingroup$ @N.F.Taussig Yeah, thank you! $\endgroup$ Aug 11, 2018 at 9:53

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