1998-1999 Olympiad Correspondence Problems

1998-1999 Olympiad Correspondence Problems

Set 2

7.: For a positive integer n, let r(n) denote the sum of the remainders when n is divided by 1, 2, ¼, n respectively.

: (a) Prove that r(n) = r(n-1) for infinitely many positive integers n.

: (b) Prove that n²/10 < r(n) < n²/4 for each integer n ³ 7.

View solution

8.: Counterfeit coins weigh a and genuine coins weigh b (a ¹ b). You are given two samples of three coins each and you know that each sample has exactly one counterfeit coin. What is the minimum number of weighings required to be certain of isolating the two counterfeit coins by means of an accurate scale (not a balance)?

: (a) Solve the problem assuming a and b are known.

: (b) Solve the problem assuming a and b are not known.

View solution

9.: Similar isosceles triangles EBA, FCB, GDC and DHA are erected externally on the four sides of the planar quadrilateral ABCD with the sides of the quadrilateral as their bases. Let M, N, P, Q be the respective midpoints of the segments EG, HF, AC and BD. What is the shape of PMQN?

View solution

10.: Given two points A and B in the Euclidean plane, let C be free to move on a circle with A as centre. Find the locus of P, the point of intersection of BC with the internal bisector of angle A of triangle ABC.

View solution

11.: Let ABC be a triangle; let D be a point on AB and E a point on AC such that DE and BC are parallel and DE is a tangent to the incircle of the triangle ABC. Prove that 8DE £ AB + BC + CA.

View solution

12.: Suppose that n is a positive integer and that x + y = 1. Prove that

xⁿ⁺¹

n
å
k = 0

æ
ç
è

n+k
k

ö
÷
ø

y^k+ yⁿ⁺¹

n
å
k = 0

æ
ç
è

n+k
k

ö
÷
ø

x^k = 1 .

View solution

Problem 7.

7.: First solution. (a) Suppose that n-1 = iq_i + r_i with 0 £ r_i < i for 1 £ i £ n-1. Then n = iq_i + (r_i + 1). If n is a multiple of i, then r_i + 1 = i. Otherwise, r_i + 1 is the remainder when n is divided by i.

: Thus

r(n)

{ r_i + 1 : 1 £ i £ n-1,i does not divide n }

n-1
å
i = 1

(r_i + 1) -

{ d :d |n, 1 £ d < n }

= r(n-1) + (n-1) -

{ d : d |n,1 £ d < n } .

Hence r(n) = r(n-1) Û the sum of the divisors of n except n itself is n - 1. If n = 2^k, then the sum of the divisors of n less than n is

1 + 2 + ¼+ 2^k-1 = 2^k - 1

with the result that r(2^k) = r(2^k - 1) for each positive integer k.

: (b) Let n = 2k where k ³ 4. Then, since 2k = 2(k-1) + 2, k-1 does not divide 2k. Considering division by k-1, k, k+1, ¼, 2k - 1, we find for even n = 2k ³ 8 that

r(n)

= r(2k) ³ 2 + (k-1) + (k-2) + ¼+ 2 + 1

n²

n²

= r(2k) £ [1 + 2 + ¼+ (k-2)]+ [(k-1) + ¼+ 2 + 1]

= (k-1)² <

n²

: Let n = 2k+1 where k ³ 2. Then considering division by k, k+1, ¼, 2k, we find for n ³ 5 that

r(n)

= r(2k+1) ³ 1 + k + (k-1) + ¼+ 1

n²

n²

= r(2k+1) £ [1 + ¼+ (k-1)]+ [k + (k-1) + ¼+ 1]

= k² <

n²

7.: Second solution. (a) By inspection, we conjecture that r(2^k) = r(2^k - 1) for each positive integer k. Consider any positive integer s between 1 and 2^k which is not a power of 2. Since s does not divide 2^k, 2^k must leave remainder 1 more than the corresponding remainder for 2^k - 1 upon division by s. These values of s contribute 2^k - (k + 1) more to the sum for r(2^k) than to the sum for r(2^k - 1).

: Consider now the numbers of the form 2^t where 0 £ t £ k-1. Divided into 2^k, they leave no remainder, while divided into 2^k - 1, they leave a remainder of 2^t - 1. These values of 2^t contribute

k-1
å
t = 0

(2^t - 1) = (1 + 2 + ¼+ 2^k-1) - k = 2^k - (k + 1)

more to the sum for 2^k - 1 than to the sum for r(2^k). Since 2^k leaves no remainder when divided by 2^k, it follows that r(2^k - 1) = r(2^k).

