 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(n1) for infinitely many positive integers n.
 (b) Prove that n^{2}/10 < r(n) < n^{2}/4 for each integer n ³ 7.
 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.
 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?
 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.
 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.
 12.
 Suppose that n is a positive integer and that x + y = 1. Prove that

 7.
 First solution. (a) Suppose that n1 = iq_{i} + r_{i} with 0 £ r_{i} < i for 1 £ i £ n1. 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


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


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


 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 £ k1. 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

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


 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


 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_{1} = 2a, then both coins are counterfeit. Otherwise, weigh B and Q next. If w_{1} = w_{2} = 2b, then C and R are counterfeit. If w_{1} = w_{2} = 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_{1} = 2b and w_{2} = 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_{1} = w_{2}. For the fourth and final weighing, select A and obtain the weight w_{4}. If w_{4} = w_{1}/2 = w_{2}/2, then A, P, B and Q weigh the same and C and R are counterfeit. If w_{4} = w_{3}/2, then A is genuine and B and P are counterfeit. If w_{4} 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_{1} ¹ w_{2}. We know that C must be genuine. For the third weighing, weigh C and P. If the result is 2w_{1}, then P must be genuine and we know that the counterfeit coin must weigh w_{2}; now weigh Q to determine its status, and so deduce the status of R. If the weight is 2w_{2}, then we can conduct a similar analysis. If the result is w_{1} + w_{2}, 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.
 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




 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 = ^{1}/_{2}(OE +OG) = ^{1}/_{2}(IE+KG). Similarly, ON = ^{1}/_{2}(OF +OH) = ^{1}/_{2}(JF +LH). Hence OM +ON = ^{1}/_{2}(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 = ^{1}/_{2}BA
and LP = ^{1}/_{2}DC
whence QP = ^{1}/_{4} (BA +DC)
and NM = OMON = 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.
 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)^{2} + y^{2} = r^{2}, so that the coordinates of C have the form (1 + rcosq, rsinq) (0 £ q < 2p). The bisector of ÐBAC passes through the point





 10.
 Fourth solution. See Figure 10.4. Since b^{2} = d^{2} + s^{2}  2ds cosq and c^{2} = r^{2} + s^{2}  2rscosq,

 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}/_{2}((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.)
 11.
 First solution. Since triangles ADE and ABE are similar,



 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,



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









 Comment. Equality occurs when s = 2a (b + c = 3a) and when tanbtang = 1/2.
 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^{n+1}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^{n+1}x^{k}. Since this covers all eventualities, we have that

 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.

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

 12.
 Fourth solution. [D. Brox] Let u_{n} (x, y) = x^{n+1}å_{k = 0}^{n} ((n+k)  k)y^{k}. Then, for each positive integer n exceeding 1,




 12.
 Fifth solution. [D. Arthur] Let f(n) = å_{k = 0}^{n} ((n+k)  k)x^{k} y^{k} [x^{nk+1} + y^{nk+1} ] and



