Question

How many distinct positive integers would we have to choose from the numbers 1,2,3,.....,2014 to guarantee that some pair of the chosen values has a difference that is a multiple of 5? Explain and use the Pigeonhole Principle

Answer 1

so we want to look at the set of numbers : 1 + 5k, 2 + 5k , 3 + 5k , 4 + 5k .

Answer 2

so count how big k is until you reach 2014

Answer 3

1 + 5*402 = 2011
1 + 5*403= 2016

there might be a more clever way to solve this

Answer 4

4+5(402)....But i don't see how this uses the pigeonhole principle

Answer 5

think about this from a modular arithmetic perspective... how many integers must we pick to guarantee there are two with the same residue mod 5? well, hypothetically, the worst scenario we could have is that none of our integers have the same residue. since there are 5 possible remainders mod 5 (\(0,1,2,3,4\)) we know to have none share the same residue we can have at most 5 integers. having 6 then guarantees two have the same remainder

Answer 6

to put it more succinctly, our pigeonholes are the different congruence classes \(\pmod5\)