9th Lord of the Math

Solution Booklet

Saint Stephen’s High School

December 3, 2016
9th Lord of the Math
Solution Booklet

Saint Stephen’s High School

December 3, 2016
 Contributors
Balete Immanuel Josiah
Balete Nathanael Joshua
Chuatak John Thomas
Co Randall Lewis
Sison Richie Rainier
Sy Julius Vincent
Tan Hans Markson
Tiu Benedict Ryan
Yu Marc Adrian

DISCLAIMER: Not all of the problems here are original. Some are lifted or edited from previous competi-

tions or textbooks. All information provided here is for educational purposes only.
Team Finals

TF1 Problem The Russian Cyrillic alphabet has 33 letters, 21 of which are
consonants and 10 are vowels. The remaining two letters do not fit in
either category, and are called “signs”. The two signs cannot appear at
the beginning of a word and can only follow a consonant. How many
three-letter Russian “words” (strings of letters) with at least one vowel
satisfy the above condition?
Answer 21 370
Solution Denote by C a consonant, V a vowel, and S a sign. Then
only strings with length three that are of the following types satisfy
the conditions: V V V , V VC and permutations, VCC and permu-
tations, VCS, and CSV . There are 103 = 1000 strings of the form
V V V , 21 × 102 × 3 = 6300 strings of the form V VC (including per-
mutations), 212 × 10 × 3 = 13 230 strings of the form VCC (including
permutations), and 21 × 10 × 2 × 2 = 840 strings of the form VCS or
CSV , giving a total of 21 370 possible strings.

TF2 Problem Taxicab Geometry is one kind of non-Euclidean geometry

where all points are in the x y-plane and the distance function is de-
fined as the sum of the positive differences of their corresponding

1
 x-, and y-coordinates. For example, the distance between (1, 2) and
(.5, −6) is 8.5. Find the area of the circle in a taxicab geometry cen-
tered at the origin with radius 50 units. A circle is defined as the set
of points that are equidistant from its center.
Answer 5000 square units
Solution It can be easily verified that this circle has the shape of a
square, with vertices (±50, 0) and (0, ±50). Therefore, the area is
502 ⋅ 2 = 5000 square units.

TF3 Problem ISBNs are numbers that are used to identify most published
books. It consists of ten digits, where the first nine digits a1 to a9
range from 0 to 9, and the tenth digit a10 from 0 to 10. The first nine
digits give information about the book for identification, and the
tenth digit is a “check digit” to check if the first nine digits might be
wrongly encoded. The check digit a10 is chosen given the first nine
digits such that
10
∑ ia i ≡ 0 (mod 11).
i=1
If the first nine digits are 0 − 825417 − 39, find the check digit.
Answer 8

2
 Solution Expanding the given condition, we have

0(1) + 8(2) + 2(3) + 5(4) + 1(5) + 4(6) + 7(7)

+ 8(3) + 9(9) + 10 (a10 ) = 217 + 10a10 ≡ 0 (mod 11).

Since 217 ≡ 8 (mod 11), then a10 = 8 because 80 + 8 ≡ 0 (mod 11).

TF4 Problem For a positive integer n, let r n be a positive integer from 1

to 9 inclusive such that n ≡ r n (mod 9). Define

A = {n ≤ 1000 ∣ n ≡ 0 (mod r n )} .

Find the cardinality of A.

Answer 527
Solution It is easy to see that for all positive integers x ≤ 1000 such
that r x = 1, 3, or 9, then x ∈ A. There are 112 numbers that are 1
(mod 9), 111 that are 3 (mod 9), and 111 that are 9 (mod 9).

If x ≡ 2 (mod 9), then x = 18a + 2, a a nonnegative integer. Since

x ≤ 1000, a ≤ 55. Thus there are 55 + 1 = 56 numbers here. (Note
that a = 0 is a valid case.)

If x ≡ 4 (mod 9), then x = 36a + 4. The possible values for a here

are {0, 1, . . . , 27}, giving 28 numbers.

3
 If x ≡ 5 (mod 9), then x = 45a + 5, and a ≤ 22. Thus there are 23
numbers for this case.

If x ≡ 6 (mod 9), then x = 18a + 6, and like in the case where x ≡ 2

(mod 9), there are 56 possible numbers.

If x ≡ 7 (mod 9), then x = 63a + 7. The largest value of a such that

