Question

Prove that if we randomly pick 39 numbers then there will always be 3 of them...

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.

Homework Answers

Answer #1

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.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
3. Prove the following about the Fibonacci numbers: (a) Fn is even if and only if...
3. Prove the following about the Fibonacci numbers: (a) Fn is even if and only if n is divisible by 3. (b) Fn is divisible by 3 if and only if n is divisible by 4. (c) Fn is divisible by 4 if and only if n is divisible by 6.
Let N2K be the set of the first 2k natural numbers. Prove that if we choose...
Let N2K be the set of the first 2k natural numbers. Prove that if we choose k + 1 numbers out of these 2k, there is at least one pair of numbers a, b for which a is divisible by b.
Prove that 1+2+3+...+ n is divisible by n if n is odd. Always true that 1+2+3+...+...
Prove that 1+2+3+...+ n is divisible by n if n is odd. Always true that 1+2+3+...+ n is divisible by n+1 if n is even? Provide a proof.
Prove deductively that for any three consecutive odd integers, one of them is divisible by 3
Prove deductively that for any three consecutive odd integers, one of them is divisible by 3
prove that 2^2n-1 is divisible by 3 for all natural numbers n .. please show in...
prove that 2^2n-1 is divisible by 3 for all natural numbers n .. please show in detail trying to learn.
Prove that (n − 1)^3 + n^ 3 + (n + 1)^3 is divisible by 9...
Prove that (n − 1)^3 + n^ 3 + (n + 1)^3 is divisible by 9 for all natural numbers n.
Prove the following using induction: (a) For all natural numbers n>2, 2n>2n+1 (b) For all positive...
Prove the following using induction: (a) For all natural numbers n>2, 2n>2n+1 (b) For all positive integersn, 1^3+3^3+5^3+···+(2^n−1)^3=n^2(2n^2−1) (c) For all positive natural numbers n,5/4·8^n+3^(3n−1) is divisible by 19
3.a) Let n be an integer. Prove that if n is odd, then (n^2) is also...
3.a) Let n be an integer. Prove that if n is odd, then (n^2) is also odd. 3.b) Let x and y be integers. Prove that if x is even and y is divisible by 3, then the product xy is divisible by 6. 3.c) Let a and b be real numbers. Prove that if 0 < b < a, then (a^2) − ab > 0.
Assume that when adults with smartphones are randomly​ selected, 39​% use them in meetings or classes....
Assume that when adults with smartphones are randomly​ selected, 39​% use them in meetings or classes. If 30 adult smartphone users are randomly​ selected, find the probability that exactly 21 of them use their smartphones in meetings or classes.
From the numbers between 1 to 30, find out how many of them are divisible by...
From the numbers between 1 to 30, find out how many of them are divisible by 2 and 4. When a number is divisible by 3, print "Three". When a number is divisible by 5, print "Five". When a number is divisible by both, print "ThreeFive". Otherwise, just print the number
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT