# Counting Subset Properties

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!

• 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. – Ross Millikan Feb 27 '13 at 3:49

## 2 Answers

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.

@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.

• 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. – muzzlator Feb 27 '13 at 3:48
• @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). – Ross Millikan Feb 27 '13 at 3:51
• 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? – user64093 Feb 27 '13 at 3:53
• @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. – Ross Millikan Feb 27 '13 at 3:57
• Oh...What you were saying makes perfect sense now. Thanks a bunch! – user64093 Feb 27 '13 at 4:01