Solutions and comments

61.

Let S = 1!2!3!¼99!100! (the product of the first 100 factorials). Prove that there exists an integer k for which 1 £ k £ 100 and S/k! is a perfect square. Is k unique? (Optional: Is it possible to find such a number k that exceeds 100?)

We show that k = 50 is the only possibility. First, k cannot exceed 100, for otherwise 101! would be a factor of k! but not S, and so S/k! would not even be an integer. Let k £ 100. The prime 47 does not divide k! for k £ 46 and divides 50! to the first power. Since S/50! is a square, it evidently divides S to an odd power. So k ³ 47 in order to get a quotient divisible by 47 to an even power. The prime 53 divides each k! for k ³ 53 to the first power and divides S/50!, and so S to an even power. Hence, k £ 52.

The prime 17 divides 50! and S/50!, and hence S to an even power, but it divides each of 51! and 52! to the third power. So we cannot have k = 51 or 52. Finally, look at the prime 2. Suppose that 2^2u is the highest power of 2 that divides S/50! and that 2^v is the highest power of 2 that divides 50!; then 2^2u+v is the highest power of 2 that divides S. The highest power of 2 that divides 48! and 49! is 2^v-1 and the highest power of 2 that divides 46! and 47! is 2^v-5. >From this, we deduce that 2 divides S/k! to an odd power when 47 £ k £ 49. The desired uniqueness of k follows.

Solution 2. Let p be a prime exceeding 50. Then p divides each of m! to the first power for p £ m £ 100, so that p divides S to the even power 100 - (p - 1) = 101 - p. From this, it follows that if 53 ³ k, p must divide S/k! to an odd power.

On the other hand, the prime 47 divides each m! with 47 £ m £ 93 to the first power, and each m! with 94 £ m £ 100 to the second power, so that it divides S to the power with exponent 54 + 7 = 61. Hence, in order that it divide S/k! to an even power, we must make k one of the numbers 47, ¼, 52.

By an argument, similar to that used in Solution 1, it can be seen that 2 divides any product of the form 1! 2! ¼(2m-1)! to an even power and 100! to the power with exponent

Solution 3. As above, S/(50!) is a square. Suppose that 53 £ k £ 100. Then 53 divides k!/50! to the first power, and so k!/50! cannot be square. Hence S/k! = (S/50!)¸(k!/50!) cannot be square. If k = 51 or 52, then k!/50! is not square, so S/k! cannot be square. Suppose that k £ 46. Then 47 divides 50!/k! to the first power, so that 50!/k! is not square and S/k! = (S/50!)×(50!/k!) cannot be square. If k = 47, 48 or 49, then 50!/k! is not square and so S/k! is not square. Hence S/k! is square if and only if k = 50 when k £ 100.

62.

Let n be a positive integer. Show that, with three exceptions, n! + 1 has at least one prime divisor that exceeds n + 1.

Henceforth, assume that n exceeds 4. If n is prime, then n + 1 is composite, so by our initial comment, all of its prime divisors exceed n + 1. If n is composite and square, then n! is divisible by the four distinct integers 1, n, Ön, 2Ön, while is n is composite and nonsquare with a nontrivial divisor d. then n! is divisible by the four distinct integers 1, d, n/d, n. Thus, n! is divisible by n². Suppose, if possible, the result fails, so that n! + 1 = 1 + rn + Kn², and 1 º 1 + rn (mod n²). Thus, r must be divisible by n, and, since it is positive, must exceed n. Hence

63.

Let n be a positive integer and k a nonnegative integer. Prove that

n! = (n + k)n - æ ç è n 1 ö ÷ ø (n + k - 1)n + æ ç è n 2 ö ÷ ø (n + k - 2)n- ¼± æ ç è n n ö ÷ ø kn .

We apply this to the problem at hand. Note that an ordered selection of n numbers selected from among 1, 2, ¼, n+k is a permutation of { 1, 2, ¼, n } if and only if it is constrained to contain each of the numbers 1, 2, ¼, n. Let S be the set of all ordered selections, and we say that a selection has property P_i iff its fails to include at least i of the numbers 1, 2, ¼, n (1 £ i £ n). The number of selections with property P_i is the product of (n || i), the number of ways of choosing the i numbers not included and (n+k-i)ⁿ, the number of ways of choosing entries for the n positions from the remaining n+k-1 numbers. The result follows.

Solution 2. We begin with a lemma:

Returning to the problem at hand, we see that the right side of the desired equation is equal to

Solution 3. Let m = n + k, so that m ³ n, and let the right side of the equation be denoted by R. Then

Let

By induction, we establish that

64.

Let M be a point in the interior of triangle ABC, and suppose that D, E, F are respective points on the side BC, CA, AB, which all pass through M. (In technical terms, they are cevians.) Suppose that the areas and the perimeters of the triangles BMD, CME, AMF are equal. Prove that triangle ABC must be equilateral.

By considering pairs of triangles with equal heights, we find that