: (b) Let n = 2m. If m < r < n, then n = r + (n - r) with n - r < r. Hence

m²

n²

n²

when n ³ 10. Let n = 2m + 1. If m < r < n, then

n²

for n ³ 3. Since r(8) = 8 > 8²/10, we have that r(n) ³ n²/10 for n ³ 7.

: Now for the reverse inequality. If 2 £ r £ n/2, the remainders upon division by r do not exceed r - 1, while if n/2 < r £ n, we know exactly what the remainders are. Thus

>From these we deduce that r(n) < n²/4 for all n.

Problem 8.

8.: First solution. The problem can be solved in three weighings when the weights are known and in four weighings when the weights are not known. Let the two samples be { A, B, C } and { P, Q, R } and let w_i be the result of the ith weighing.

: (a) Weigh A and P. If w₁ = 2a, then both coins are counterfeit. Otherwise, weigh B and Q next. If w₁ = w₂ = 2b, then C and R are counterfeit. If w₁ = w₂ = a + b, then C and R must be genuine; weigh A to determine its status; if, for example, A is genuine, then B and P are counterfeit. Finally, supppose, say, that w₁ = 2b and w₂ = a + b, then A and P are genuine and one of B and Q is counterfeit, as is one of C and R. A third weighing to discover the status of B will allow one to deduce the status of the remaining coins.

: The problem cannot be solved in two weighings. There is no point in putting all coins from either lot on the scale as this would provide no new information. Since learning the weight of one coin in a sample is equivalent to learning the total weight of the other two, the effective choices for a weighing are: (1) one coin (say A); (2) one coin from each sample (say A and P); (3) one coin from one sample and two from the other (say A, P, Q).

: Suppose that a single coin A was selected for the first weighing and found to be genuine. Then the second weighing would identify the two counterfeit coins only if they were the only two coins either put on the scale or left off the scale. But ensuring the first possibility would require one coin from each sample on the second weighing while ensuring the second would require three coins on the scale, and these two options are inconsistent. Thus, the determination cannot be made sure in two weighings.

: Suppose that one coin from each sample was taken on the first weighing and at least one found to be genuine. If both were found to be genuine, then the second weighing would have to involve at least one coin from each pile. If the second weighing revealed all genuine or two counterfeit coins, then this would settle the matter only if it involved exactly one coin from each pile. But in this case, if the second weighing resulted in one genuine and one coutnerfeit coin, we would not know when coin in either weighing was counterfeit.

: Finally, suppose A, P and Q were weighed to begin with. If all were genuine, then the second weighing would identify the two remaining counterfeit coins only if they were the only two coins on the scale, and we cannot guarantee this in advance.

: (b) First solution. On the first three weighings, weigh the sets { A, P }, { B, Q } and { C, R }. Two of the three weights must be the same, either 2b, 2b, 2a in some order or a+b, a+b, 2b in some order. Suppose, wolog, that w₁ = w₂. For the fourth and final weighing, select A and obtain the weight w₄. If w₄ = w₁/2 = w₂/2, then A, P, B and Q weigh the same and C and R are counterfeit. If w₄ = w₃/2, then A is genuine and B and P are counterfeit. If w₄ has neither of these values, then A is counterfeit along with Q.

: Three weighings do not suffice. A single weighing gives absolutely no information about the character of the coins since we do not know a and b. Essentially, all we find out is the average weight of a coin. Suppose the average weight of a coin in the first weighing is p and the average weight of a coin in the second weighing is q. Either p = q or p ¹ q. There are nine possibilities for the pair of counterfeit coins, and one of the outcomes from the first two weighings must leave at least five of them extant. If r is the average weighing of the coins in the third weighing, there are at most three outcomes (whether r is equal to none, one or both of p and q), and this does not suffice to distinguish among the five possibilities.

: Comment: Another suggested possibility is to weigh a fixed coin of one pile with each of the coins in the second pile for the first three weighings. This will identify the counterfeit coin in the second pile. Now take it from there.

: (b) Second solution. For the first two weighings, weigh A and B individually. If A and B weigh the same, then we know that C is counterfeit and what the weight of a genuine coin is. For the third and fourth weighings, weigh P and Q, and the situation can now be determined. Suppose that the weights are different, i.e. w₁ ¹ w₂. We know that C must be genuine. For the third weighing, weigh C and P. If the result is 2w₁, then P must be genuine and we know that the counterfeit coin must weigh w₂; now weigh Q to determine its status, and so deduce the status of R. If the weight is 2w₂, then we can conduct a similar analysis. If the result is w₁ + w₂, then P must be counterfeit (since C is genuine). Now weigh Q to find the weight of a genuine coin and so determine which of A and B is genuine.

