ASSIGNMENT

SUBJECT: IOQM Topic: Number Theory

READ THE INSTRUCTIONS CAREFULLY

1. Questions 1 to 10 carry 2 marks each; Questions 11 to 20 carry 3 marks each;
Questions 21 and 30 carry 5 marks each.
2. There are no negative marks.
3. Use of mobile phones, smartphones, ipads, calculators, programmable wrist watches is
STRICTLY PROHIBITED. Only ordinary pens and pencils are allowed inside the examination hall.
4. The correction is done by machines through scanning. On the OMR Sheet, darken bubbles
completely with a black pencil or a black or blue ball pen. Darken the bubbles completely only
after you are sure of your answer; else, erasing may lead to the OMR sheet getting damaged
and the machine may not be able to read the answer.
5. The name, email address, and date of birth entered on the OMR sheet will be your login
credentials for accessing your PRMO score.
6. Incomplete/Incorrectly and carelessly filled information may disqualify your candidature.
7. Each question has a one, two or three digit number as answer.

1. Let x, y, and z all exceed 1 and let w be a positive number such that logx w = 24, logy w = 40, and
logxyz w = 12. Find logz w.
Let x, y and z all exceed 1 and let w be a positive number such that logx w = 24, logy
w = 40 and logxyz w = 12. Find logz w.
Ans. (60)
Sol. The logarithmic notation doesn't tell us much, so we'll first convert everything to the equivalent
exponential forms. x24 = w, y40 = w, and (xyz)12 = w. If we now convert everything to a power of 120,
it will be easy to isolate z and w. x120 = w5, y120 = w3, and (xyz)120 = w10.
With some substitution, we get w5w3z120 = w10 and logz w = 060.
k (k + 1)( 2k + 1)
2. It is known that, for all positive integers k, 12 + 22 + 32 + ... + k2 = . Find the smallest
6
positive integer k such that 12 + 22 + 32 + … + k2 is a multiple of 200.
Ans. (112)
k (k + 1)( 2k + 1)
Sol. is a multiple of 200 if k(k + 1)(2k + 1) is a multiple of 1200 = 24 . 3 . 52. So 16, 3, 25
6
|k(k + 1) (2k + 1)|.
Since 2k + 1 is always odd, and only one of k and k + 1 is even, either k, k + 1  0 (mod 16).
Thus, k  0, 15 (mod 16 ) .

If k  0 (mod 3), then 3|k. If k  1 (mod 3), then 3|2k + 1. If k  2 (mod 3), then 3|k + 1.
Thus, there are no restrictions on k in (mod 3).
It is easy to see that only one of k, k + 1, and 2k + 1 is divisible by 5. So either k, k + 1, 2k + 1  0
(mod 25).
Thus, k  0 , 24, 12 (mod 25).
From the Chinese Remainder Theorem, k  0 , 112, 224, 175, 287, 399 (mod 400). Thus, the smallest
positive integer k is 112.
For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 1
3. There exist r unique nonnegative integers n1 > n2 > … > nr and r unique integers ak (1  k  r) with
n n2 n
each ak either 1 or –1 such that a1 3 1 + a2 3 + ... + ar 3 r = 2008 . Find n1 + n2 + … + nr.
Ans. (21)
Sol. In base 3, we find that 200810 = 22021013 . In other words, 2008 = 2  36 + 2  35 + 2  33 + 1  32 + 1  30 .
In order to rewrite as a sum of perfect powers of 3, we can use the fact that 2  3k = 3k+1 − 3k : 2008
= (37 – 36) + (36 – 35) + (34 – 33) + 32 + 30 = 37 – 35 + 34 – 33 + 32 + 30
The answer is 7 + 5 + 4 + 3 + 2 + 0 = 021.
3n+ 1 − 1
Note: Solution by bounding is also possible, namely using the fact that 1 + 3 + 32 + ... + 3n =
2

 19   20   21   91 
