Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How will you show that from a set of twelve given natural numbers (arbitrary) you can always find two such that their difference is divisible by $5$?

share|improve this question
3  
What have you tried? –  JavaMan Nov 26 '11 at 4:14
3  
Pigeonhole principle; Hint: from any set of six natural numbers you can always find two whose difference is a multiple of $5$. –  Arturo Magidin Nov 26 '11 at 4:16
5  
By the way, you should work on your question titles. There are very many problems in mathematics that are something with numbers, and knowing that this one is the second you've asked in quick succession is completely useless for someone who reads the lists of questions. –  Henning Makholm Nov 26 '11 at 4:18
add comment

2 Answers 2

up vote 3 down vote accepted

Label your twelve numbers $a_1,\dots,a_{12}$, and consider the eleven differences, $a_1-a_2,\dots,a_1-a_{12}$. These eleven elements cannot all be in different congruence classes modulo $5$, since there are only $5$ such congruence classes. So $$a_1-a_i\equiv a_1-a_j\pmod{5}$$ for some distinct $a_i$ and $a_j$. This implies $a_i\equiv a_j\pmod{5}$. That said, $12$ seems a little large, and you can actually conclude this from a set of only $6$ numbers.

share|improve this answer
1  
I have done it in this way: The last digit[unit's place] of a number may be filled in 10 ways from 0 through 9.So if you have 11 or more numbers you can always find two whose difference will give you zero in the units place. Obviously it is divisible by five. –  Anamitra Palit Nov 26 '11 at 4:52
2  
@AnamitraPalit: I would suggest learning a bit about modulo arithmetic. In fact, your argument shows that among 11 or more numbers, there are always two whose difference is a multiple of ten (let alone a multiple of five). Six numbers are more than enough to guarantee a difference which is a multiple of $5$. In general, you need $n+1$ to guarantee that there are two whose difference is a multiple of $n$. –  Arturo Magidin Nov 26 '11 at 5:11
add comment

Suppose, your numbers are $a_1,a_2,\ldots,a_{12}$. Divide each number by 5 and collect their remainders as $r_1, r_2 , r_3,\ldots, r_{12}$. As each $r_i$ satisfies $0\leq r_i\leq 4$ for each $i$, $1\leq i\leq 12$, there always exists at least two $r_i$'s, say $r_j$ and $r_k$, having same remainders. Take corresponding numbers $a_j$ and $a_k$. Since, $r_j=r_k$, it implies $a_j \bmod 5= a_k \bmod 5$, which further implies $(a_j-a_k) \bmod5=0$; i.e. there difference is divisible by 5. proved :)

It can be proved even for 6 numbers. Moreover, in the case of 12 numbers, we can always find two numbers such that their difference is divisible by 11.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.