1
$\begingroup$

Let $N=\{1,2,...,100\}$ and $A$ be a subset of $N$ with $|A|=55$. Show that $A$ contains two numbers with difference $9$. Is this also true for $|A|=54$?

I was trying to solve this via the pigeonhole principle:

Consider pairs of elements taken from $N$ with differences of $9$. e.g. $\{1,10\}, \{2,11\}, \{3,12\}, \ldots , \{n, n+9\}$, where $1 \leq n \leq 91$, as the lower and upper bounds of $N$ are $1$ and $100$. Thus there are $91-1= 90$ possible pairs which result in a difference of $9$. I reasoned that thus, if $|A|=91$, that via the pigeonhole principle, the extra element would necessarily have to pair and be a difference.

However, intuitively this seems wrong (also obviously so since it asks me to prove $|A|$ must only equal $55$). I think I am misunderstanding the application of the pigeonhole principle...any help/alternative solutions would be appreciated!

$\endgroup$
  • $\begingroup$ The problem with your approach is that if $10 \in A$, you can't have either $1$ or $19$ but you are only counting one of them. $\endgroup$ – Ross Millikan Feb 27 '13 at 3:49
3
$\begingroup$

Look at the numbers modulo $9$. There are $55$ numbers you are putting into $9$ categories, at least one of the modulo classes has $7$ numbers in there. If they were all separated by at least $18$, they would have minimum difference of $108$ from the biggest and smallest element.

$\endgroup$
1
$\begingroup$

@Serkan had a good idea but deleted it-if s/he restores it I will delete this. Think about $\{1,10\}$ through $\{9,18\}$ and repeat that through $\{81,90\}$ plus $\{91,100\}$. That is $46$ pairs that you can only have one of.

$\endgroup$
  • $\begingroup$ Should be noted that $46$ pairs of things means 8 numbers don't belong in any class, but that would still give you $55 - 8 = 47$ numbers to put into those pairs. $\endgroup$ – muzzlator Feb 27 '13 at 3:48
  • $\begingroup$ @muzzlator: correct. I was leaving that for OP, but no problem. Both of our approaches get there (and actually result in very similar sets for the $54$ part of the question). $\endgroup$ – Ross Millikan Feb 27 '13 at 3:51
  • $\begingroup$ Ah...So {1,10}, {2,11}, ...{9, 18}, {19, 28}, {20, 29}, ..., {27, 36}, {37, 46}, ......, {81, 90}, {91, 100}, such that each number from 1-100 only appears in exactly ONE pair. There are 46 of these. Am I then correct in saying that any set A above size 46 satisfies the stated property? $\endgroup$ – user64093 Feb 27 '13 at 3:53
  • $\begingroup$ @user64093: no, because you haven't accounted for $[92,99]$. That is $8$ items, all of which can be in $A$, and you can only have one of each of the $46$ pairs, for a total of $54$. But having $[92,99]$ constrains the choices from the other pairs. $\endgroup$ – Ross Millikan Feb 27 '13 at 3:57
  • $\begingroup$ Oh...What you were saying makes perfect sense now. Thanks a bunch! $\endgroup$ – user64093 Feb 27 '13 at 4:01

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.