1

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?

FoiledIt24
  • 933
  • 1
  • 10
  • 21

3 Answers3

6

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.

TheSilverDoe
  • 29,720
1

HINT: Note that $55 = 4\times 12 + 7$. So either

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

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

Mike
  • 20,434
0

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

Will Jagy
  • 139,541