ManHattan Problem

[kakz]

For positive integers k and n, the "k-power remainder of n" is defined as r in the following equation:
n = k^w + r, where w is the largest integer such that r is not negative. For instance, the 3-power remainder of 13 is 4, since 13 = 3^2 + 4. In terms of k and w, what is the largest possible value of r that satisfies the given conditions?
(A)(k - 1)k^w - 1
(B)k^w - 1
(C)(k + 1)k^w - 1
(D)k^(w+1) - 1
(E)(k + 1)k^(w+1) - 1

Have also included screenshot. OA is A

[user123321]

given n = k^w + r
based on given conditions, your r will be maximum only when n is just 1 less than k^(w+1).
then only you can write that n as k^w + some r which is maximum

so, k^(w+1) - 1 = k^w + r
solving you get r = k^(w+1)-k^w -1
=> r = (k-1)k^w - 1

user132321

[GMATGuruNY]

For positive integers k and n, the "k-power remainder of n" is defined as r in the following equation:
n = k^w + r, where w is the largest integer such that r is not negative. For instance, the 3-power remainder of 13 is 4, since 13 = 3^2 + 4. In terms of k and w, what is the largest possible value of r that satisfies the given conditions?
(A)(k - 1)k^w - 1
(B)k^w - 1
(C)(k + 1)k^w - 1
(D)k^(w+1) - 1
(E)(k + 1)k^(w+1) - 1

Have also included screenshot. OA is A

Let k=3 and w=2.
Then k^w = 3² = 9.

n = 3² + r.
To maximize r, we need to maximize n.
If n≥27, then the value of w will have to increase, since w must be as great as possible:
27 = 3^w + r
27 = 3³ + 0, implying that w=3 and r=0.

Thus, if k=3 and w=2, the maximum possible value of n is 26:
26 = 3² + r
r = 17. This is our target.

Now we plug k=3 and w=2 into the answers to see which yields our target of 17.

Only answer choice A works:
(k - 1)k^w - 1 = (3-1)(3²) - 1 = 17.

The correct answer is A.

[GmatMathPro]

For something like this it can be instructive to look at a wide range of concrete examples to get a better handle on how things are actually working. The following image is a screenshot of an Excel spreadsheet with k=2, values of n from 1 to 33, and the resulting values of w and r for n=k^w+r.



As you can see, for any given value of w, r increases as n increases. Then, once n becomes big enough to require the next value of w (in this case, when n becomes the next power of 2), r goes back to zero and begins increasing again. Thus, for any given value of w, r is maximized when n is one less than the next power of k, or k^(w+1). Mathematically, when n=k^(w+1)-1, r is maximized. So, n=k^w+r (by definition) and n=k^(w+1)-1 (when r is maximized). Equating the two expressions for n:

k^(w+1)-1=k^w+r
r=k^(w+1)-k^w-1
r=k^w(k-1)-1 (factoring k^w out of the first two terms)
r=(k-1)k^w-1

Now, you may notice that in this case, when k=2, the maximum r value can also be expressed as r=k^w-1. This, no doubt, is why it was included as an answer choice. So, if you were doing this solely by plugging numbers in, 2 may be a misleading choice for the value of k. If we look at a similar chart where k=3, it becomes clear that k^w-1 is generally not the correct expression for the maximum value of r:



Of course, you won't be able to make lengthy Excel spreadsheets when you take the actual test. The point is just to see how things work. You can see that just as with regular remainders, k-power remainders repeat in some sort of cycle. With regular remainders, if n is divided by k, the remainders cycle from 0 to k-1 as n is increased. With k-power remainders, the remainders cycle from 0 to (k-1)k^w-1. So, if you encounter some kind of atypically defined remainder on the test, you can keep in mind that the remainders will probably follow some sort of pattern like this.