x ≤ 1000 is a = 15, so there are 16 numbers for this case.

Finally, if x ≡ 8 (mod 9), then x = 72a + 8, and there are 14 possible

numbers for x.

In total, the cardinality of A is 112 + 111 + 111 + 56 + 28 + 23 + 56 +

16 + 14 = 527.

TF5 Problem The two front tires of a new four-wheeled car will wear
out after 38 400 km, whereas the two rear tires will wear out after
51 600 km. Also, suppose that five identical tires, including one spare
tire, come with the car. If you can easily change the tires whenever
you want, what is the maximum distance that can be driven?
Answer 55 040 km
Solution If we assume that tires wear out at a constant rate, then the
total wear (i.e., if the wear on a tire is 1 then the tire is unusable) on

4
 2 2 1
the four tires for every kilometer is + = . Thus
38 400 51 600 11 008
the maximum number of kilometers obviously happens if the wear
is spread evenly among the five tires. Thus the total distance that can
be traveled is 5 × 11 008 = 55 040 km.

TF6 Problem Three circles with equal radii Γ1 , Γ2 , Γ3 are on a plane such
that each of the three circles passes through the other two circles’
centers. A smaller circle Γ4 is internally tangent to all three circles,
and the three circles are all internally tangent to a larger circle Γ5 . If
the product of the lengths of the radii of the five circles is equal to 162,
find the radius of Γ1 .
Answer 3
Solution
A
O1
O4
O2 O3
B

Let O n be the center of circle Γn . (In this case O3 = O4 .) We as-

sign O2 (0, 0), O3 (r, 0), such that r is the radius of Γ1 . Then, since

5
 √
r 3
O1 O2 O3 is equilateral, O1 ( , r). Since O4 lies on the altitudes of
2 2
△O1 O2 O3 , it is the orthocenter
√ and thus the centroid, as the triangle
r 3
is equilateral. Then O4 ( , r).
2 6
Note that A, O1 , O4 and B are collinear and the line that contains
them is perpendicular to the segment √ O2 O3 . Since AO1 is a radius,
r 3+2
then A is r units above O1 , i.e., A ( , r); similarly BO1 is a
√ 2 2
r 3−2
radius thus B ( , r). A radius of Γ4 is O4 B, which has length
√ √ 2 2 √
3 3−2 3− 3
r− r= r. On the other hand, a radius of Γ5 is O4 A,
6 2 √ 3 √ √
3+2 3 3+ 3
which has length r− r= r.
2 6 3
√
3 − 3
Therefore the product of the lengths of the radii is r 3 ⋅ r⋅
√ 3
3+ 3 2
r = 162, or r 5 = 162. Solving for r, we have r = 3.
3 3
√
TF7 Problem The volume of a right circular cylinder is 6 3 cm3 . What
is its minimum possible total surface area?
√
Answer 18 3 π cm2
Solution Let r and h be the radius and the height of the cylinder,
respectively. Also let T SA be the total surface area, and V the vol-

6
 √
+ 2πrh ≥ 3 2πr 2 (πrh)2 =
3
ume. Then from AM-GM, T SA = 2πr 2
√ √
3 2π (πr 2 h)2 = 3 2πV 2 = 18 3 π cm2 .
3 3 √

TF8 Problem Find cot (cot−1 2 + cot−1 3 + cot−1 5 + cot−1 7).

11
Answer
23
Solution Note that Arg(2 + i) = cot−1 2, Arg(3 + i) = cot−1 3, Arg(5 +
i) = cot−1 5, and Arg(7 + i) = cot−1 7. Then, by de Moivre’s formula,
we have

cot−1 2 + cot−1 3 + cot−1 5 + cot−1 7

= Arg(2 + i) + Arg(3 + i) + Arg(5 + i) + Arg(7 + i)
= Arg ((2 + i)(3 + i)(5 + i)(7 + i))
23 11
= Arg(110 + 230i) = tan−1 = cot−1
11 23

TF9 Problem x34y73 is divisible by 7. Find the sum of all possible values
of y − x.
Answer 3
Solution Since 34 073 ≡ 4 (mod 7), 100 000 ≡ 5 (mod 7), and 100 ≡
2 (mod 7) then x and y satisfy the equivalence (5x+2y) ≡ 3 (mod 7).
But (5x + 2y) ≡ (−2x + 2y) ≡ 10 (mod 7), so (y − x) ≡ 5 (mod 7).