Wolog, suppose that AB ³ BC ³ CA. Since AB ³ BC, ÐAEB ³ 90^°, and so AM ³ MC. Thus x ³ p. Similarly, y ³ p and p ³ z.

Consider triangles BMD and AME. We have BD ³ AE, BM ³ AM, ME = ¹/₂BM and MD = ¹/₂AM. Therefore

65.

Suppose that XTY is a straight line and that TU and TV are two rays emanating from T for which ÐXTU = ÐUTV = ÐVTY = 60^°. Suppose that P, Q and R are respective points on the rays TY, TU and TV for which PQ = PR. Prove that ÐQPR = 60^°.

Since ÐQ¢TP = ÐTPP¢ = 60^°, TV || P¢P. Let T be the translation that takes P¢ to P. It takes Q¢ to a point Q¢¢ on the ray TV, and PQ¢¢ = P¢Q¢ = PQ. Hence Q¢¢ can be none other than the point R [why?], and the result follows.

Solution 2. The reflection in the line XY takes P ® P, Q ® Q¢ and R ® R¢. Triangles PQR¢ and PQ¢R are congruent and isosceles, so that ÐTQP = ÐTQ¢P = ÐTRP (since PQ¢ = PR). Hence TQRP is a concyclic quadrilateral, whence ÐQPR = ÐQTR = 60^°.

Solution 3. [S. Niu] Let S be a point on TU for which SR || XY; observe that DRST is equilateral. We first show that Q lies between S and T. For, if S were between Q and T, then ÐPSQ would be obtuse and PQ > PS > PR (since ÐPRS > 60^° > ÐPSR in DPRS), a contradiction.

The rotation of 60^° with centre R that takes S onto T takes ray RQ onto a ray through R that intersects TY in M. Consider triangles RSQ and RTM. Since ÐRST = ÐRTM = 60^°, ÐSRQ = 60^° -ÐQRT = ÐTRM and SR = TR, we have that DRSQ º DRTM and RQ = RM. (ASA) Since ÐQRM = 60^°, DRQM is equilateral and RM = RQ. Hence M and P are both equidistant from Q and R, and so at the intersection of TY and the right bisector of QR. Thus, M = P and the result follows.

Solution 4. [H. Pan] Let Q¢ and R¢ be the respective reflections of Q and R with respect to the axis XY. Since ÐRTR¢ = 120^° and TR = TR¢, ÐQR¢R = ÐTR¢R = 30^°. Since Q, R, Q¢, R¢, lie on a circle with centre P, ÐQPR = 2ÐQR¢R = 60^°, as desired.

Solution 5. [R. Barrington Leigh] Let W be a point on TV such that ÐWPQ = 60^° = ÐWTU. [Why does such a point W exist?] Then WQTP is a concyclic quadrilateral so that ÐQWP = 180^° - ÐQTP = 60^° and DPWQ is equilateral. Hence PW = PQ = PR.

Suppose W ¹ R. If R is farther away from T than W, then ÐRPT > ÐWPT > ÐWPQ = 60^° Þ 60^° > ÐTRP = ÐRWP > 60^°, a contradiction. If W is farther away from T than R, then ÐWPT > ÐWPQ = 60^°Þ 60^° > ÐRWP = ÐWRP > 60^°, again a contradiction. So R = W and the result follows.

Solution 6. [M. Holmes] Let the circle through T, P, Q intersect TV in N. Then ÐQNP = 180^° - ÐQTP = 60^°. Since ÐPQN = ÐPTN = 60^°, DPQN is equilateral so that PN = PQ. Suppose, if possible, that R ¹ N. Then N and R are two points on TV equidistant from P. Since ÐPNT < ÐPNQ = 60^° and DPNR is isosceles, we have that ÐPNR < 90^°, so N cannot lie between T and R, and ÐPRN = ÐPNR = ÐPNT < 60^°. Since ÐPTN = 60^°, we conclude that T must lie between R and N, which transgresses the condition of the problem. Hence R and N must coincide and the result follows.

Solution 7. [P. Cheng] Determine S on TU and Z on TY for which SR || XY and ÐQRZ = 60^°. Observe that ÐTSR = ÐSRT = 60^° and SR = RT.

Consider triangles SRQ and TRZ. ÐSRQ = ÐSRT - ÐQRT = ÐQRZ - ÐQRT = ÐTRZ; ÐQSR = 60^° = ÐZTR, so that DSRQ = DTRZ (ASA).

Hence RZ = RQ Þ DRQZ is equilateral Þ RZ = ZQ and ÐRZQ = 60^°. Now, both P and Z lie on the intersection of TY and the right bisector of QR, so they must coincide: P = Z. The result follows.

Solution 8. Let the perpendicular, produced, from Q to XY meet VT, produced, in S. Then ÐXTS = ÐVTY = 60^° = ÐXTU, from which is can be deduced that TX right bisects QS. Hence PS = PQ = PR, so that Q, R, S are all on the same circle with centre P.

