1
$\begingroup$

Prove that every subset of $55$ elements of the set $\{1,2,3,\ldots,98,99,100\}$ contains at least $2$ numbers with a difference of $9$.

What I've done is used the following trick:

Divide the set into $\{1,\ldots,50\}$ and the second set is determined by the last element of the first set (i.e. $50$) $+$ the elements of the first set consecutively. Then there are $50$ pairs that differ from $50$. So by the pigeon hole principle if you select 55 elements there are 2 elements who form a pair with a difference of $9$.

Would this proof considered to be valid?

$\endgroup$
5
  • $\begingroup$ @Arthur I meant the $2^{nd}$ part of your question . I'll edit that $\endgroup$
    – Anonymous196
    Sep 28, 2017 at 10:17
  • 1
    $\begingroup$ I don't understand your argument. I'd work with pairs of the form $(1,10),\cdots,(9,18),(19,28),\cdots, (27,36),(37,46),\cdots$. $\endgroup$
    – lulu
    Sep 28, 2017 at 10:29
  • $\begingroup$ See my explanation in answer beneath. $\endgroup$
    – Anonymous196
    Sep 28, 2017 at 10:36
  • $\begingroup$ Use the Pigeonhole Principle. $\endgroup$
    – Shaun
    Sep 28, 2017 at 10:47
  • $\begingroup$ I already said that in my OP. $\endgroup$
    – Anonymous196
    Sep 28, 2017 at 10:48

2 Answers 2

Reset to default
5
$\begingroup$

Divide $S=\{1,2,\ldots,100\}$ into the following sets: $$ \{1,10,19,28,37,46,55,64,73,82,91,100\},\quad\text{12 elements} \\ \{2,11,20,29,38,47,56,65,74,83,92\}, \quad\text{11 elements}\\ \{3,12,21,30,39,48,57,66,75,84,93\}, \quad\text{11 elements}\\ \{4,13,22,31,40,49,58,67,76,85,94\},\quad\text{11 elements} \\ \{5,14,23,32,41,50,59,68,77,86,95\}, \quad\text{11 elements}\\ \{6,15,24,33,42,51,60,69,78,87,96\}, \quad\text{11 elements}\\ \{7,16,25,34,43,52,61,70,79,88,97\},\quad\text{11 elements} \\ \{8,17,26,35,44,53,62,71,80,89,98\}, \quad\text{11 elements}\\ \{9,18,27,36,45,54,63,72,81,90,99\}\quad\text{11 elements}. $$ If we pick 55 elements out of these 9 subsets, then in at least one of these subsets, we will have picked at least 7 elements. In such case, in that subset, among the 7 elements, there will be at least a pair of consecutive elements, i.e. of difference 9.

$\endgroup$
0
$\begingroup$

How does the fact that we have $50$ pairs with a difference $50$ helps you conclude there is a pair of integers with differnece $9$?

Here's a hint how to solve this problem. Try to construct a counterexample. Divide the set into subsets modulo $9$. So for example one of the subsets would be: $\{1,10,19,28,37,46,55,64,73,82,91,100\}$. What's the biggest number of integers you can include without having a pair of integers with a difference $9$? Now do the same for all subsets.

$\endgroup$
3
  • $\begingroup$ With the above question I meant that if you have a series of 2n consecutive integers (say $a + 1, a+2, \ldots , a+ 2n-1, a + 2n$) than there are n pairs who have a difference of $n$ namely $(a+1, a + n+1), (a+2, a+ n+2),\ldots , (a + n, a + 2n)$ Now one can state by the pigeon hole principle if one selects more than n elements there are two pairs liable to differ n from eachother. $\endgroup$
    – Anonymous196
    Sep 28, 2017 at 10:35
  • $\begingroup$ @AnonymousI I still don't see how this will help you with the question $\endgroup$
    – Stefan4024
    Sep 28, 2017 at 11:05
  • $\begingroup$ I made a wrong assumption. $\endgroup$
    – Anonymous196
    Sep 28, 2017 at 11:06

You must log in to answer this question.

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