Problem 9.

9.: First solution. See Figure 9.1. Represent the points in the problem as complex numbers. Let I, J, K, L be the respective midpoints of AB, BC, CD, DA. Then, by the similarity of the triangular ``ears'', there is a real number U for which

E - I = iU(A - B), F - J = iU(B - C), G - K = iU(C - D), H - L = iU(D - A)

(I + K + iU(A - B + C - D)) =

(A + B + C + D + 2iU(A - B + C - D))

N =

(H + F) =

(A + B + C + D + 2iU(B - C + D - A)) .

Also P = ¹/₂(A + C) and Q = ¹/₂(B + D). It follows that M + N = ¹/₂(A + B + C + D) = P + Q. Also M - N = iU(A - B + C - D) = i2U(P - Q), so that MN and PQ right bisect each other and so MPNQ is a rhombus.

9.: Second solution. [K. Choi] See Figures 9.1 and 9.2. Let I, J, K, L be the respective midpoints of AB, BC, CD, DA respectively. Since IJKL is a parallelogram, its diagonals IK and JL bisect each other in a point O. Since LQ and PJ are both parallel to AB and LP and QJ are both parallel to CD, LQJP is a parallelogram and so JL and PQ bisect each other in the point O. Now OE = OI +IE and OG = OK +KG = IO +KG, whence OM = ¹/₂(OE +OG) = ¹/₂(IE+KG). Similarly, ON = ¹/₂(OF +OH) = ¹/₂(JF +LH). Hence OM +ON = ¹/₂(IE +KG+JF +LH).

: But a certain rotation and a dilation takes IE to BA, JF to CB, etc, and we deduce that OM +ON = 0 and PMQN is a parallelogram. Further, QL = ¹/₂BA and LP = ¹/₂DC whence QP = ¹/₄ (BA +DC) and NM = OM-ON = 2OM = IE+KG. Since BA^IE and DC^KG (with the perpendicularity implemented by the same transformation), we have that QP ^NM and so PMQN is a rhombus.

Problem 10.

10.: First solution. Since AP bisects ÐCAB, then BP:PC = BA:CA, the latter ratio being constant. Thus, the locus of P is the image of the locus of C with respect to a dilatation with centre B and factor |BP |/|BC |. Since |BP |:|BC | = |AB |: (|CA |+|AB |), observe that this circle passes through A, with P coinciding with A when CAB is collinear.

10.: Second solution. [J. Lei] Select O so that AO:OB = AC:AB. Then CP:PB = AC:AB = AO:OB ÞAC || OP Þ ÐAPO = ÐCAP = ÐPAOÞ AO = OP so that P moves on a circle of radius |AO | and centre O.

: Conversely, let P be a point on the circle of radius |AO | and centre O. Produce BP to C so that CP:PB = AO:OB, Then CA || PO and CA : AB = PO : OB = CP : PB, so that AP bisects angle CAB and AC is of constant length. The point C must be on the original circle. For, if not, a point C¢ on the circle with ÐC¢AB = ÐCAB would give a point P¢ ¹ P and yield a contradiction.

10.: Third solution. Let B be located at (0, 0) and A at (1, 0) in the cartesian plane. Let C move on the circle of equation (x - 1)² + y² = r², so that the coordinates of C have the form (1 + rcosq, rsinq) (0 £ q < 2p). The bisector of ÐBAC passes through the point

and so has the equation

where t = tan[(q)/2]. The equation of BC is

since sinq = 2t(1 + t²)^-1 and cosq = (1 - t²)(1 + t²)^-1. The intersection point of the two lines is

1+r

which tracks around the circle of equation

1+r

1+r

which passes through (1, 0), the centre of the circle upon which C moves.

10.: Fourth solution. See Figure 10.4. Since b² = d² + s² - 2ds cosq and c² = r² + s² - 2rscosq,

d²

r²

b²

c²

d² + s² - 2ds cosq

r² + s² - 2rscosq

from which s(r - d)(rs + ds - 2rdcosq) = 0. Hence, either r = d or (r+d)s = 2rdcosq.

: Suppose that r = d. Then B lies on the circle and AP right bisects BC. Hence ÐAPB = 90^° and so P tracks a circle with diameter AB.

