Show there must be two numbers in the list whose difference is $12$. This question came up while tutoring: "$55$ numbers are randomly selected from the first $100$ positive integers. Show there must be two numbers in the list whose difference is $12$."
It definitely requires the Pigeonhole Principle but we were unsure how to set it up. My idea was to list all of the possible pairs whose difference is $12$:
$$(1,13), (2,14), \ldots (87, 99), (88, 100)$$ of which there are $88$ pairs. I'm not sure what to do from here.
I know similar questions have been asked here, like this one. Is there a way to apply those techniques to this problem?
 A: The set of all integers between $1$ and $100$ can be written as
$$\lbrace 1,..., 24 \rbrace \cup \lbrace 25, ..., 48 \rbrace \cup \lbrace 49,..., 72\rbrace \cup \lbrace 73, ..., 96 \rbrace \cup \lbrace 97,..., 100 \rbrace $$
If you choose $55$ numbers, then at least $51$ of them are taken in the first four sets. So at least $13$ of them are taken in one of the four sets. Now you can conclude.
A: HINT: Note that $55 = 4\times 12 + 7$. So either

*

*there is an integer $k$ so that there are at least 6 integers
that are $k \mod 12$, or


*there has to be at least 7 integers $k \in \{0,1,\ldots, 11\}$ such that there are 5 numbers picked that are $k \mod 12$.
So fix such a $k$. If 1. is satisfied then there are 6 integers
$j \in \{0,1,\ldots, 8\}$ such that $12j+k$ was picked. If 2. was satisfied then fix such a $k$, and we may also assume $k \in \{7,8,\ldots, 11\}$. So here there would be 5 integers $j \in \{0,1,2,\ldots,7\}$ so that $12j+k$ was picked, so there must be an $i$ s
t. both $12i+k$ and $12(i+1)+k$ were picked.
A: actually the puzzle works with 53 numbers chosen.  Look at arithmetic progressions with common difference 12, up to max 100. In
$$  1, 13, 25, 37, 49, 61, 73, 85, 97 $$
we can choose five members that are not adjacent, namely
$$ 1, 25, 49, 73, 97.$$
The same happens for the sequences beginning $1,2,3,4,$  so we can accommodate $4 \cdot 5 = 20$ numbers without forcing any difference of exactly 12.
For the sequences that begin $5,6,7,8,9,10,11,12$ we get only four spots each;
$$5,17,29, 41, 53, 65, 77, 89 $$
stops early because the next number 101 is above 100.
This sequence can accommodate just four socially distant element, for instance
$$  5, 29, 53, 77. $$
This adds  $8 \cdot 4 = 32$ more numbers: we can accommodate $20+32= 52$ socially distant numbers, but not 53