4. Suppose r is a real number for which r +  + r +  + r +  + ... + r +  = 546 .
 100   100   100   100 

Find  100r  . (For real x,  x  is the greatest integer less than or equal to x.)
Ans. (546)
1
Sol. Note that the value of r up to the closest multiple of doesn't matter, so assume 100r is an
100
integer. By Hermite's Identity, this equation is equivalent to
 1   18   92   99  
 100r  −  r +  + ... + r +  + r +  + ... + r +   = 546.
 100  100   100  100  
  

5. How many of the first 1000 positive integers can be expressed in the form 2x  + 4x  + 6x  + 8x 

, where x is a real number, and z  denotes the greatest integer less than or equal to z?
Ans. (600)
1
Sol. Noting that all of the numbers are even, we can reduce this to any real number x between 0 to
2
n n+ 1
, as this will be equivalent to to for any integer n (same reasoning as above). So now we
2 2
only need to test every 10 numbers; and our answer will be 100 times the number of integers we
can reach between 1 and 10.
We can now approach this by directly searching for the integers (this solution) or brute forcing all
of the cases (next solution):
We can match up the greatest integer functions with one of the partitions of the integer. If we let
1 1
x= then we get the solution 10; now consider when x  : 2x  = 0 , 4x   1 , 6x   2 , 8x   3
2 2
. But according to this the maximum we can get is 1 + 2 + 3 = 6, so we only need to try the first 6
numbers.
1
1: Easily possible, for example try plugging in x = .
8
1
2: Also simple, for example using .
6

For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 2

1
3: The partition must either be 1 + 1 + 1 or 1 + 2. If 4x  = 1 , then x  , but then 8x   2 ; not
4
possible; and vice versa to show that the latter partition doesn't work. So we cannot obtain 3.
1
4: We can partition as 1 + 1 + 2, and from the previous case we see that works.
4
1
5: We can partition as 1 + 2 + 2, from which we find that works.
3
3
6: We can partition as 1 + 2 + 3, from which we find that works.
8
Out of these 6 cases, only 3 fails. So between 1 and 10 we can reach only the integers 1, 2, 4, 5, 6,
10; hence our solution is 6. 100 = 600.

6. Positive numbers x, y, and z satisfy xyz = 1081 and (log10 x)(log10 yz) + (log10 y)(log10 z) = 468 . Find

(log10 x) + (log10 y ) + (log10 z)

2 2 2
.

Ans. (75)
Sol. Using the properties of logarithms, log10 xyz = 81 by taking the log base 10 of both sides, and (log10
x)(log10 y) + (log10 x) (log10 z) + (log10 y)(log10 z) = 468 by using the fact that log10 ab = log10 a + log10
b.
Through further simplification, we find that log10 x + log10 y + log10 z = 81. It can be seen that there
is enough information to use the formula (a + b + c) 2 = a2 + b2 + c2 + 2ab + 2ac + 2bc, as we have

both a + b + c and 2ab + 2ac + 2bc, and we want to find a2 + b2 + c2 .

After plugging in the values into the equation, we find that (log 10 x)2 + (log10 y)2 + (log10 z)2 is equal
to 6561 – 936 = 5625.

(log10 x) + (log10 y ) + (log10 z)

2 2 2
However, we want to find , so we take the square root of 5625, or

075.

7. Given that
(1) x and y are both integers between 100 and 999, inclusive;
(2) y is the number formed by reversing the digits of x; and
(3) z = |x – y|
How many distinct values of z are possible?
Ans. (9)
Sol. We express the numbers as x = 100a + 10b + c and y = 100c + 10b + a. From this, we have
z = |100a + 10b + c – 100c – 10b – a|
= |99a – 99c| = 99|a – c|
Because a and c are digits, and a and c are both between 1 and 9 (from condition 1), there are 009
possible values (since all digits except 9 can be expressed this way).

