-2

Using the pigeonhole principle, prove that if we choose 14 different numbers from the following set {1, 2, 3, 4,...,20}, then definitely there are two numbers such as a and b (among our 14 selected numbers) which their difference is at least 7 (i.e. |a-b| ≥7)

Jenny
  • 7
  • 2
    Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Jan 01 '24 at 03:38
  • 1
    What have you tried? It isn't even close, as if you choose any eight integers with no restriction on the range there are two whose difference is at least seven. – Ross Millikan Jan 01 '24 at 04:24

1 Answers1

1

Assume there exist $14$ different numbers that we can choose such that the smallest difference is $6$, or that there are $6$ numbers between the largest and smallest. Then, by the pidgeonhole princple, we must have chosen at least one number twice, since $14 > 6$. This is a contradiction, since all of our numbers are unique. Hence, we must have a difference of at least $7$.

Redo the phrasing since it's a bit convoluted but this is the main concept of the pidgeonhole principle through a contradiction.

Robert Murray
  • 1,788