TIFR CSE 2011 | Part A | Question: 10

Question

Let $m$, $n$ denote two integers from the set $\{1, 2,\dots,10\}$. The number of ordered pairs $\left ( m, n \right )$ such that $2^{m}+2^{n}$ is divisible by $5$ is.

• A. $10$
• B. $14$
• C. $24$
• D. $8$
• E. None of the above

Comments

Being a CS student, we should be aware of the powers of 2, in the sense what is 2¹ and 2² etc...

{2¹,2³,2⁷} , we can combine 2¹ with 2³ and 2¹ with 2⁷    , here 4 order pairs are possible

{2²,2⁴,2⁸}, we can combine 2² with 2⁴ and 2² with 2⁸    , here 4 order pairs are possible

{2³,2⁵,2⁹}, we can combine 2³ with 2⁵ and 2³ with 2⁹    , here 4 order pairs are possible

{2⁴,2⁶,2¹⁰} , we can combine 2⁴ with 2⁶ and 2⁴ with 2¹⁰ , here 4 order pairs are possible

 {2⁵,2⁷}, we can combine 2⁵ with 2⁷ , here 2 order pairs are possible

 {2⁶,2⁸}, we can combine 2⁶ with 2⁸ , here 2 order pairs are possible

 {2⁷  ,2⁹}, we can combine 2⁷with 2⁹ , here 2 order pairs are possible

 {2⁸,2⁷}, we can combine 2⁸ with 2¹⁰ , here 2 order pairs are possible

Hence total order pairs, 4*4 + 2*4 = 24

Answer 1

Ending in $2: \left \{ 2^1, 2^5, 2^9 \right \}$

Ending in $4: \left \{ 2^2, 2^6, 2^{10} \right \}$

Ending in $6: \left \{ 2^4, 2^8 \right \}$

Ending in $8: \left \{ 2^3, 2^7 \right \}$

To make $2^m+2^n$ divisible by $5$, it must end in either a $0$ or a $5$.

Since, $m,n > 1$, all numbers $2^m, 2^n$ are even. Since sum of even numbers is even, $2^m+2^n$ cannot end in a $5$.

Thus, $2^m+2^n$ must end in a $0$.

Possible ways to achieve a number ending with $0$ are:

$$\begin{array}{c} \hline \begin{array}{lllll} 2^m + 2^n: &m \in \left \{ 1, 5, 9 \right \}, &n \in \left \{ 3, 7 \right \} &\implies 3 \times 2 &= 6 \text{ pairs}\\[1em] 2^m + 2^n: &m \in \left \{ 3, 7 \right \}, &n \in \left \{ 1, 5, 9 \right \} &\implies 2 \times 3 &= 6 \text{ pairs}\\[2em] 2^m + 2^n: &m \in \left \{ 2,6,10 \right \}, &n \in \left \{ 4,8 \right \} &\implies 3 \times 2 &= 6 \text{ pairs}\\[1em] 2^m + 2^n: &m \in \left \{ 4,8 \right \}, &n \in \left \{ 2,6,10 \right \} &\implies 2 \times 3 &= 6 \text{ pairs}\\ \end{array}\\[2em] \hline \text{Total} = 6 + 6 + 6 + 6 = 24 \text{ ordered pairs} \end{array}$$

Thus, option C is correct.

Comments

wish i had the power to mark it as the best answer . :)

---

Is this correct approach?

$2^m+2^n=2^m(1+2^{n-m})$, $(1+2^{n-m})$ should be divisible by 5 (bcoz other factor i.e. $2^m$ can never be divisible by 5).
$(1+2^{n-m})$ will be divisible by 5 only if $2^{n-m}$ ends with 4 or 9. But $2^{n-m}$ can not be end with 9, so it has to end with 4.
$2^p$ will end with 4 if p = 2,6,10 and so on.
that says difference between $n$ and $m$ is either 2, 6 or 10. (it can not be greater than 10 for given problem.)
$n-m=2$ for this possible solutions are 8.
$n-m=6$ for this possible solutions are 4.
$n-m=10$ for this possible solution is none.

total 8+4+0 = 12.

ordered pairs are 12 x 2 = $24$.

Answer 2

It would be divisible by 5 only if (2 ^ m + 2 ^ n) will have a 0 or 5 in the last digit . Now 5 cannot occur as the last digit in this case since 2 even no addition can never result odd number .

Now the possible powers of 2 within 10 are = {2,4,8,16,32,64,128,256,512,1024}

So the possible combinations which will bring a 0 as the last digit is

{ ( 2,8) ,(4,16 ), (8,32) ,(16,64) , (128,2) , (512 ,8) , (1024,16 ) , (1024 , 256 ) , (512,128) , (256 ,4 ) ,(128 , 32) ,(256,64) }

There are 12 pairs . But since these are ordered pairs (a,b ) will be treated differently than  (b,a ) .

Hence there are 12 * 2 = 24 such pairs.

Ans is option  C.

Answer 3

2^(m+n)%5=0

then 2^m ≡ 2^n (mod 5) (or 2^n ≡ 2^m (mod 5))

2^|m-n| ≡ 1 (mod 5)

(2^|(m-n)|+1) % 5 =0

find such m and n pairs

highest difference between m and n is 9 (set is {1,2,...,10})

all nos less than 1024 which is a power of 2 : 2,4,8,16,32,64,128,256,512

Out of them only 4(2^2) and 64(2^6) are suitable candidates

|m-n| =2  (So the highest number can have max value 10(10-8=2){(10,8),(8,10)} and min value 3 (3-1=2)(3,1),(1,3)} 

So there will be 2*(10-3+1)= 16 such pairs of (m,n)

|m-n| = 6 (So the highest number can have max value 10(10-4=6){(10,4),(4,10)} and min value 7 (7-1=6)(7,1),(1,7)}

So there will be 2*(10-7+1)= 8 such pairs of (m,n)

answer is 24 pairs