DaniyalAlwani wrote:
ScottTargetTestPrepI really struggle in these problems. There are two methods to solve these I believe.
1/ As this question requires, how many times 3 appears in 9!?
This can be answered in following way:
9/ 3 + 9/3^2
3+1 = 4 times
2/ Method which you described:
9/3 = 3
3/3 = 1
3+ 1 = 4 times
However, what is the difference between both them methods? And can I use method 1 to solve this?
Response: As a matter of fact, the two methods are equivalent. I’ll only show that dividing n by k^2 and dividing n by k successively two times will produce the same quotient; however, the idea applies to any power of k.
Let n divided by k produce a quotient of s and a remainder of r. We have:
n = ks + r
Now, divide s by k. Let the quotient be q and the remainder be p. Then:
s = kq + p
Substitute s = kq + p in the first equality:
n = k(kq + p) + r = k^2 * q + kp + r
The above suggests that the quotient when n is divided by k^2 is q; however, we have to show that kp + r is less than k^2 before we can actually conclude that. Recall that the remainder is always strictly less than the divisor. So, we have r ≤ k - 1 from the first division and p ≤ k - 1 from the second division. Multiplying the second inequality by k, we obtain:
kp ≤ k^2 - k
Adding the above inequality and the inequality r ≤ k - 1 together, we obtain:
kp + r ≤ k^2 - 1
Notice that n = k^2 * q + kp + r and kp + r is less than k^2. Then, the quotient from the division of n by k^2 is q, which is the same quotient we obtain by successively dividing n by k two times. This shows that to determine the number of factors of k in n!, you can either divide n by k, k^2, k^3 etc. until you get a zero quotient or you can divide n by k and keep dividing the quotient by k, until you get a zero quotient. Both will give you the same answer.
_________________
5-star rated online GMAT quant
self study course
See why Target Test Prep is the top rated GMAT quant course on GMAT Club. Read Our Reviews