CMS/SMC
Société mathématique du Canada
www.smc.math.ca
Société mathématique du Canada
  location: 
       

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?)
Solution 1. Note that, for each positive integer j, (2j-1)!(2j)! = [(2j-1)!]2 ·2j. Hence


S = 50

j=1 
[(2j-1)!]2 [2j] = 25050!

50

j=1 
(2j-1)!

2

 
 ,
from which we see that k = 50 is the required number.

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 22u is the highest power of 2 that divides S/50! and that 2v is the highest power of 2 that divides 50!; then 22u+v is the highest power of 2 that divides S. The highest power of 2 that divides 48! and 49! is 2v-1 and the highest power of 2 that divides 46! and 47! is 2v-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


100/2 + 100/4 + 100/8 + 100/16 + 100/32 + 100/64 = 50 + 25 + 12 + 6 + 3 + 1 = 97 .
Hence, 2 divides S to an odd power. So we need to divide S by k! which 2 divides to an odd power to get a perfect square quotient. This reduces the possibilities for k to 50 or 51. Since


S = 299·398·497 992·100 = (2·4 50)(249·349 ·448 99)2 = 50! ·250( )2 ,
S/50! is a square, and so S/51! = (S/50!)(51) is not a square. The result follows.

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.
Solution. Any prime divisor of n! + 1 must be larger than n, since all primes not exceeding n divide n!. Suppose, if possible, the result fails. Then, the only prime that can divide n! + 1 is n+1, so that, for some positive integer r and nonnegative integer K,


n! + 1 = (n + 1)r = 1 + rn + Kn2 .
This happens, for example, when n = 1, 2, 4: 1! + 1 = 2, 2! + 1 = 3, 4! + 1 = 52. Note, however, that the desired result does hold for n = 3: 3! + 1 = 7.

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, 2n, 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 n2. Suppose, if possible, the result fails, so that n! + 1 = 1 + rn + Kn2, and 1 1 + rn (mod n2). Thus, r must be divisible by n, and, since it is positive, must exceed n. Hence


(n+1)r (n+1)n > (n+1)n(n-1)1 > n! + 1 ,
a contradiction. The desired result follows.



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 .
Solution 1. Recall the Principle of Inclusion-Exclusion: Let S be a set of n objects, and let P1, P2, , Pm be m properties such that, for each object x S and each property Pi, either x has the property Pi or x does not have the property Pi. Let f(i, j, , k) denote the number of elements of S each of which has properties Pi, Pj, , Pk (and possibly others as well). Then the number of elements of S each having none of the properties P1, P2, , Pm is


n -

1 i m 
f(i)+

1 i < j m 
f(i, j)-

1 i < j < l m 
f(i, j, l)+ + (-1)m f(1, 2, , m)  .

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 Pi iff its fails to include at least i of the numbers 1, 2, , n (1 i n). The number of selections with property Pi is the product of (n || i), the number of ways of choosing the i numbers not included and (n+k-i)n, 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:


n

i=0 
(-1)i

n
i


im =

0
(0 m n-1)
(-1)n n!
(m = n) .
We use the convention that 00 = 1. To prove this, note first that i(i-1)(i-m) = im+1 + bmim+ + b1i + b0 for some integers bi. We use an induction argument on m. The result holds for each positive n and for m = 0, as the sum is the expansion of (1 - 1)n. It also holds for n = 1, 2 and all relevant m. Fix n 3. Suppose that it holds when m is replaced by k for 0 k m n-2. Then


n

i=0 
(-1)i

n
i


im+1
= n

i=1 
(-1)i

n
i


i(i-1)(i-m) - m

k=0 
bk n

i=0 
(-1)i

n
i


ik
= n

i=m+1 
(-1)i

n
i


i(i-1)(i-m) - 0
= n

i=m+1 
(-1)i n!i!
i!(n-i)!(i-m-1)!
= n-m-1

j=0 
(-1)m+1+j n!
(n-m-1-j)!j!
= n-m-1

j=0 
(-1)m+1(-1)j n(n-1)(n-m)[(n-m-1)!]
(n-m-1-j)!j!
= (-1)m+1n(n-1)(n-m) n-m-1

