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$

put on hold as off-topic by user21820, Jendrik Stelzner, Paul Frost, Adrian Keister, Cesareo 2 days ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Jendrik Stelzner, Paul Frost, Adrian Keister, Cesareo
If this question can be reworded to fit the rules in the help center, please edit the question.

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$
  • $\begingroup$ I didn't want to offend you, it is part of standard terminology. And I'm sorry you don't understand the answer. $\endgroup$ – Maria Mazur Aug 1 '18 at 10:52
  • $\begingroup$ Did you mean $f: A \to \{1, 2, \ldots, 100\}$? $\endgroup$ – N. F. Taussig Aug 11 '18 at 11:07
  • $\begingroup$ Why did you include 100? @N.F.Taussig $\endgroup$ – Maria Mazur Aug 11 '18 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$ – N. F. Taussig Aug 11 '18 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$
  • 1
    $\begingroup$ This is exact solution as here: math.stackexchange.com/questions/2865068/… $\endgroup$ – user582949 Aug 11 '18 at 6:10
  • $\begingroup$ Oops, snipped :( $\endgroup$ – tarit goswami Aug 11 '18 at 6:11
  • $\begingroup$ But, that solution is not complete, so I will not delete it. $\endgroup$ – tarit goswami Aug 11 '18 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$ – N. F. Taussig Aug 11 '18 at 8:24
  • $\begingroup$ @N.F.Taussig Yeah, thank you! $\endgroup$ – tarit goswami Aug 11 '18 at 9:53

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