Since ÐQTS = 120^°, we have that ÐSQT = ÐQSR = 30^°, so that QR must subtend an angle of 60^° at the centre P of the circle. The desired result follows.

Solution 9. [A.Siu] Let the right bisector of QR meet the circumcircle of TQR on the same side of QR at T in S. Since ÐQSR = ÐQTR = 60^° and QS = QR, ÐSQR = ÐSRQ = 60^°. Hence ÐSTQ = 180^° - ÐSRQ = 120^°. But ÐYTQ = 120^°, so S must lie on TY. It follows that S = P.

Solution 10. Assign coordinates with the origin at T and the x-axis along XY. The the respective coordinates of Q and R have the form (u, -Ö3u) and (v, Ö3v) for some real u and v. Let the coordinates of P be (w, 0). Then PQ = PR yields that w = 2(u + v). [Exercise: work it out.]

Solution 11. [J.Y. Jin] Let C be the circumcircle of DPQR. If T lies strictly inside C, then 60^° = ÐQTR > ÐQPR and 60^° = ÐPTR > ÐPQR = ÐPRQ. Thus, all three angle of DPQR would be less than 60^°, which is not possible. Similarly, if T lies strictly outside C, then 60^° = ÐQTR < ÐQPR and 60^° = ÐPTR < ÐPQR = ÐPRQ, so that all three angles of DPQR would exceed 60^°, again not possible. Thus T must be on C, whence ÐQPR = ÐQTR = 60^°.

Solution 12. [C. Lau] By the Sine Law,

Suppose, if possible, that ÐTRP is obtuse. Then, in triangle TPR, TP would be the longest side, so PR < TP. But in triangle TQP, PQ is the longest side, so PQ > TP, and so PQ ¹ PR, contrary to hypothesis. Hence ÐTRP is acute. Therefore, ÐTQP = ÐTRP. Let PQ and RT intersect in Z. Then, 60^° = ÐQTZ = 180^° - ÐTQP - ÐQZT = 180^° - ÐTRP - ÐRZP = ÐQPR, as desired.

66.

(a) Let ABCD be a square and let E be an arbitrary point on the side CD. Suppose that P is a point on the diagonal AC for which EP ^AC and that Q is a point on AE produced for which CQ ^AE. Prove that B, P, Q are collinear.

(b) Does the result hold if the hypothesis is weakened to require only that ABCD is a rectangle?

Solution 2. (a) EPQC, with a pair of supplementary opposite angles, is concyclic, so that ÐCQP = ÐCEP = 180^°- ÐEPC - ÐECP = 45^°. Since CBAQ is concyclic, ÐCQB = ÐCAB = 45^°. Thus, ÐCQP = ÐCQB so that Q, P, B are collinear.

(b) Suppose that ABCD is a nonquare rectangle. Then taking E = D yields a counterexample.

Solution 3. (a) The circle with diameter AC that passes through the vertices of the square also passes through Q. Hence ÐQBC = ÐQAC. Consider triangles PBC and EAC. Since triangles ABC and EPC are both isosceles right triangles, BC : AC = PC : EC. Also ÐBCA = ÐPCE = 45^°. Hence DPBC ~ DEAC (SAS) so that ÐPBC = ÐEAC = ÐQAC = ÐQBC. It follows that Q, P, B are collinear.

Solution 4. [S. Niu] Let ABCD be a rectangle and let E, P, Q be determined as in the problem. Let EP be produced to meet BC in F. Since ÐABF = ÐAPF, the quadrilateral ABPF is concyclic, so that ÐPBC = ÐPBF = ÐPAF. Since ABCQ is concyclic, ÐQBC = ÐQAC = ÐPAE. Now B, P, Q are collinear

Solution 5. [M. Holmes] (a) Suppose that BQ intersects AC in R. Since ABCQD is concyclic, ÐAQR = ÐAQB = ÐACB = 45^°, so that ÐBQC = 45^°. Since ÐEQR = ÐAQB = ÐECR = 45^°, ERCQ is concyclic, so that ÐERC = 180^° - ÐEQC = 90^°. Hence ER ^AC, so that R = P and the result follows.

Solution 6. [L. Hong] (a) Let QC intersect AB in F. We apply Menelaus' Theorem to triangle AFC: B, P, Q are collinear if and only if

Solution 7. (a) Select coordinates so that A ~ (0, 1), B ~ (0, 0), C ~ (1, 0), D ~ (1, 1) and E ~ (1, t) for some t with 0 £ t £ 1. It is straightforward to verify that P ~ (1 - ^t/₂, ^t/₂).

Since the slope of AE is t - 1, the slope of AQ should be (1 - t)^-1. Since the coordinates of Q have the form (1 + s, s(1 - t)^-1) for some s, it is straightforward to verify that

(b) The result fails if A ~ (0, 2), B ~ (0, 0), C ~ (1, 0), D ~ (1, 2). If E ~ (1, 1), then P ~ (³/₅, ⁴/₅) and Q ~ (³/₂, ¹/₂).