Prove that if we randomly pick 39 numbers then there will always be 3 of them with the property that their pairwise differences are divisible by 19.
Let be randomly picked numbers. Now we will look at the set modulo 19 (or, remainders modulo 19).So let
be the remainder set i,e .
Now there are 19 remainders and 39 numbers. Therefore by pigeon hole principle( box principle) there are at least 39/19 numbers same amongst in the remainder set. 39/19>2, and it has to be an integer so we get 3 numbers having same remainder modulo 19 so their pairwise differences are divisible by 19. Proved.
Get Answers For Free
Most questions answered within 1 hours.