7
 Therefore either y − x is −2 or 5. The sum is 5 − 2 = 3.

TF10 Problem The sum of the first ten terms of an arithmetic sequence
is 155 and the sum of the first two terms of a geometric sequence is
9. Find all possible ordered pairs of the common difference and the
common ratio (d, r) if the common difference is the first term of the
geometric sequence and the common ratio is the first term of the
arithmetic sequence.
2 25
Answer (3, 2) and ( , )
3 2
Solution As from the problem let the common difference, and the
first term of the geometric sequence, be d; and let the common ratio,
and the first term of the arithmetic sequence, be r. Then we know
that r + (r + d) + (r + 2d) + ⋯ + (r + 9d) = 10r + 45d = 155, and
9
d + dr = 9. Solving for r in the second equation gives r = − 1 (since
d
90
d =/ 0). Then, −10+45d = 155. This simplifies to 90+45d 2 = 165d,
d
2
or 3d 2 − 11d + 6 = 0 ⇒ (d − 3)(3d − 2) = 0. Therefore d = 3 or d = .
3
2 25
If d = 3 then r = 2; if d = then r = . Thus the ordered pairs are
3 2
2 25
(3, 2) and ( , ).
3 2
TF11 Problem Suppose you have a circular pizza divided into six equal

8
slices, and you have to choose one flavor for each slice. If there are
three flavors to choose from, and adjacent slices have to have different
flavors, how many ways are there to flavor the pizza?
Answer 14
Solution Three cases have to be considered: one where there are three
slices of one flavor and three of another; one where there are two slices
for each of the three flavors; and another where there is one slice of
the first flavor, two of the second, and three of the third. One cannot
have 4 or more slices for one flavor as it will require some adjacent
slices to have the same flavor.

Case 1. Three slices for each of two flavors. If the flavors are A and B
then one can only have ABABAB as the order of the flavors. Note that
ABABAB = BABABA since this is just rotation by one slice. Therefore
3
there are ( ) = 3 ways in this case.
2
Case 2. Two slices for each of three flavors. The only possible permuta-
tions are ACBCAB, ABCBAC, ABCABC, ACBABC, and ACBACB.
All other permutations are rotations of any of the above. Thus there
are five ways here.

Case 3. One slice for the first flavor, two for the second, three for the

9
 third. If we first denote the flavor with three slices as A, the one with
two as B, and the last one C our only permutation is ABABAC. Now
there are three choices for A, two for B and one for C. Thus we have
6 ways.

Therefore we have a total of 3 + 5 + 6 = 14 ways.

TF12 Problem In a diving competition, 5 judges score each dive on a scale

from 1 to 10. The point value of the dive is obtained by dropping the
highest and lowest scores and multiplying the sum of the remaining
scores by the degree of difficulty. If a dive with a degree of difficulty
of 3.2 received scores of 7.5, 8.0, 9.0, 6.0 and 8.5, what was the point
value of the dive?
Answer 76.8
Solution The sum of the scores excluding the highest and lowest
scores is 24. Multiplying by 3.2 we get 76.8.

TF13 Problem For what real values of k will the function f (x) = (k −2)x +
3k − 4, x ∈ R be even, and for what values of k will the function be
odd?
4
Answer Even: k = 2; Odd: k =
3
Solution An even function f satisfies f (−x) = f (x). Therefore we

10
 have −(k − 2)x + 3k − 4 = (k − 2)x + 3k − 4 for all real x, thus k − 2 = 0.
Thus k = 2 will make the function even.

An odd function, meanwhile, satisfies f (−x) = − f (x). Therefore we

have −(k − 2)x + 3k − 4 = −((k − 2)x + 3k − 4) for all real x, which
4
implies 3k − 4 = 0. Thus k = will make the function odd.
3
TF14 Problem Lewis has five cards. Each card has one black and one white
face. He shuffles the five cards and puts them in a row. If Lewis can
flip consecutive cards with the same face to the other face, what is the
expected value of the minimum number of flips needed to make all
the cards black face up?
3
Answer
2
Solution We work by cases. For brevity a “white card” means a card
whose white face is face up.

Case 1. There are exactly 0 white cards. The probability of this hap-
1
pening is and 0 flips are needed.
32
Case 2. There is exactly 1 white card. The probability of this happening
5
is and 1 flip is needed.
32
Case 3. There are exactly 2 white cards. The probability of the two