8. For how many pairs of consecutive integers in {1000, 1001, 1002, …, 2000} is no carrying required
when the two integers are added?
Ans. (156)
Sol. For one such pair of consecutive integers, let the smaller integer be 1ABC where A, B and C are
digits from 0 through 9.
We wish to count the ordered triples (A, B, C). By casework, we consider all possible forms of the
larger integer, as shown below.
For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 3
Together, the answer is 53 + 52 + 5 + 1 = 156.

9. Let N be the number of ways to write 2010 in the form 2010 = a3 . 103 + a2 . 102 + a1 . 10 + a0, where
the ai's are integers, and 0  ai  99. An example of such a representation is 1.103 + 3.102 + 67.101 +
40.100. Find N.
Ans. (202)
Sol. If we choose a3 and a1 such that (103)(a3) + (10)(a1)  2010 there is a unique choice of a2 and a0 that
makes the equality hold. So N is just the number of combinations of a3 and a1 we can pick.
If a3 = 0 or a3 = 1 we can let a1 be anything from 0 to 99. If a3 = 2 then a1 = 0 or a1 = 1. Thus N = 100
+ 100 + 2 = 202.

10. For any positive integer x, let S(x) be the sum of the digits of x, and let T(x) be |S(x + 2) – S(x)|. For
example, T(199) = |S(201) – S(199)| = |3 – 19| = 16. How many values of T(x) do not exceed 1999?
Ans. (223)
Sol. For most values of x, T(x) will equal 2. For those that don't, the difference must be bumping the
number up a ten, a hundred, etc. If we take T(a999) as an example, |(a + 1) + 0 + 0 + 1 – (a + 9 + 9
+ 9)| = |2 – 9(3)| And in general, the values of T(x) will then be in the form of |2 – 9n| = 9n - 2.
 1999 − 7 
From 7 to 1999, there are   = 222 solutions; including 2 and there are a total of 223
 9 
solutions.

 2002 
11. Find the least positive integer k for which the equation   = k has no integer solutions for n.
 n 
(The notation  x  means the greatest integer less than or equal to x.)
Ans. (49)
2002 2002  2002   2002   2002   2002 
Sol. Note that if −  1 , then either  =  , or  =  + 1 . Either way, we
n n+ 1  n   n+ 1   n   n+ 1 
won't skip any natural numbers.
2002 2002
The greatest n such that −  1 is n = 44. (The inequality simplifies to n(n + 1) < 202 ,
n n+ 1
which is easy to solve by trial, as the solution is obviously 2002 .)
 2002   2002   2002   2002   2002   2002 
We can now compute:   = 44   = 45   = 46   = 47   = 48   = 50 .
 45   44   43   42   41   40 
 2002 
From the observation above (and the fact that   = 1 ) we know that all integers between 1
 2002 
 2002 
and 44 will be achieved for some values of n. Similarly, for n < 40 we obviously have    50
 n 
.
For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 4
 2002 
Hence the least positive integer k for which the equation   = k has no integer solutions for
 n 
n is 049.
 2002 
Note: After getting that   = 44 , for ease of computation above, we can use the fact that (40
 45 
+ k)(49 – k) varies solely based on k2 and checking these gives us that the pattern fails at k = 0
giving us 049 as the answer.

12. Someone observed that 6! = 8. 9. 10. Find the largest positive integer n for which n! can be
expressed as the product of n – 3 consecutive positive integers.
Ans. (23)

Sol. The product of n – 3 consecutive integers can be written as

(n − 3 + a ) ! for some integer a. Thus,
a!

n! =
(n − 3 + a ) ! , from which it becomes evident that a  3. Since (n – 3 + a)! > n!, we can rewrite
a!
n! (n + 1)(n + 2) ... (n − 3 + a )
this as = n!  (n + 1)(n + 2 ) ... (n − 3 + a ) = a ! . For a = 4, we get n + 1 = 4!
a!
so n = 23. For greater values of a, we need to find the product of a – 3 consecutive integers that
a −3
equals a!. n can be approximated as a ! , which decreases as a increases. Thus, n = 23 is the
greatest possible value to satisfy the given conditions.

