0
$\begingroup$

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$?

  • 5
    By the way, you should work on your question titles. There are _very many_ $p$roblems 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.2011-11-26

2 Answers 2

3

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.

  • 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$.2011-11-26
2

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.