11
 4
cards being adjacent is and 1 flip is needed. The probability that
32
6
the two are not adjacent is and 2 flips are needed.
32
Case 4. There are exactly 3 white cards. The probability that the
3
three cards are adjacent is and 1 flip is needed. The probability
32
6
that exactly two of the three cards are adjacent is and 2 flips are
32
1
needed. The probability that none are adjacent is and 3 flips are
32
needed.

Case 5. There are exactly 4 white cards. The probability that the four
2
cards are adjacent is and 1 flip is needed. The probability that
32
3
exactly three of the four are adjacent is and 2 flips are needed.
32
Case 6. There are exactly 5 white cards. The probability that this
1
happens is and 1 flip is needed.
32
1 5 4 6 3
Therefore, the expected value is ⋅0+ ⋅1+ ⋅1+ ⋅2+ ⋅
32 32 32 32 32
6 1 2 3 1 48 3
1+ ⋅2+ ⋅3= ⋅1+ ⋅2+ ⋅1= = .
32 32 32 32 32 32 2
TF15 Problem In the cryptarithm APAT + APAT = WALO, each letter
consistently represents one digit from 0 to 9. Two letters cannot rep-
resent the same digit, and a number cannot start with the digit zero.

12
What is the sum of all possible values of the 4-digit number WALO?
The letter O does not necessarily represent the digit zero.
Answer 40 226
Solution First, A can only be 1, 2, 3 or 4. Also, either W is one more
than L or one less. In fact, A cannot be 1 or 3 because there are no
integer solutions for 2P = 1, 2P = 11, 2P = 3 or 2P = 13.

Case 1. A = 2. First consider the case where W = 4 and L = 5:

2P2T + 2P2T = 425O. Here, P = 1 as there is no carry-over to the
thousands place. On the other hand, there is a carry-over to the tens
place; thus T ≥ 5. T cannot be 5 as it has already been used. If T = 6,
then O = 2; but A = 2. If T = 7, O = 4; if T = 8, O = 6; and if T = 9,
O = 8. These are the three solutions.

2 1 2 ❙
5✓
✓❙ 2 1 2 6 2 1 2 7
+ 2 1 2 ❙
5❙
✓✓ + 2 1 2 6 + 2 1 2 7
4 2 5 0 4 2 5 ✓
2
❙ 4 2 5 4

2 1 2 8 2 1 2 9
+ 2 1 2 8 + 2 1 2 9
4 2 5 6 4 2 5 8
If W = 5 and L = 4, then P = 6 and T ≤ 4 since there is a carry-over

13
to the thousands place and none to the tens place. If T = 0, O = 0,
contradicting the fact that all letters must represent different digits.
If T = 1, O = 2; but A = 2. Similarly T =/ 2. If T = 3, O = 6, but P = 6.
T =/ 4 since L = 4. Therefore there are no solutions for this case.

2 6 2 ❙
0✓
✓❙ 2 6 2 1 2 6 2 ❙2✓
+ 2 6 2 ❙
✓✓ + 2 6 2 1
0❙ + 2 6 2 ✓
2
❙

5 2 4 ❙
0❙
✓✓ 5 2 4 ✓
2
❙ 5 2 4 ✓
4
❙

2 6 2 3 2 6 2 ✓
4
❙

+ 2 6 2 3 + 2 6 2 ❙4✓
5 2 4 ❙
6❙
✓✓ 5 2 4 8

Case 2. A = 4. First consider the case where W = 8 and L = 9. Then

2P = 4 or P = 2. Since there is a carry-over to the tens digit, T ≥ 5. If
T = 6, O = 2 but already P = 3. If T = 7, O = 4 but L = 4. T =/ 8 as
W = 8 and T =/ 9 as L = 9. Thus, T can only be 5, and O = 0.

4 2 4 5 4 2 4 6 4 2 4 7
+ 4 2 4 5 + 4 2 4 6 + 4 2 4 7
8 4 9 0 8 4 9 ❙2✓ 8 4 9 ❙4✓

14
 4 2 4 ❙
8❙
✓✓ 4 2 4 ❙
9❙
✓✓

+ 4 2 4 ❙
8✓
✓❙ + 4 2 4 ❙
9✓
✓❙