13. If a < b < c < d < e are consecutive positive integers such that b + c + d is a perfect square and a
+ b + c + d + e is a perfect cube, what is the smallest possible value of c?
Ans. (675)
Sol. Since the middle term of an arithmetic progression with an odd number of terms is the average
of the series, we know b + c + d = 3c and a + b + c + d + e = 5c. Thus, c must be in the form of 3
. x2 based upon the first part and in the form of 52 . y3 based upon the second part, with x and y
denoting an integers. c is minimized if it’s prime factorization contains only 3, 5, and since there
is a cubed term in 52 . y3, 33, must be a factor of c. 33 52 = 675, which works as the solution.

14. Find the least positive integer such that when its leftmost digit is deleted, the resulting integer is
1
of the original integer.
29
Ans. (725)
Sol. Suppose the original number is N = anan− 1 ...aa a0 , where the ai are digits and the first digit, an, is

nonzero. Then the number we create is N0 = an− 1 ...a 1a0 so N = 29N0. But N is N0 with the digit an
added to the left, so N = N0 + an . 10n. Thus, N0 + an . 10n = 29N0 an . 10n = 28N0. The right-hand side
of this equation is divisible by seven, so the left-hand side must also be divisible by seven. The
number 10n is never divisible by 7, so an must be divisible by 7. But an is a nonzero digit, so the only
possibility is an = 7. This gives 7 . 10n = 28N0 or 10n = 4N0. Now, we want to minimize both n and N0,
so we take N0 = 25 and n = 2. Then N = 7 . 102 + 25 = 725 and indeed, 725 = 29 . 25.

For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 5

15. Find the sum of all positive integers n for which n2 – 19n + 99 is a perfect square.
Ans. (35)
Sol. Suppose there is some k such that x2 – 19x + 99 = k2. Completing the square, we have that (x –
19/2)2 + 99 – (99/2)2 = k2, that is, (x – 19/2)2 + 35/4 = k2. Multiplying both sides by 4 and rearranging,
we see that (2k)2 – (2x – 19)2 = 35. Thus, (2k – 2x + 19) (2k + 2x - 19) = 35. We then proceed as we
did in the previous solution.

16. What is the largest positive integer n for which n3 + 100 is divisible by n + 10?
Ans. (890)
Sol. If n + 10 |n3 + 100|, gcd(n3 + 100, n + 10) = n + 10. Using the Euclidean algorithm, we have gcd(n 3 +
100, n + 10) = gcd(–10n2 + 100, n + 10) = gcd(100n + 100, n + 10) = gcd(–900, n + 10) , so n + 10 must
divide 900. The greatest integer n for which n + 10 divides 900 is 890; we can double-check
manually and we find that indeed 900 | 8903 + 100.

17. Let n be the smallest positive integer that is a multiple of 75 and has exactly 75 positive integral
n
divisors, including 1 and itself. Find .
75
Ans. (432)
Sol. The prime factorization of 75 = 3152 = (2 + 1)(4 + 1)(4 + 1). For n to have exactly 75 integral divisors,
e −1
−1
we need to have n = p1 1 pe2
2 ... such that e1 e2 … = 75. Since 75|n, two of the prime factors must
be 3 and 5. To minimize n, we can introduce a third prime factor, 2. Also to minimize n, we want
5, the greatest of all the factors, to be raised to the least power. Therefore, n = 2 4 34 52 and
n 243452
= = 16  27 = 432 .
75 3  52

18. Let S be the set of all rational numbers r, 0 < r < 1, that have a repeating decimal expansion in the
form 0.abcabcabc … = 0.abc , where the digits a, b, and c are not necessarily distinct. To write the
elements of S as fractions in lowest terms, how many different numerators are required?
Ans. (660)
Sol. We consider the method in which repeating decimals are normally converted to fractions with an
example:
x = 0.176
176
 1000x = 176.176  999x = 1000x − x = 176  x =