j=0 
(-1)j

n-m-1
j


= 0 .
(Note that the j=0 term is 1, which is consistent with the 00 = 1 convention mentioned earlier.) So i=0n (-1)i (n || i)im = 0 for 0 m n-1. Now consider the case m = n:


n

i=1 
(-1)i

n
i


in = n

i=1 
(-1)i

n
i


i(i-1)(i-n+1) - n-1

k=0 
bk n

i=0 
(-1)i

n
i


ik .
Every term in the first sum vanishes except the nth and each term of the second sum vanishes. Hence i=1n(-1)i (n || i) in = (-1)n n!.

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


(n+k)n
-

n
1


(n+k-1)n +

n
2


(n+k-2)n - + (-1)n

n
n


(n+k-n)n
= n

i=0 
(-1)i

n
i


(n-i+k)n = n

i=0 
(-1)i

n
i


n

j=0 


n
j


(n-i)j kn-j
= n

i=0 
n

j=0 
(-1)i

n
i




n
j


(n-i)j kn-j = n

j=0 


n
j


kn-j n

i=0 
(-1)i

n
i


(n-i)j
= n

j=0 


n
j


kn-j n

i=0 
(-1)i

n
n-i


(n-i)j
= n

j=0 


n
j


kn-j n

i=0 
(-1)n(-1)i

n
i


ij .
When 0 j n-1, the sum i=0n (-1)i (n || (n-i))(n-i)j = i=0n (-1)n-i(n || i)ij vanishes, while, when j = n, it assunes the value n!. Thus, the right side of the given equation is equal to (n || n)k0n! = n! as desired.

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


R
= mn -

n
1


(m-1)n+

n
2


(m - 2)n - + (-1)i

n
i


(m - i)n + + (-1)n

n
n


(m - n)n
= mm

n

j=0 
(-1)i

n
i




-

n
1


mn-1

n

i=1 
(-1)i i

n
i




+

n
2


mn-2

n

i=1 
(-1)i i2

n
i




+
             + (-1)n

n
n




n

i=1 
(-1)i in

n
i




 .

Let


f0(x) = (1 - x)n = n

i=0 
(-1)i

n
i


xi
and let


fk(x) = x Dfk-1(x)
for k 1, where Df denotes the derivative of a function f. Observe that, from the closed expression for f0(x), we can establish by induction that


fk(x) = n

i=0 
(-1)i ik

n
i


xi
so that R = k=0n (-1)k (n || k)mn-k fk (1).

By induction, we establish that


fk (x) = (-1)k n(n-1)(n - k + 1)xk (1 - x)n-k+ (1 - x)n-k+1 gk (x)
for some polynomial gk(x). This is true for k = 1 with g1(x) = 0. Suppose if holds for k = j. Then


fj(x)
= (-1)jn(n-1)(n-j+1)xj-1(1 - x)n-j- (-1)jn(n-1)(n-j+1)(n-j)xj(1-x)n-j-1
             - (n-j+1)(1-x)n-jgj(x) + (1 - x)n-j+1gj(x) ,
whence


fj+1(x)
= (-1)j+1n(n1)(n-j)xj(1-x)n-(j+1)+ (1-x)n-(j+1)+1[(-1)jn(n-1)(n-j+1)xj
             - (n-j+1)xgk(x) + x(1-x)gj(x)]
and we obtain the desired representation by induction. Then for 1 k n-1, fk(1) = 0 while fn(1) = (-1)nn!. Hence R = (-1)n fn(1) = n!.



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.
Solution. [L. Lessard] Let the common area of the triangles BMD, CME and AMF be a and let their common perimeter be p. Let the area and perimeter of DAME be u and x respectively, of DMFB be v and y respectively, and of DCMD be w and z respectively.

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


AF
FB
= a
v
= 2a + u
v + a + w
= a+u
a+w
 ,


BD
DC
= a
w
= 2a + v
u + a + w
= a + v
a + u
 ,


CE
EA
= a
u
= 2a + w
u + a + v
= a + w
a + v
 .
>From these three sets of equations, we deduce that