8 4 9 6 8 4 9 ❙
8❙
✓✓

If W = 9 and L = 8, then P = 7. Now T ≤ 4 as there is no carry-over

to the tens digit. If T = 0, O = 0 which cannot be; if T = 2, O = 4 but
already A = 4. Similarly T =/ 4. If T = 1, O = 2; if T = 3; O = 6. These
are the two solutions.

4 7 4 ❙
0✓
✓❙ 4 7 4 1 4 7 4 2
+ 4 7 4 ❙
0❙
✓✓ + 4 7 4 1 + 4 7 4 2
9 4 8 ❙
0✓
✓❙ 9 4 8 2 9 4 8 ❙4✓

4 7 4 3 4 7 4 ❙4✓
+ 4 7 4 3 + 4 7 4 ✓
4
❙

9 4 8 6 9 4 8 ❙
8❙
✓✓

Our solutions are 4254, 4256, 4258, 8490, 9482, 9486. Their sum is
40 226.

15
Individual Semifinals
Easy Round

IS-E1 Problem Bulbasaur, Charmander, and Squirtle have some berries

to eat. All three are in a generous mood, so Bulbasaur gives Char-
mander as many berries as Charmander has and Squirtle as many
Squirtle has. Then, Charmander does the same, giving Bulbasaur
and Squirtle as many berries as they each have. Finally, Squirtle
gives Bulbasaur and Charmander as many berries as each have. If
after this each has 16 berries, how many berries did Bulbasaur have
at first?
Answer 26
Solution We work backwards. Before Squirtle shared its berries
16
we know that Bulbasaur and Charmander each have = 8 berries.
2
Since there is a total of 48 berries, Squirtle has 48−8−8 = 32 berries.
8
Before Charmander shared, Bulbasaur has = 4 berries and Squir-
2
32
tle, = 16 berries, leaving Charmander with 48 − 4 − 16 = 28
2
berries. Thus, at the beginning of the game, before Bulbasaur shared,
28 16
Charmander has = 14 berries and Squirtle, = 8 berries. Thus,
2 2
Bulbasaur has 48 − 14 − 8 = 26 berries.

16
IS-E2 Problem Find the last digit of 711 + 810 − 912 .
Answer 4
Solution Note that 711 < 911 and 810 < 911 . Thus 711 +810 < 911 +911 <
912 , and the given expression is negative. From modulo arithmetic
it is known that the last digit of 711 is 3, the last digit of 810 is 4, and
the last digit of 912 is 1. Therefore the last digit of 711 + 810 − 912 is
not 3 + 4 − 1 = 6, but 10 − 6 = 4.

IS-E3 Problem A convex polyhedron consists solely of hexagonal and

quadrilateral faces. If for all vertices three faces meet at a vertex,
how many quadrilateral faces are there?
Answer 6
Solution Let there be m hexagonal faces and n quadrilateral faces.
6m + 4n 6m + 4n
We have m + n faces, vertices, and edges, since
3 2
two adjacent faces of convex polyhedra always meet at an edge. By
6m + 4n 6m + 4n
Euler’s polyhedron formula we have +(m+n) = +
3 2
2. Simplifying the equation, the m’s cancel out, and n = 6.

IS-E4 Problem At how many points do the graphs of y = 2 log x and

y = log(2x) intersect in the x y-plane?
Answer 1

17
 Solution 2 log x = log(2x) implies that x 2 = 2x, since 2 log x =
log x 2 . This gives us x = 0 or x = 2. If x = 0, there is no value for
y as log 0 is undefined; if x = 2, y = 2 log 2. Therefore there is only
one intersection.

IS-E5 Problem How many permutations of five distinct letters are there
if one letter has to be in front of another?
Answer 60
Solution Without the restriction, there are 5! = 120 permutations.
Now there is a bijection between permutations where one letter, say
A, is always in front of another, say B, and permutations where B is
ahead of A. Thus exactly half of the permutations satisfy the given
120
condition, or = 60 permutations.
2
Average Round

IS-A1 Problem At most how many circles of radius 1 cm can fit inside a
square with side 20 cm such that the circles do not overlap?
Answer 105
Solution The circle have to be packed such that adjacent circles’
centers form equilateral triangles. Refer to the following figure.

18
 √
3