999

Thus, let x = 0.abc

abc
 1000x = abc.abc  999x = 1000x − x = abc  x =
999
If abc is not divisible by 3 or 37, then this is in lowest terms. Let us consider the other multiples:
333 multiples of 3, 27 of 37, and 9 of both 3 and 37, so 999 – 333 – 27 + 9 = 648, which is the
amount that are neither. The 12 numbers that are multiples of 81 reduce to multiples of 3. We
have to count these since it will reduce to a multiple of 3 which we have removed from 999, but,
this cannot be removed since the numerator cannot cancel the 3.There aren't any numbers which
are multiples of 372, so we can't get numerators which are multiples of 37. Therefore 648 + 12 =
660.
For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 6
19. Find the number of positive integers with three not necessarily distinct digits, abc, with a  0 and
c  0 such that both abc and cba are multiples of 4.
Ans. (40)
Sol. A positive integer is divisible by 4 if and only if its last two digits are divisible by 4. For any value
of b, there are two possible values for a and c, since we find that if b is even, a and c must be
either 4 or 8, and if b is odd, a and c must be either 2 or 6. There are thus 2 . 2 = 4 ways to choose
a and c for each b, and 10 ways to choose b since b can be any digit. The final answer is then 4 .
10 = 040.

 200 
20. What is the largest 2-digit prime factor of the integer n 
 100  ?
 
Ans. (61)
 200  200!
Sol. Expanding the binomial coefficient, we get   = . Let the required prime be p; then 10
 100  100! 100!
 p < 100. If p > 50, then the factor of p appears twice in the denominator. Thus, we need p to
appear as a factor at least three times in the numerator, so 3p < 200. The largest such prime is
061, which is our answer.
Clarification of Solution 1
 200  200!
We know that   = . Since p < 100, there is at least 1 factor of p in each of the 100! in
 100  100! 100!
the denominator. Thus there must be at least 3 factors of p in the numerator 200! for p to be a
200!
factor of n = . (Note that here we assume the minimum because as p goes larger in value,
100! 100!
the number of factors of p in a number decreases,)
 200  200
So basically, p is the largest prime number such that    3 Since p  = 66.66... , the largest
 p  3
prime value for p is p = 61.

21. The increasing sequence 1, 3, 4, 9, 10, 12, 13 … consists of all those positive integers which are
powers of 3 or sums of distinct powers of 3. Find the 100 th term of this sequence.
Ans. (981)
Sol. Rewrite all of the terms in base 3. Since the numbers are sums of distinct powers of 3, in base 3
each number is a sequence of 1s and 0s (if there is a 2, then it is no longer the sum of distinct
powers of 3). Therefore, we can recast this into base 2 (binary) in order to determine the 100th
number. 100 is equal to 64 + 32 + 4, so in binary form we get 1100100. However, we must change
it back to base 10 for the answer, which is 36 + 35 + 32 = 729 + 243 + 9 = 981.

22. Let [r, s] denote the least common multiple of positive integers r and s. Find the number of ordered
triples (a, b, c) of positive integers for which [a, b] = 1000, [b, c] = 2000, and [c, a] = 200.
Ans. (70)
Sol. It's clear that we must have a = 2j5k, b = 2m5n and c = 2p5p for some nonnegative integers j, k, m,
n, p, q. Dealing first with the powers of 2: from the given conditions, max (j, m) = 3, max(m, p) =
max(p, j) = 4. Thus we must have p = 4 and at least one of m, j equal to 3. This gives 7 possible
triples (j, m, p): (0, 3, 4), (1, 3, 4), (2, 3, 4), (3, 3, 4), (3, 2, 4), (3, 1, 4) and (3, 0, 4).

