International Mathematical Olympiad

Preliminary Selection Contest — Hong Kong 2006

Outline of Solutions

Answers:

6− 2
1. 666 2. 1475 3. 60 4.
2

4 3 27
5. 6. 2 7. 8. 32
3 23

9. 30000 10. 240 11. 4020 12. 6

13. 1505 14. 3456 15. 51 16. 30

16 17
17. 18. 281 19. 2310 20. 13
17

Solutions:

1. Let the two numbers be x and y. Then we have x + y = xy − 2006 . Upon factorisation, we have
( x − 1)( y − 1) = 2007 .

Since 2007 = 32 × 223 , it has 6 positive factors, namely, 1, 3, 9, 223, 669 and 2007. As one of x
and y (say, x) is a perfect square, x − 1 must be 1 less than a perfect square. Among 1, 3, 9, 223,
669 and 2007, only 3 has this property ( 3 = 22 − 1 ). Therefore we should take x − 1 = 3 and
y − 1 = 669 , i.e. x = 4 and y = 670 . It follows that the answer is 670 − 4 = 666 .

2006n 20062 + 2006n 20062 20062

2. Note that = − = 2006 − .
2006 + n 2006 + n 2006 + n 2006 + n
Hence, in order for 2006n to be a multiple of 2006 + n , 2006 + n must be a factor of 20062 .
As 1 ≤ n ≤ 2005 , we have 2007 ≤ 2006 + n ≤ 4011 . As 20062 = 22 × 17 2 × 592 , the only factor of
2006 + n between 2007 and 4011 is 592 = 3481 . Hence we must have 2006 + n = 3481 , or
n = 1475 .

1
3. Let x be the normal walking speed of Peter and u be the speed of the escalator. Since speed is
u + x 30
inversely proportional to time taken, we have = , which gives u = 2 x . Let the
u + 2 x 40
u 40 40(u + x) 40(2 x + x)
answer be t seconds. Then we have = , so that t = = = 60 .
u+x t u 2x

4. We claim that AC = 1 . If AC > 1 , then by

A
considering ∆DAC we see that ∠DAC must be B
smaller than 60° (recall that in a triangle, the side 135° 75°
1
opposite a larger angle is longer), while ∠CAB must
be smaller than 75° by considering ∆ABC. It leads to 1
the contradiction ∠DAB < 135° . In a similar way, we D
can get a contradiction when AC < 1 , thereby 1
establishing the claim. Now ∆CAB is isosceles with C
CA = CB = 1 and base angles 75°. Therefore
AB = 2 cos 75°
= 2 cos(45° + 30°)
= 2(cos 45° cos 30° − sin 45° sin 30°)
6− 2
=
2

5. We claim that X is the circumcentre of ∆ABC.

A
Assuming the claim, we know from the sine
4 4 3
law that = 2 AX , so that AX = . 60°
sin 60° 3
It remains to prove the claim. Since X is on the X I
perpendicular bisector of BC, we have
XB = XC . It therefore suffices to show that B C
∠BXC = 2∠BAC = 120° . But this is clear, 4
because
∠BXC = ∠BIC
= 180° − ∠IBC − ∠ICB
∠ABC ∠ACB
= 180° − −
2 2
180° − ∠BAC
= 180° −
2
= 120°

2
  π
6. Let x = cos θ where 0 ≤ θ ≤ π . Then x + 1 − x 2 = cos θ + sin θ = 2 cos  θ −  . Since the
 4
maximum value of the cosine function is 1, the maximum value of x + 1 − x 2 is 2 , and
π 2
equality is attained when θ = , i.e. when x = .
4 2
Remark. A solution using calculus obviously exists.

7. Note that Sn and Tn , both being the sum of the first n terms of an arithmetic sequence, are
both quadratic polynomials with constant term 0. Hence we may assume Sn = An 2 + Bn and
Tn = Cn 2 + Dn . Consequently, an = Sn − Sn −1 = 2 An + ( B − A) . Similarly bn = 2Cn + ( D − C ) .
Plugging these into the given equation, we have
2 An + ( B − A) 2n − 1
= ,
2Cn + ( D − C ) 3n + 1
which gives 6 An 2 + (3B − A)n + ( B − A) = 4Cn 2 + (2 D − 4C )n + (C − D) . As this is true for all
3A 5A
n, we equate the coefficients to solve for A, B, C, D. We get B = 0 , C = and D = .
2 2
Hence we have
S9 A(9) 2 + (0)(9) 27
= = .
T6  3 A  2  5 A  23
  (6) +   (6)
 2   2 
Remark. It is easy to guess the answer if one assumes an = 2n − 1 and bn = 3n + 1 .

8. Note that the point G is not useful except that it