Since the diameter of each circle is 2 cm, then ten of them can fit
exactly on the bottom row. Thus the second bottom row will have
one less (9 circles). The rows will alternate having 10 and 9 circles.
Now we have to find how many rows there will be.
√
If there are n rows, then the height will be 2 + (n − 1) 3. Now
√ √
2 + (n − 1) 3 ≤ 20, or n ≤ 6 3 + 1. But 100 < 108 < 121 ⇒ 10 <
√ √ √
6 3 < 11 ⇒ 11 < 6 3+1 < 12. Therefore there are ⌊6 3 + 1⌋ = 11
rows. There are six rows with ten circles and five rows with nine
circles, thus we can fit at most 60 + 45 = 105 circles.
2016 √
IS-A2 Problem Evaluate the series ∑ kik , where i = −1.
k=0
Answer 1008 − 1008i
2016 4n+4
Solution The sum is equal to ∑ kik . We consider the sum ∑ kik ,
k=1 k=4n+1
where n is a nonnegative integer. This sum is (4n + 4) − (4n + 2) +

19
 ((4n + 1) − (4n + 3))i = 2 − 2i. This happens 504 times, thus the
answer is 1008 − 1008i.

IS-A3 Problem An unfair coin is tossed n times, for some positive integer
√
n. If the variance of the distribution of the number of heads is 99,
find the minimum possible value for n.
Answer 40
Solution The variance of the binomial distribution Bi(n, p) is np(1−
√
p) = 99, where p is the probability of heads. By AM-GM, p(1 −
1 √ n √ √
p) < (as p =/ 1 − p), so 99 < , or n > 4 99 = 1584. Since
√4 √ √ 4
39 = 1521 < 1584 < 1600 = 40, the minimum possible value
of n is 40.

IS-A4 Problem A turtle born on January 1 in the first half of the nineteenth
century was x years old in the year x 2 . How old is it now, in years?
Answer 210 years old
√ √ √
Solution We see that 42 = 1764 < 1800 < 1849 = 43 <
√
1850. Thus x = 43, and the turtle was born in 432 − 43 = 1806. It
is now 210 years old.

IS-A5 Problem Find the sum of all values of x that satisfy the equation
2⌊x⌋ = x + 2{x}, where ⌊x⌋ is defined as the least integer greater

20
 than or equal to x, and {x} = x − ⌊x⌋.
Answer 4
Solution Substituting x = ⌊x⌋ + {x} into the original equation gives
us 2⌊x⌋ = ⌊x⌋ + 3{x}, or ⌊x⌋ = 3{x}. Since 0 ≤ {x} < 1, 0 ≤ ⌊x⌋ < 3.
Thus ⌊x⌋ can only be 0, 1, or 2.
1
If ⌊x⌋ = 0, then {x} = 0, and x = 0; if ⌊x⌋ = 1, then {x} = and
3
4 2 8
x = ; if ⌊x⌋ = 2, then {x} = and x = . The sum of all possible
3 3 3
values, then, is 4.

Difficult Round

IS-D1 Problem A polynomial f with positive integer coefficients satisfies

f (12) = 311×113. If the sum of its coefficients is 31, find all possible
values of f (10).
Answer 57 034
Solution Let f (x) = a n x n + a n−1 x n−1 + ⋯ + a1 x + a0 . Then f (12) =
a n 12n + a n−1 12n−1 + ⋯ + a1 ⋅ 12 + a0 . A possible set of values for the
coefficients are the consecutive digits of the base-12 representation
of 311 × 113 = 35 14310 = 18 40712 . Note that the sum of the digits
here is 20, and that 20 + 12 − 1 = 31.

21
 Currently our function is f (x) = x 4 + 8x 3 + 4x 2 + 0x + 7, and to
make the sum of the coefficients 31, 1 has to be decreased from a
coefficient and 12 added to the coefficient of the lower power of x.
We can’t remove 1 from 0, as all coefficients are positive (having a
coefficient as zero just means the term won’t exist, and so does not
violate the conditions). Thus the possible functions are f1 (x) = x 4 +
8x 3 +3x 2 +12x +7, f2 (x) = x 4 +7x 3 +16x 2 +7, f3 (x) = 20x 3 +4x 2 +7.
Then f1 (10) + f2 (10) + f3 (10) = 18 427 + 18 607 + 20 407 = 57 034.
¿ √
Á √ √
3 3 √
Á
À 3 3 3
√3
IS-D2 Problem Evaluate 21 21 21 23 25 29 ⋯, where the expo-
nents of 2 are from the successive terms of the sequence 1, 1, 1, 3, 5, 9, . . .,
where the first three terms are 1 and succeeding terms are generated
by getting the sum of the last three terms.
√
Answer 7 16
Solution Denote by a the given expression. Then