For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 7

Now, for the powers of 5: we have max(k, n) = max(n, q) = max(q, k) = 3. Thus, at least two of k,
n, q must be equal to 3, and the other can take any value between 0 and 3. This gives us a total
of 10 possible triples: (3, 3, 3) and three possibilities of each of the forms (3, 3, n), (3, n, 3) and (n,
3, 3).
Since the exponents of 2 and 5 must satisfy these conditions independently, we have a total of 7
. 10 = 70 possible valid triples.

23. What is the smallest positive integer with six positive odd integer divisors and twelve positive even
integer divisors?
Ans. 180
Sol. We use the fact that the number of divisors of a number n = pe1 e2 ek
1 p2 ...pk is (e1 + 1) (e2 + 1) … (ek +
1). If a number has 18 = 2 . 3 . 3 factors, then it can have at most 3 distinct primes in its
factorization.
Dividing the greatest power of 2 from n, we have an odd integer with six positive divisors, which
indicates that it either is (6 = 2 . 3) a prime raised to the 5th power, or two primes, one of which is
squared. The smallest example of the former is 35 = 243, while the smallest example of the latter
is 32. 5 = 45.
18
Suppose we now divide all of the odd factors from n; then we require a power of 2 with =3
6
factors, namely 23–1 = 4. Thus, our answer is 22 . 32 . 5 = 180.

24. Let n = 231319. How many positive integer divisors of n2 are less than n but do not divide n?
Ans. (589)
Sol. We know that n2 = 262338 must have (62 + 1) × (38 + 1) factors by its prime factorization. If we
group all of these factors (excluding n) into pairs that multiply to n2, then one factor per pair is
63  39 − 1
less than n, and so there are = 1228 factors of n2 that are less than n. There are 32 ×
2
20 – 1 = 639 factors of n, which clearly are less than n, but are still factors of n. Therefore, using
complementary counting, there are 1228 – 639 = 589 factors of n2 that do not divide n.

25. Let N be the number of consecutive 0's at the right end of the decimal representation of the
product 1!2!3!4! … 99!100!. Find the remainder when N is divided by 1000.
Ans. (124)
Sol. A number in decimal notation ends in a zero for each power of ten which divides it. Thus, we need
to count both the number of 5s and the number of 2s dividing into our given expression. Since
there are clearly more 2s than 5s, it is sufficient to count the number of 5s.
One way to do this is as follows: 96 of the numbers 1!, 2!, 3!, 100! have a factor of 5. 91 have a
factor of 10. 86 have a factor of 15. And so on. This gives us an initial count of 96 + 91 + 86 + … +
1. Summing this arithmetic series of 20 terms, we get 970. However, we have neglected some
powers of 5 - every n! term for n  25 has an additional power of 5 dividing it, for 76 extra; every
n! for n  50 has one more in addition to that, for a total of 51 extra; and similarly there are 26
extra from those larger than 75 and 1 extra from 100. Thus, our final total is 970 + 76 + 51 + 26 + 1
= 1124, and the answer is 124.

For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 8

26. Let K be the product of all factors (b – a) (not necessarily distinct) where a and b are integers
satisfying 1  a < b  20. Find the greatest positive integer n such that 2n divides K.
Ans. (150)
Sol. In general, there are 20 – n pairs of integers (a, b) that differ by n because we can let b be any
integer from n + 1 to 20 and set a equal to b – n. Thus, the product is (119)(218)…(191) (or alternatively,
19! . 18! … 1!.)
When we count the number of factors of 2, we have 4 groups, factors that are divisible by 2 at
least once, twice, three times and four times.
Numbers that are divisible by 2 at least once: 2, 4, …, 18
Exponent corresponding to each one of them 18, 16, … 2

Sum = 2 + 4 + ... + 18 =
( 20)(9) = 90
2
Numbers that are divisible by 2 at least twice: 4, 8, …, 16
Exponent corresponding to each one of them 16, 12, … 4