H
tells us that the chord AB subtends an angle of
48°× 2 = 96° at the centre of the circle (which
we call O) so that ∠EOF = 96° ÷ 3 = 32° . We
claim that HA // OE and HB // OF. Assuming
the claim, then ∠AHB = ∠EOF = 32° and
hence the answer would be 32.
O
It remains to prove the claim. To show that HA
// OE, we shall prove that AF is perpendicular
to both HA and OE. That AF ⊥ OE is clear, C D
A B
because E is the mid-point of arc AF. Now
produce HA and FE to meet at K. First note that
K
AE = EF , and AC = CD implies KE = EF . In E F
other words, the circle with diameter KF passes
through A, so AF ⊥ HA. This shows HA // OE,

3
 and by the same argument we have HB // OF,
thereby establishing the claim.

9. Suppose Tommy invests $a, $b and $c on funds A, B and C respectively. Clearly, as long as a
positive net profit can be guaranteed, we must take a + b + c = 90000 . Then we want to
maximise
n = min{3a, 4b, 6c} − 90000

subject to the above conditions.

For maximality, we must have 3a = 4b = 6c . This is because when 3a, 4b and 6c are not all
equal, say, if 3a < 4b and 3a ≤ 6c , then Tommy can shift some investments from fund B to
fund A (or some to fund C as well, if necessary). In this way the value of 3a increases while the
values of 4b and 6c will remain greater than or equal to 3a when the shift is sufficiently small.
Therefore n increases, i.e. the value of n cannot be maximum when 3a, 4b and 6c are not all
equal.
1 1 1
Hence, in order to attain maximality, we want a : b : c = : : = 4 : 3 : 2 . In this case, the
3 4 6
maximum value of n is
4
3a − 90000 = 3 × 90000 × − 90000 = 30000 .
4+3+ 2

10. We first choose 4 boxes to place balls A, B, C, D. There are 10 possible combinations, namely,
1234, 1245, 1256, 1267, 2345, 2356, 2367, 3456, 3467 and 4567. Once the 4 boxes are chosen,
there are 4 ways to place ball A, and then 1 way to place ball B (once ball A is placed there is
only one possible position for ball B in order that balls C and D can be placed in boxes with
consecutive numbers), and finally 2 ways to place balls C and D. There are 3 remaining boxes
in which ball E can be placed. Hence the answer is 10 × 4 × 2 × 3 = 240 .

11. Let O be the common centre of the two

