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?

  • $\begingroup$ @Arthur I meant the $2^{nd}$ part of your question . I'll edit that $\endgroup$ Sep 28 '17 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 '17 at 10:29
  • $\begingroup$ See my explanation in answer beneath. $\endgroup$ Sep 28 '17 at 10:36
  • $\begingroup$ Use the Pigeonhole Principle. $\endgroup$
    – Shaun
    Sep 28 '17 at 10:47
  • $\begingroup$ I already said that in my OP. $\endgroup$ Sep 28 '17 at 10:48

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.


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.

  • $\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$ Sep 28 '17 at 10:35
  • $\begingroup$ @AnonymousI I still don't see how this will help you with the question $\endgroup$
    – Stefan4024
    Sep 28 '17 at 11:05
  • $\begingroup$ I made a wrong assumption. $\endgroup$ Sep 28 '17 at 11:06

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.