1 1 1 3 5 9 1 1 1 3 5 9
a = 2 3 2 9 2 27 2 81 2 243 2 729 ⋯ = 2 3 + 9 + 27 + 81 + 243 + 729 +⋯ .

22
 Let the exponent of a be x. Then
1 1 1 3 5 9
x= + + + + + +⋯ (1)
3 9 27 81 243 729
1 1 3 5 9
3x = 1+ + + + + +⋯ (2)
3 9 27 81 243
1 3 5 9
9x = 3 + 1+ + + + +⋯ (3)
3 9 27 81
3 5 9
27x = 9 + 3 + 1+ + + +⋯ (4)
3 9 27
8 4
(4) − (3) − (2) − (1) gives us (27 − 9 − 3 − 1)x = 8 or x = = .
4 √ √ 14 7
7
Therefore a = 2 = 2 = 16.
7 4 7

IS-D3 Problem How many 2016-digit positive integers that only have dig-
its 1, 2, 3, and 4 are there such that the number has an even number
of 2’s?
Answer 24031 + 22015
Solution Let a n be the number of n-digit integers that satisfy the
above condition. Also, let b n be the number of n-digit integers
with only 1, 2, 3, and 4 but with an odd number of 2’s. Then a n =
3a n−1 + b n−1 , because a n consists of all numbers with either (a) 1,
3, or 4 as the first digit and with an even number of 2’s among the
succeeding (n − 1) digits, or (b) 2 as the first digit and with an
odd number of 2’s among the succeeding (n − 1) digits. Similarly

23
 b n = 3b n−1 + a n−1 . Also, the initial values are a1 = 3, b1 = 1.

Adding the two equations together gives us a n +b n = 4(a n−1 +b n−1 ),

a1 + b1 = 4. Therefore, a n + b n = 4n .