circles, and let P' be a point such that
A
∆APP' is equilateral and that B and P' are
on different sides of AP. Observe that P'
PA = PP ' and PB = CP ' (as ∆BAP ≅
O
∆CAP'), so ∆PCP' is the desired triangle.
Let R = 2007 , r = 2006 , ∠POB = x and B C
∠POC = y. Then we have x + y = 120°
x− y
and = 60° − y . Now P
2
4
 [ PCP '] = [ APP '] − [ APC ] − [ AP ' C ]
= [ APP '] − [ APC ] − [ APB]
= [ APP '] − [ ABPC ]
= [ APP '] − [OAB] − [OAC ] − [OBP] − [OCP]
3 2 2 3 2 2 1
=  R + r − 2 Rr cos(120° + y )  − (r + r ) − Rr (sin x + sin y )
4 4 2
3 2 2 3 1 x+ y x− y
= (R − r ) + Rr cos(60° − y ) − Rr ⋅ 2sin cos
4 2 2 2 2
3 2 2 3 3
= (R − r ) + Rr cos(60° − y ) − Rr cos(60° − y )
4 2 2
3 2 2
= (R − r )
4
4013 3
=
4
Hence a + b + c = 4013 + 3 + 4 = 4020 .

Remark. It would be easy to guess the answer if one considers the special case where A, O, P
are collinear.

12. Each face of the octahedron is an equilateral triangle of side length 6, the altitude of which is
6sin 60° = 3 3 . Consequently, half of the octahedron (i.e. the square pyramid in which every
(3 3 )
2
edge has length 6) has altitude − 32 = 3 2 , i.e. the volume of the octahedron is
1
2 × × 62 × 3 2 = 72 2 .
3
On the other hand, if we let r be the radius of the inscribed sphere of the regular octahedron
and A be the surface area of the octahedron, then the volume of the octahedron would also be
1 1 1
equal to Ar . Now A = 8 × × 6 × 3 3 = 72 3 . Hence we have × 72 3 × r = 72 2 , which
3 2 3
gives r = 6 . This is also the greatest possible radius of a sphere which can be placed inside
the tetrahedron.

n2
13. Let f (n) = . For n ≤ 1003 , we have
2006
n2 (n − 1) 2 2n − 1
f (n) − f (n − 1) = − = <1
2006 2006 2006
10032
Since f (1) = 0 and f (1003) = = 501.5 , the sequence contains every integer from 0 to
2006
501 inclusive. On the other hand, when n > 1003 ,

5
 2n − 1
f (n) − f (n − 1) = >1.
2006
Moreover, since
10042 (1003 + 1) 2 10032 2 ×1003 1 1
f (1004) = = = + + = 501.5 + 1 + > 502 ,
2006 2006 2006 2006 2006 2006
10042  10052   20062 
we see that   
,  , …,   are all distinct integers, all greater than 501.
 2006   2006   2006 
Therefore, the number of different integers in the sequence is 502 + 1003 = 1505 .
0 to 501 = 502 and thereafter from 1004 to 2006 is 1003

14. Such positive integers are all divisible by 9 since each has sum of digits 0 + 1 + 2 + + 9 = 45 .
Hence we can change the number ‘11111’ in the question to ‘99999’ without affecting the
answer. We denote such a 10-digit positive integer by ABCDEFGHIJ . For this number to be
divisible by 99999, a necessary and sufficient condition is that ABCDE + FGHIJ should be
divisible by 99999 (see Remark). Hence ABCDE + FGHIJ must be exactly 99999. In other
words, each of A + F , B + G , C + H , D + I and E + J must be equal to 9, i.e. we need only
choose A, B, C, D, E. There are 9 choices for A as it cannot be zero (once A is chosen, F is also
fixed). There are 8 choices for B as it cannot be equal to A and F (once B is chosen, G is also
fixed). Similarly, there are 6, 4, 2 choices for C, D, E respectively, and at the same time H, I, J
are fixed. Hence the answer is 9 × 8 × 6 × 4 × 2 = 3456 .

Remark. The divisibility test for 99999 is to put the digits into groups of 5 from the right, and
then add up the numbers (as positive integers) in each group. The original number is divisible
by 99999 if and only if the sum obtained is divisible by 99999. In the 10-digit case, this can be
explained by the following congruence equation:
ABCDEFGHIJ = 100000 × ABCDE + FGHIJ
≡ 1× ABCDE + FGHIJ
= ABCDE + FGHIJ (mod 99999)

15. Since ABCDEF is convex, it must be either C y

or F which has y-coordinate 4. Suppose C has D (d, 10)
y-coordinate 4. Then, since AB = BC , either C
must be either (2b, 4) or (0, 4), both of which E (e, 8)
are not allowed (as the former implies that A, B, C (c, 6)
C are collinear while the latter implies that
F (f, 4)
ABCDEF is concave). Hence F has y-
coordinate 4. Furthermore, since CD // AF, the B (b, 2)
y-coordinate of D exceeds that of C by 4. It x
A (0, 0)
follows that the y-coordinates of D and C are 10
6
 and 6 respectively, and thus the y-coordinate of
E is 8.
Let C = (c, 6), D = (d, 10), E = (e, 8) and F = (f, 4). From the fact that BC = CD , we know that
b = d , i.e. BD is vertical. As AB and ED are equal and parallel, ABDE is a parallelogram, and
hence AE is also vertical , so e = 0 . Furthermore, ∆AEF and ∆BCD are congruent by the SSS
condition. Note also that f < 0 by the convexity condition.
1
Now the area of ABCDEF is equal to 2 [ AFE ] + [ ABDE ] = 2 × × 8 × (− f ) + 8b = 8(b − f ) , so
2
we must find the values of b and f. Let x be the side length of the hexagon. Computing the
lengths of AB and AF respectively, we have
x 2 = b 2 + 4 = f 2 + 16 .

On the other hand, since ∠FAB = 120°, applying cosine law in ∆FAB gives
b^2+f^2 - 2bf + 4 = 3x^2
expressing x and f in terms of b we get : (b − f ) 2 + (2 − 4) 2 = x 2 + x 2 − 2( x)( x) cos120° = 3 x 2 .
3b^4 - 88b^2 - 400 = 0. Now solving the
quadratic in b^2 we get 10 8
b^2 = 100/3 , or Solving, we get b= and f = − . Hence the area of ABCDEF is 8(b − f ) = 48 3 , and
b = 10/sqrt(3). Hence f = - 8/sqrt(3) 3 3
hence the answer is 48 + 3 = 51 .

16. Note that y < 21 , and the triangle inequality in ∆ADE

implies y + y > 21 − y , or y > 7 . It follows that y is A

between 8 and 20 inclusive.

y 21 – y
Now, applying cosine law in ∆ADE and ABC, we get
y 2 + (21 − y ) 2 − y 2 D
cos A = y E
2 y (21 − y )
33 – y y
and
332 + 212 − x 2 B C
cos A = x
2(33)(21)

respectively. Equating and simplifying, we get

y (2223 − x 2 ) = 14553 = 33 × 7 2 × 11 .
Since 8 ≤ y ≤ 20 , the only possible values of y are 9
and 11. These correspond to x 2 = 606 and 900
respectively. As the former is not a perfect square, we
take the latter which corresponds to x = 30 .

7
17. Suppose that in ∆ABC, BC = 3 , AC = 4 and AB = 5 .
Of course ∠ACB = 90°. Without loss of generality, F B E
we fix A at the origin and assume that ∆ABC lies in
the first quadrant, and that the square to enclose 3 θ
5
∆ABC has sides parallel to the coordinate axes and
has A as a vertex. Let ADEF denote the smallest C
4
rectangle with sides parallel to the coordinate axes
θ
that can enclose ∆ABC. Clearly, when ADEF is a A D
square, that is the smallest square that can enclose
∆ABC.
Now suppose ADEF is indeed a square with C on DE and B on EF as shown. Let
∠CAD = ∠BCE = θ . We have AD = 4 cos θ and ED = 3cos θ + 4sin θ . Equating, we get
1 4 16 17
cos θ = 4sin θ and hence tan θ = . Thus AD = 4 cos θ = 4 × = , which is the
4 17 17
desired smallest possible side length.

18. We use (m, n) to denote the H.C.F. of m and n. Using the facts that (m, n) = (m, n + km) for any
integer k and (m, n) = (2m, n) if n is odd, we have

g (n) = ( f (n), f (n + 1)) = (70 + n 2 , 70 + (n + 1) 2 )

= (70 + n 2 , 2n + 1) = (140 + 2n 2 , 2n + 1)
= (140 − n, 2n + 1) = (280 − 2n, 2n + 1)
= (281, 2n + 1)
≤ 281
Hence the largest possible value of g (n) is 281. Finally, 281 is indeed attainable because
f (140) = 70 + 1402 = 281× 70 while f (141) = 70 + 1412 = 281× 71 . It follows that the answer is
281.

M
19. Let M be the L.C.M. of a1 , a2 , …, a11 , and set mi = . Then each mi is a positive integer
ai
and m1 > m2 > > m11 . Furthermore, m1 , m2 , …, m11 form an arithmetic sequence and M is
also the L.C.M. of m1 , m2 , …, m11 . Write b11 = b and bi − bi +1 = d , where b, d are positive
integers. Note that b and d have to be relatively prime by the definition of M. We want to
minimise
lcm(b, b + d , … , b + 10d )
a1 = .
b + 10d
When b = 2 and d = 1 , we find that a1 = 2310 . We prove below that a1 cannot be any smaller,
so that the answer would be 2310. Indeed, if d ≥ 2 , then

8
 lcm(b + 5d , b + 6d , … , b + 10d ) (b + 5d )(b + 6d ) (b + 10d ) 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 4
a1 ≥ = ≥ d > 2310 .
b + 10d 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ (b + 10d ) 2⋅ 2⋅ 2⋅ 2⋅3

Hence we may assume d = 1 . In this case

lcm(b + 5, b + 6, … , b + 10) (b + 5)(b + 6) (b + 10) (b + 5)(b + 6) (b + 9)
a1 ≥ = ≥
b + 10 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ (b + 10) 48
If b ≥ 4 , we see that a1 > 2310 . So it remains to check the cases b = 1, 2, 3. Among these, we
find that b = 2 gives the minimum value a1 = 2310 .

20. Let f (n) be the number of the card received by child n. Consider the sequence
1, f (1) , f ( f (1)) , f ( f ( f (1))) , …
Note that the term 2006 must eventually occur and the sequence can no longer be continued as
f (2006) is undefined. Furthermore, if we let S be the set of integers from 1 to 2006 which
have not occurred in the above sequence, then we see that f ( S ) = S . It easily follows that
every child in S must receive the card with the same number as his own.
It therefore remains to count the number of such sequences, starting from 1 and ending in
2006, and each term (except for the first one) is a multiple of the previous term. Note that
2006 = 2 × 17 × 59 , and every positive factor of 2006 is of the form 2a17b59c and can be
denoted by the three-tuple (a, b, c) where each of a, b, c is 0 or 1. The problem is thus reduced
to counting the number of sequences from (0,0,0) to (1,1,1) for which each coordinate must be
greater than or equal to the corresponding coordinate in the previous term.
If we increase the three coordinates one by one, we get 3! = 6 such sequences. If we first
increase one of the coordinates and then increase the other two at once, we get C13 = 3 such
sequences. If we first increase two of the coordinates at once and then increase the remaining
one, we get C23 = 3 such sequences. Finally, we get 1 such sequence if we jump from (0,0,0) to
(1,1,1) directly. It follows that the answer is 6 + 3 + 3 + 1 = 13 .