a3
uvw
= 1 ;


a2 + (w - u)a - uv = 0 ,


a2 + (u - w)a - vw = 0 ,


a2 + (v - u)a - uw = 0 ;
whence


a3 = uvw          and           3a2 = uv + vw + uw .
This means that uv, vw, uw are three positive numbers whose geometric and arithmetic means are both equal to a2. Hence a2 = uv = vw = uw, so that u = v = w = a. It follows that AF = FB, BD = DC, CE = EA, so that AD, BE and CF are medians and M is the centroid.

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 = 1/2BM and MD = 1/2AM. Therefore


p - x = (BD + MD + BM) - (AE + ME + AM) = (BD - AE) + 1
2
(BM - AM) 0
and so p x. Since also x p, we have that p = x. But this implies that AM = MC, so that ME ^AC and AB = BC. Since BE is now an axis of a reflection which interchanges A and C, as well as F and D, it follows that p = z and p = y as well. Thus, AB = AC and AC = BC. Thus, the triangle is equilateral.



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.
Solution 1. Let R be a rotation of 60 about T that takes the ray TU to TV. Then, if R transforms Q Q and P P, then Q lies on TV and the line QP makes an angle of 60 with QP. Because of the rotation, PTP = 60 and TP = TP, whence TPP is an equilateral triangle.

Since QTP = TPP = 60, TV || PP. Let T be the translation that takes P to P. It takes Q to a point Q on the ray TV, and PQ = PQ = 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 PQR are congruent and isosceles, so that TQP = TQP = 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, QRR = TRR = 30. Since Q, R, Q, R, lie on a circle with centre P, QPR = 2QRR = 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.]


|PQ |2 - |QR |2
= (u - w)2 + 3u2 - (u - v)2 - 3(u + v)2
= w2 - 2uw - 4v(u + v) = w2 - 2uw - 2vw
= w2 - 2(u + v)w = 0 .
Hence PQ = QR = PR and DPQR is equilateral. Therefore QPR = 60.

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,


sinTQP
|TP |
= sin120
|PQ |
= sin60
|PR |
= sinTRP
|TP |
 ,
whence sinTQP = sinTRP. Since QTP, in triangle QTP is obtuse, TQP is acute.

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 1. Let ABCD be a rectangle, and let E, P, Q be determined as in the problem. Suppose that ACD = BDC = a. Then PEC = 90 - a. Because EPQC is concyclic, PQC = PEC = 90 - a. Because ABCQD is concyclic, BQC = BDC = a. The points B, P, Q are collinear BQC = PQC a = 90 - a a = 45 ABCD is a square.

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


PBC = QBC PAF = PAE AC   right  bisects   EF


ECA = ACB = 45 ABCD   is  a  square .

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


AB
BF
· FQ
QC
· CP
PA
= -1 .
Let the side length of the square be 1 and the length of DE be a. Then |AB | = 1. Since DADE ~ DFBC, AD : DE = BF : BC, so that |BF | = 1/a and |FC | = [(1+a2)]/a. Since DADE ~ DCQE, CQ:EC = AD:EA, so that |CQ | = (1 - a)/[(1 + a2)]. Hence


|FQ |
|CQ |
= 1 + |FC |
|CQ |
= 1 + 1 + a2
a(1 - a)
= 1 + a
a(1 - a)
 .
Since DECP is right isosceles, |CP | = (1 - a)/2 and |PA | = 2 - |CP | = (1 + a)/2. Hence |CP |/|PA | = (1 - a)/(1 + a). Multiplying the three ratios together and taking account of the directed segments gives the product -1 and yields the result.

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/2, t/2).

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


Q ~

2-t
1 + (1 - t)2
, t
1 + (1 - t)2)


 .
It can now be checked that the slope of each of BQ and BP is t(2 - t)-1, which yields the result.

(b) The result fails if A ~ (0, 2), B ~ (0, 0), C ~ (1, 0), D ~ (1, 2). If E ~ (1, 1), then P ~ (3/5, 4/5) and Q ~ (3/2, 1/2).


© Société mathématique du Canada, 2014 : http://www.smc.math.ca/