Solutions and comments

Solutions and comments

Let S=1!2!3!99!100! (the product of the first 100 factorials). Prove that there exists an integer k for which 1k100 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= Πj=1 50[(2j-1)!]2 [2j]= 250 50! [ Πj=1 50(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 k100. The prime 47 does not divide k! for k46 and divides 50! to the first power. Since S/50! is a square, it evidently divides S to an odd power. So k47 in order to get a quotient divisible by 47 to an even power. The prime 53 divides each k! for k53 to the first power and divides S/50!, and so S to an even power. Hence, k52.
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 47k49. 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 pm100, so that p divides S to the even power 100-(p-1)=101-p. From this, it follows that if 53k, p must divide S/k! to an odd power.
On the other hand, the prime 47 divides each m! with 47m93 to the first power, and each m! with 94m100 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


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·450)( 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 53k100. 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 k46. 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 k100.

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 11+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.

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 xS 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- 1im f(i)+ 1i<jm f(i,j)- 1i<j<lm 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 (1in). 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:

i=0 n(-1)i ( n i ) im ={ 0 (0mn-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 + bm im ++ b1 i+ 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 n3. Suppose that it holds when m is replaced by k for 0kmn-2. Then

i=0 n(-1)i ( n i ) im+1 = i=1 n(-1)i ( n i )i(i-1)(i-m)- k=0 m bk i=0 n(-1)i ( n i ) ik = i=m+1 n(-1)i ( n i )i(i-1)(i-m)-0 = i=m+1 n(-1)i n!i! i!(n-i)!(i-m-1)! = j=0 n-m-1(-1)m+1+j n! (n-m-1-j)!j! = j=0 n-m-1(-1)m+1 (-1)j n(n-1)(n-m)[(n-m-1)!] (n-m-1-j)!j! =(-1)m+1 n(n-1)(n-m) j=0 n-m-1(-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=0 n(-1)i ( n i ) im =0 for 0mn-1. Now consider the case m=n:

i=1 n(-1)i ( n i ) in = i=1 n(-1)i ( n i )i(i-1)(i-n+1)- k=0 n-1 bk i=0 n(-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=1 n(-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 = i=0 n(-1)i ( n i )(n-i+k)n = i=0 n(-1)i ( n i ) j=0 n( n j )(n-i)j kn-j = i=0 n j=0 n(-1)i ( n i )( n j )(n-i)j kn-j = j=0 n( n j ) kn-j i=0 n(-1)i ( n i )(n-i)j = j=0 n( n j ) kn-j i=0 n(-1)i ( n n-i )(n-i)j = j=0 n( n j ) kn-j i=0 n(-1)n (-1)i ( n i ) ij .

When 0jn-1, the sum i=0 n(-1)i ( n n-i )(n-i)j = i=0 n(-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 ) k0 n!=n! as desired.
Solution 3. Let m=n+k, so that mn, 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 [ j=0 n(-1)i ( n i ) ]-( n 1 ) mn-1 [ i=1 n(-1)i i( n i ) ]+( n 2 ) mn-2 [ i=1 n(-1)i i2 ( n i ) ]+ +(-1)n ( n n ) [ i=1 n(-1)i in ( n i ) ].


f0 (x)=(1-x)n = i=0 n(-1)i ( n i ) xi

and let

fk (x)=x Dfk-1 (x)

for k1, 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)= i=0 n(-1)i ik ( n i ) xi

so that R= k=0 n(-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)j n(n-1)(n-j+1) xj-1 (1-x)n-j -(-1)j n(n-1)(n-j+1)(n-j) xj (1-x)n-j-1 -(n-j+1)(1-x)n-j gj (x)+(1-x)n-j+1 gj '(x),


fj+1 (x) =(-1)j+1 n( n1 )(n-j) xj (1-x)n-(j+1) +(1-x)n-(j+1)+1 [(-1)j n(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 1kn-1, fk (1)=0 while fn (1)=(-1)n n!. Hence R=(-1)n fn (1)=n!.

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 ΔAME be u and x respectively, of ΔMFB be v and y respectively, and of ΔCMD 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;


a3 =uvwand3 a2 =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 ABBCCA. Since ABBC, AEB 90ˆ , and so AMMC. Thus xp. Similarly, yp and pz.
Consider triangles BMD and AME. We have BDAE, BMAM, ME= 1 2 BM and MD= 1 2 AM. Therefore

p-x=(BD+MD+BM)-(AE+ME+AM)=(BD-AE)+ 1 2 (BM-AM)0

and so px. Since also xp, we have that p=x. But this implies that AM=MC, so that MEAC 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.

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 \frakR be a rotation of 60ˆ about T that takes the ray TU to TV. Then, if \frakR transforms QQ' and PP', then Q' lies on TV and the line Q'P' makes an angle of 60ˆ with QP. Because of the rotation, P'TP= 60ˆ and TP'=TP, whence TP'P is an equilateral triangle.
Since Q'TP=TPP'= 60ˆ , TVP'P. Let \frakT 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 PP, QQ' and RR'. 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 SRXY; observe that ΔRST 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 ΔPRS), 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 ΔRSQΔRTM and RQ=RM. (ASA) Since QRM= 60ˆ , ΔRQM 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=2QR'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 ΔPWQ is equilateral. Hence PW=PQ=PR.
Suppose WR. 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ˆ , ΔPQN is equilateral so that PN=PQ. Suppose, if possible, that RN. Then N and R are two points on TV equidistant from P. Since PNT<PNQ= 60ˆ and ΔPNR 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 SRXY 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 ΔSRQ=ΔTRZ (ASA).
Hence RZ=RQΔRQZ 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.]

PQ2 -QR2 =(u-w)2 +3 u2 -(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 ΔPQR is equilateral. Therefore QPR= 60ˆ .
Solution 11. [J.Y. Jin] Let \frakC be the circumcircle of ΔPQR. If T lies strictly inside \frakC, then 60ˆ =QTR>QPR and 60ˆ =PTR>PQR=PRQ. Thus, all three angle of ΔPQR would be less than 60ˆ , which is not possible. Similarly, if T lies strictly outside \frakC, then 60ˆ =QTR<QPR and 60ˆ =PTR<PQR=PRQ, so that all three angles of ΔPQR would exceed 60ˆ , again not possible. Thus T must be on \frakC, whence QPR=QTR= 60ˆ .
Solution 12. [C. Lau] By the Sine Law,

sinTQP TP = sin 120ˆ PQ = sin 60ˆ 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 PQPR, 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.

(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 EPAC and that Q is a point on AE produced for which CQAE. 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=α. Then PEC= 90ˆ -α. Because EPQC is concyclic, PQC=PEC= 90ˆ -α. Because ABCQD is concyclic, BQC=BDC=α. The points B, P, Q are collinear &lrArr;BQC=PQC&lrArr;α= 90ˆ -α&lrArr;α= 45ˆ &lrArr;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 ΔPBC~ΔEAC (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


&lrArr;ECA=ACB= 45ˆ &lrArr;ABCDisasquare.

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 ERAC, 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 ΔADE~ΔFBC, AD:DE=BF:BC, so that BF=1/a and FC=1+ a2 /a. Since ΔADE~ΔCQE, 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 ΔECP 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 0t1. 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 ).