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$?
Tell me more
×
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.
|
|
|||||||||||||
|
|
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. |
|||||||||
|
|
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. |
||||
|
|