Similarly, subtracting one from the other results in a n −b n = 2(a n−1 −

b n−1 , a1 − b1 = 2. Therefore, a n − b n = 2n . This means that a n =
4n + 2n 4n − 2n
and b n = .
2 2
42016 + 22016
The question is asking for a2016 , which is = 24031 +22015 .
2
IS-D4 Problem For each of the about 7 billion people in the world, com-
pute the product of the number of fingers in his/her right hand, left
hand, right foot and left foot. Suppose the about 7 billion products
are also multiplied together. Give a reasonable estimate, within 5%
of the exact answer, of this value. You may leave your answer in
exponential form.
Answer 0
Solution An amputee will have zero as the product, and thus the
product of all the numbers is zero. Only zero is accepted since
0 ± 5% = 0.

IS-D5 Problem The angle of elevation of a building is observed from a

24
point on the horizontal plane on which it stands. At a point x feet
nearer the angle of elevation is the complement of the original angle
observed. At another point y feet nearer (from the second point)
the angle of elevation is now double the first. Express the height of
the building
√ in terms of x and y.
2
x 2
Answer (x + y) − ( )
2
Solution Let the original angle of elevation observed have measure
A, the height of the building be h, and the distance between the
building and the third point be z. Then from the given tan A =
h y+z h
= , and tan 2A = . Now from the double-angle
x+y+z h z
y+z
2(
2(y + z)h
)
h h
formula = 2 = 2 2
, or 2z(y + z) = h2 − (y +
z y+z h (y + z)
1−( )
h
z)2 ⇒ h2 = (y + z)(y + 3z).
h y+z
But = ⇒ h2 = (y + z)(x + y + z). Equating the
x+y+z h
x
two implies x + y + z = y + 3z as y + z =/ 0. Therefore, z = . Now
2
2 2
3 2 2
x 2
h = (y + z)(x + y + z) = y + 2x y + x = (x + y) − ( ) , or
√ 4 2
2
x
h = (x + y)2 − ( ) .
2

25
Individual Finals
√
−1 + 5
E Problem What is the value of φ12 + φ8 + φ5 + 160φ, where φ = .
2
Answer 99
Solution Note that φ2 + φ − 1 = 0.

First, we show by induction that for all positive integers n,

φ n = (−1)n+1 Fn φ + (−1)n Fn−1 ,

where F0 = 0, F1 = 1, Fi = Fi−1 + Fi−2 for integers i ≥ 2 are the Fibonacci

numbers.

Now for n = 1, LHS = (−1)2 F1 φ + (−1)1 F0 = φ + 0 = φ = RHS.

Assume that the statement is true for n = k. Then φ k = (−1)k+1 Fk φ +

(−1)k Fk−1 . Now for n = k + 1:

φ k+1 = φ k φ = ((−1)k+1 Fk φ + (−1)k Fk−1 ) φ

= (−1)k+1 Fk φ2 + (−1)k Fk−1 φ
= (−1)k+1 Fk (−φ + 1) + (−1)k Fk−1 φ
= (−1)k φ (Fk + Fk−1 ) + (−1)k+1 Fk
= (−1)k φFk+1 + (−1)k+1 Fk
= (−1)k+2 φFk+1 + (−1)k+1 Fk

26
 Thus the statement is true for n = k + 1, and by induction true for all
positive integers n. This means that

φ12 = (−1)13 F12 φ + (−1)12 F11 = −144φ + 89

φ8 = (−1)9 F8 φ + (−1)8 F7 = −21φ + 13
φ5 = (−1)6 F5 φ + (−1)5 F4 = 5φ − 3

Adding these three equations gives us φ12 + φ8 + φ5 = −160φ + 99, or

φ12 + φ8 + φ5 + 160φ = 99.

A Problem In a class election for class head, 44 students write their choice
on a slip of paper. Now the teacher counts the votes in a uniformly
random order. If Student A gets 26 votes and Student B gets 18 votes,
what is the probability that Student A never trailed during the counting
process?
1
Answer
3
Solution We define a list like ABAABAB . . ., which tells us who was
selected for the ith slip. Now, since the votes for A and votes for B can
44
be rearranged we have ( ) lists with 26 A’s and 18 B’s.
18
We call a list with 26 A’s and 18 B’s good if it satisfies the given condition
and bad otherwise. A list is bad when there exists a k such that A has

27
 k votes and B has k + 1 votes. The smallest k is the first time A trails.
For every bad list, after the first instance A trails, we swap all remaining
votes of A to B and vice versa. Therefore after this point A gets 17 − k
votes and B gets 26 − k votes, giving us A with k + 17 − k = 17 votes and
B with k + 1 + 26 − k = 27 votes.

After the manipulation, B will always win. Therefore any list with 17 A’s
and 27 B’s can be reverted to a bad list by selecting the first time B has
more votes than A (which is guaranteed) then swapping A’s votes with
B’s votes afterwards. Thus there exists a bijection between bad lists and
44
lists with 17 A’s and 27 B’s, and there are ( ) bad lists.
17
Thus, the probability is

# of bad lists (44) 44!26!18! 2 1

(1 − ) = 1 − 17 = 1 − = 1 − = .
# of lists (44
18) 27!17!44! 3 3

2064
∏ k!
D Problem Find all nonnegative integers N ≤ 2064 such that is a
k=1
N!
perfect square.
Answer 1032

28
Solution First we show that 1032 is a solution.
2064 1032
∏ k! = ∏ (2k)!(2k − 1)!
k=1 k=1
1032
= ∏ (2k) ((2k − 1)!)2
k=1
1032 1032
= ( ∏ ((2k − 1)!)2 ) (21032 ∏ k)
k=1 k=1
1032 2
= (2516 ∏ (2k − 1)!) (1032!)
k=1

Therefore N = 1032 is a possible solution. Now assume for the sake

of contradiction that there exists another nonnegative integer M that
M!
satisfies this condition. Then it follows that either (if M > 1032)
1032!
2064 2064
∏ k! ∏ k!
1032!
or (if M < 1032) is a perfect square, since both and
k=1 k=1
M! 1032! M!
are perfect squares.
M!
Note that if M > 1032, then will always contain only one copy of
1032!
M!
1033, since 1033 is prime. Thus will never be a perfect square.
1032!
1032!
Similarly, if M < 1032, then will always contain only one copy of
M!
1032!
1031, since 1031 is prime. Thus will never be a perfect square.
M!
Therefore only N = 1032 satisfies the given condition.

29