Sum = 4 + 8 + ... + 16 =
( 20 )( 4 ) = 40
2
Numbers that are divisible by 2 at least three times: 8, 16
Exponent corresponding to each one of them 12, 4
Sum = 12 + 4 = 16
Number that are divisible by 2 at least four times: 16
Exponent corresponding to each one of them 4
Sum = 4
Summing these give an answer of 150.

27. What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a
positive composite integer?
Ans. (215)
Sol. The requested number mod42 must be a composite number. Also, every number that is a multiple
of 42 greater than that prime number must also be prime, except for the requested number itself.
So, we make a table, listing all the primes up to 42 and the numbers that are multiples of 42
greater than them, until they reach a composite number.

Since 215 is the greatest number in the list, it is the answer. Note that considering mod 5 would
have shortened the search, since gcd(5, 42) = 1, and so within 5 numbers at least one must be
divisible by 5.

For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 9

28. The product N of three positive integers is 6 times their sum, and one of the integers is the sum
of the other two. Find the sum of all possible values of N.
Ans. (336)
Sol. Let the three integers be a, b, c. N = abc = 6(a + b + c) and c = a + b. Then N = ab (a + b) = 6(a +
b + a + b) = 12(a + b). Since a and b are positive, ab = 12 so {a, b} is one of {1, 12}, {2, 6}, {3, 4} so a
+ b is one of 13, 8, 7 so the sum of all possible values of N is 12 . (13 + 8 + 7) = 12(28) = 336.

29. Let S be the sum of all numbers of the form a/b, where a and b are relatively prime positive
divisors of 1000. What is the greatest integer that does not exceed S/10?
Ans. (248)
a
Sol. Since all divisors of 1000 = 2353 can be written in the form of 2m5n, it follows that can also be
b
expressed in the form of 2x5y, where –3  x, y  3. Thus every number in the form of a/b will be
expressed one time in the product (2−3
+ 2−2 + 2−1 + 20 + 21 + 22 + 23 )
(5−3
+ 5−2 + 5−1 + 50 + 51 + 52 + 53 . )
Using the formula for a geometric series, this reduces to

S=
(
2−3 27 − 1)  5 (5 − 1) = 127  78124 = 2480 + 437 , and  S  = 248 .
−3 7

 
2−1 5−1 4000 1000  10 

30. Let N be the number of positive integers that are less than or equal to 2003 and whose base-2
representation has more 1's than 0's. Find the remainder when N is divided by 1000.
Ans. (155)
n
Sol. In base-2 representation, all positive numbers have a leftmost digit of 1. Thus there are  
k 
numbers that have n + 1 digits in base 2 notation, with k + 1 of the digits being 1's.
n+ 1 n−1 n
In order for there to be more 1's than 0's, we must have k + 1  k   k  . Therefore,
2 2 2
the number of such numbers corresponds to the sum of all numbers on or to the right of the
vertical line of symmetry in Pascal's Triangle, from rows 0 to 10 (as 2003 < 2 11 – 1). Since the sum
of the elements of the rth row is 2r, it follows that the sum of all elements in rows 0 through 10 is
 2i 
20 + 21 + … + 210 = 211 – 1 = 2047. The center elements are in the form   , so the sum of these
i 
5
 2i 
elements is   i
i =0
 = 1 + 2 + 6 + 20 + 70 + 252 = 351 .

2047 + 351
The sum of the elements on or to the right of the line of symmetry is thus = 1199 .
2
However, we also counted the 44 numbers from 2004 to 211 – 1 = 2047. Indeed, all of these numbers
have at least 61's in their base-2 representation, as all of them are greater than 1984 = 111110000002,
which has 51's. Therefore, our answer is 1199 – 44 = 1155, and the remainder is 155.

For more free study material visit - https://unacademy.com/content/indian-olympiad-qualifier-in-mathematics/ 10