Difficult Probability Solved QuestionAptitude Discussion

 Q. If the integers $m$ and $n$ are chosen at random from integers 1 to 100 with replacement, then the probability that a number of the form  $7^{m}+7^{n}$ is divisible by 5 equals:
 ✔ A. $\dfrac{1}{4}$ ✖ B. $\dfrac{1}{7}$ ✖ C. $\dfrac{1}{8}$ ✖ D. $\dfrac{1}{49}$

Solution:
Option(A) is correct

Table below can be scrolled horizontally

Form of the exponent
$m$ $4x +1$ $4x+3$ $4x+2$ $4x$
$n$ $4y+3$ $4y+1$ $4y$ $4y+2$
last digit of
$7^m+7^n$
$0$ $0$ $0$ $0$
Number of
selections
$25 \times 25$ $25 \times 25$ $25 \times 25$ $25 \times 25$

If  a  number  ends  in  a  0  then  the  number  must  be divisible by 5.

Hence required probability is,

$=\dfrac{625 \times 4}{100^2}$

$=\dfrac{1}{4}$

Edit: Thank you, Barry, for the very good explanation in the comments.

Edit 2: Thank you Vaibhav, corrected the typo now it's $25 \times 25$ and not $26 \times 25$.

Edit 3: For yet another approach of solving this question, check comment by Murugan.

(7) Comment(s)

Murugan
()

This sum is very simple. Power cycles of 7 are 7, 9, 3, 1

So totally 4 possibilities.

Total possibilities are $^4P_1 \times ^4P_1=16$

For selecting a number from 1 to 100 which are divisible by 5,

$m=9$, $n=1$ or $m=1$, $n=9$ or $m=7$, $n=3$ or $m=3$, $n=7$

i.e. 4 chances.

Therefore, probability is $\frac{4}{16}=\frac{1}{4}$

Vaibhav
()

Its should be $25*25$ not $26*25$

Deepak
()

Thank you Vaibhav, corrected typo in the solution.

Apurv
()

I did this: Let $m>n$ (Clearly m and n can't be equal because $5$ can't divide $2*7^{m}$).

Now $7^{m}+7^{n}=7^{n}(7^{m-n}+1)$. If $5$ has to divide this, it implies that 5 has to divide $(7^{m-n}+1)$ (because it cannot divide a power of $7$).

Since powers of $7$ have a cyclic order of $7,9,3,1$; $7^{m-n}$ has to therefore end in a $9$ and therefore $m-n$ can be $2,6,10,...,98$.

Hence the only set of values of $n$ are $(1,2,3,...,97),(1,2,3,...,93),(1,2,3,...,89),...,(1)$. Also fixing $n$ would fix $m$.

Therefore the number of favorable cases is $97+93+89+...+2=1224$. Which means that the required probability should be $\frac{1224}{^{100}C_2$ which turns out to be $\frac{68}{275}$, which is not matching with any of the options..

Where did I go wrong ??

Barry
()

You made three mistakes, or possibly four. One or two of them reside in your calculation $97+93+89+\cdots+2=1224$. It should be $97+93+89+\cdots+1=1225$. It's a little odd that the correction seemingly subtracts $1$ on one side and adds it to the other, so let me spell out the correct calculation:

\begin{align} 97+93+89+\cdots+1&=(4\cdot24+1)+(4\cdot23+1)+(4\cdot22+1)+\cdots+(4\cdot1+1)+1\\ &=4(24+23+22+\cdots+1)+25\\ &=4\left({24\cdot25\over2}\right)+25=1225 \end{align}

However, these aren't the correct numbers to be adding anyway. The correct calculation would have been

$$98+94+90+\cdots+2=1250$$

This is because the correct sets of values for $n$, corresponding to $m-n=2,6,\ldots,98$ are $(1,2,\ldots,98),(1,2,\ldots,94),\ldots,(1,2)$, since presumably you are allowing $m$ to take the value $100$ as well as $99$.

The final, most substantial error resides in what you did with this number after you got it, which was to divide it by ${100\choose2}=4950$. This computes the probability that of two different numbers the given form will be divisible by $5$. But the problem allows for the two numbers to be the same.

At this point you might be tempted to add the $100$ ways two numbers can be the same to the $4950$ ways they can be different and get $1225/5050=49/202$, but this would also be the wrong answer. The correct thing is to double the number $1225$ to get the total number of ways to choose $m$ and $n$ so that $7^m+7^n$ is divisible by $5$ regardless of which one is larger, and then divide by the total number of ways to choose two numbers between $1$ and $100$, which is simply $100^2=10000$. So the correct answer is $2500/10000=1/4$, as others have pointed out.

All that said, it's worthwhile understanding what you did wrong, and it's also worthwhile understanding (from the answers other people have given) how the problem could have been solved by taking a simpler approach.

Derek
()

$7\equiv 2 \bmod 5, 2^1 \equiv 2,2^2 \equiv 4, 2^3\equiv 3 ,2^4\equiv 1$. morever if $m\equiv a\bmod4$ then $2^m\equiv2^a$. (because $2^4\equiv 1 \bmod5)$

so if you want the sum to be divisible by 5 there are 4 ways for this to happen:

$m\equiv1$ and $n\equiv4 \bmod 4$

$m\equiv4$ and $n\equiv1 \bmod 4$

$m\equiv2$ and $n\equiv3 \bmod 4$

$m\equiv3$ and $n\equiv2 \bmod 4$

So if $m$ is any congruence class then the probability $n$ is the corresponding correct class is $\frac{1}{4}$

The numbers are probably intended to be independently chosen, with the possibility that $m=n$. The remainder of $7^m$ on division by $5$ is equally likely to be one of $2,4,3,1$, since $\varphi(5)$ divides $100$. So is the remainder of $7^n$.
Whatever the remainder of $7^m$ happens to be, there is a unique value of $7^n$ modulo $5$ that gives us sum $0$ modulo $5$. That value has probability $\frac{1}{4}$.
Remark: If we choose a pair of numbers (no replacement), then the answer changes. We can assume that the numbers are chosen in order, $m$ first. Whatever value of $m$ is chosen, there are $25$ choices for $n$ that will give sum $0$ modulo $7$, so the probability is $\frac{25}{99}$.