: Suppose that (r + d)s = 2rdcosq. Then (1/s)cosq = ¹/₂((1/r) + (1/d)), a constant. This means that the segment AQ on AP produced with |AP ||AQ | = 1 has constant perpendicular projection on AB, and so Q tracks along a line perpendicular to AB. Since P is the image of Q with respect to inversion in a circle with centre A and radius 1, P must move on a circle that passes through A. (Cf. Problem 5.)

Problem 11.

11.: First solution. Since triangles ADE and ABE are similar,

since the area of triangle ABC is equal to both rs and ¹/₂acsinB, where 2s = a + b + c. Thus, we have to show that

a²

But this follows from

a²

11.: Second solution. See Figure 11.2. Let u, v, w be the respective lengths of the tangents from A, B, C to the incircle. Since DH = DF and EK = EF, the perimeter of triangle ADE is 2u. The perimeter of triangle ABC is 2(u + v + w). Since triangles ADE and ABC are similar,

[u² + v² + w² - 2uv - 2uw + 2vw]

u + v + w

(u - v - w)² ³ 0 ,

the result follows.

11.: Third solution. Let r be the inradius and let 2a, 2b and 2g be the respective angles at A, B and C. Then

DE = r (tanb+ tang), BC = r (cotb+ cotg) ,

AB + BC + CA = 2r(cota+ cotb+ cotg) = 2r cotacotbcotg .

(The proof of the requisite identity is given below.) Now

tanb+ tang = cota[1 - tanbtang]

and

DE = rcota[1 - tanbtang] .

Let t = tanbtang. Then

8DE £ AB + BC + CA

is equivalent to

4 - 4tanbtang £ cotbcotg

which in turn is equivalent to

4t² - 4t + 1 = (2t - 1)² ³ 0 .

Thus, the result is established once we verify that the product of the cotangents of angles summing to 90^° is equal to the sum of the same cotangents. But, if a+ b+ g = 90^°, then

: Comment. Equality occurs when s = 2a (b + c = 3a) and when tanbtang = 1/2.

Problem 12.

12.: First solution. We first establish the equation when 0 £ x, y £ 1. Consider a biased coin, which when tossed, returns heads with a probability of x and tails with a probability of y. The coin is tossed repeatedly until either heads appears n+1 times or tails appears n+1 times. In order to achieve this, the coin has to be tossed at least n+1 times but no more than 2n+1 times.

: Suppose that 0 £ k £ n. The probability that the (n+1)th head appears on the (n+k+1)th toss is ((n+k) || k)xⁿ⁺¹y^k since the k positions for tails is one of the first n+k tosses. Similarly, the (n+1)th tail appears on the (n+k+1)th toss with probability ((n+k) || k)yⁿ⁺¹x^k. Since this covers all eventualities, we have that

1 = xⁿ⁺¹

n+k
k

y^k+ yⁿ⁺¹

n+k
k

: Replace y by 1 - x in the equation. This is a polynomial equation in x of degree at most n+1 with infinitely many solutions (any x with 0 £ x £ 1), and so it is an identity. Thus the equation holds for each complex x.

12.: Second solution.

= (x+y)ⁿ⁺¹ =

n+1
k

= xⁿ⁺¹ +

n+1
k

+ yⁿ⁺¹

= xⁿ⁺¹ +

n+1
1

xⁿ⁺¹ y+

n+1
k

n+1
n

xyⁿ⁺¹ + yⁿ⁺¹

xⁿ⁺¹

n+k
k

n+2
k

yⁿ⁺¹

n+k
k

= xⁿ⁺¹

n+k
k

n+2
k

x^n+3-ky^k + yⁿ⁺¹

n+k
k

= xⁿ⁺¹

n+k
k

n+3
k

x^{n+3 - k}y^k (x + y)

+ yⁿ⁺¹

n+k
k

= ¼ = xⁿ⁺¹

n+k
k

x^n+r+1-ky^k(x+y) + yⁿ⁺¹

n+k
k

= xⁿ⁺¹

n+k
k

x^n+r+2-ky^k + yⁿ⁺¹

n+k
k

= xⁿ⁺¹

n+k
k

x^n+r+2-ky^k(x + y) +yⁿ⁺¹

n+k
k

= ¼ = xⁿ⁺¹

n+k
k

2n
n

xⁿyⁿ(x + y) + yⁿ⁺¹

n+k
k

= xⁿ⁺¹

n+k
k

y^k + yⁿ⁺¹

n+k
k

12.: Third solution. [D. Pritchard] Let p_n (x, y) denote the polynomial on the left side. Since p₁ (x, y) = 1, it suffices to show that p_n+1(x, y) = p_n (x, y) for each positive integer n. But