Solutions and comments

A textbook problem has the following form: A man is standing in a line in front of a movie theatre. The fraction x of the line is in front of him, and the fraction y of the line is behind him, where x and y are rational numbers written in lowest terms. How many people are there in the line? Prove that, if the problem has an answer, then that answer must be the least common multiple of the denominators of x and y.
Solution. Let p and q be the denominators of x and y, when written in their lowest terms; each denominator has no positive divisor save 1 in common with the corresponding numerator. Let n be the number of people in line. Since xn and yn are integers, p and q must both divide n, so that n is a multiple of m, the least common multiple of p and q.
1-x-y can be written as a fraction of the form u/m. Since (u/m)n=u(n/m)=1, we must have that u=n/m=1, so that in particular m=n.
Comment. This is quite a difficult question to write up, because you have to put your finger quite precisely on the main issues involved. Many solvers relied on statements that were equally if not more difficult to see than the result of the problem. The point of a solution is to show how a result can be obtained from simpler or more wellknown propositions.

Let n be a positive integer and let x1 , x2 ,, xn be integers for which

x1 2 + x2 2 ++ xn 2 + n3 (2n-1)( x1 + x2 ++ xn )+ n2 .

Show that
(a) x1 , x2 ,, xn are all nonnegative;
(b) x1 + x2 ++ xn +n+1 is not a perfect square.
Solution 1. The inequality can be rewritten as

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

(The line over n-1 is a form of bracket.) Since each summand is positive for integers other than n and n-1, the inequality can hold only if each xi is equal to either n or n-1. Therefore,

n2 +1=n(n-1)+n+1 x1 + x2 ++ xn +n+1 n2 +n+1<(n+1)2 .

Parts (a) and (b) follow easily from this.
Solution 2. [R. Furmaniak] Taking the difference between the right and left sides leads to the equivalent inequality

k=1 n[2 xk -(2n-1)]2 n.

Since each term in the sum is odd, it can only be 1. Therefore 2 xk -(2n-1)=±1, whence xk is equal to n or n-1 for each k. The solution can be concluded as before.
Solution 3. [O. Bormashenko, M. Holmes] The given inequality is equivalent to

i=1 n xi ( xi - 2n-1 ) n2 - n3 .

Observe that, for each i,

xi ( 2n-1 - xi )[ 1 2 (2n-1)]2 = n2 -n+ 1 4 .

This is a consequence of the arithmetic-geometric means inequality when the left side is positive, and obvious when the left side is negative. Since xi is supposed to be an integer, we must have

xi ( 2n-1 - xi ) n2 -n

and equality occurs if and only if xi =n or xi =n-1. (One way to see this is to note that the left side is a quadratic and can take each of its values no more than twice.) Multiplying by -1 yields that

xi ( xi - 2n-1 )n- n2


i=1 n xi ( xi - 2n-1 ) n2 - n3 ,.

with equality if and only if each xi is equal to n or n-1. But because of the given inequality, equality does occur. The solution can now be completed as before.
Solution 4. The given inequality is equivalent to

i=1 n(n- xi )2 i=1 n(n- xi ).             (1)

However, since xi is an integer for each i, (n- xi )2 (n- xi ) with equality if and only if n- xi is equal to 0 or 1. Thus

i=1 n(n- xi )2 i=1 n(n- xi )             (2)

with equality if and only if n- xi =0 or 1 for each i. But (1) and (2) together imply that equality does occur for each i, whence xi is equal to either n or n-1. The solution is completed as before.

Let ABCD be a rectangle and let E be a point in the diagonal BD with DAE= 15ˆ . Let F be a point in AB with EFAB. It is known that EF= 1 2 AB and AD=a. Find the measure of the angle EAC and the length of the segment EC.
Solution. We begin with the observation that tan 15ˆ =2-3. (Exercise: Use either tanθ=(sin2θ)/(1+cos2θ)-1 or tanθ=tan(3θ-2θ) with θ= 15ˆ .) Let a and b be the respective lengths of AD and FE, so that AF=(2-3)b, AB=2b and FB=3b. Then tanFEB=3, so that FEB=ADB= 60ˆ . Hence BE=2b, BD=2a and ED=2(a-b). Since a/2b=cotADB=1/3, 3 a2 =4 b2 .
Since DAC=ADB= 60ˆ and DAE= 15ˆ , it follows that EAC= 45ˆ .
We can determine EC using the law of cosines in ΔDEC. Thus,

EC2 =4 b2 +4(a-b)2 -8(a-b)b3/2 =8 b2 -8ab+4 a2 -4ab3+4 b2 3 =4 b2 (2+3)-4ab(2+3)+4 a2 =3 a2 (2+3)-2 a2 3(2+3)+4 a2 = a2 (4-3),

whence EC=a4-3.
Comment. The length of EC can be found more straightforwardly by introducing an additional point. Produce the line FE to meet CD at G. Then EGC is a right triangle for which EG=a-b and GC=3b. Applying pythagoras theorem yields

EC2 = a2 -2ab+4 b2 = a2 -3 a2 +3 a2 =(4-3) a2 .

Find integers a, b, c such that a0 and the quadratic function f(x)= ax2 +bx+c satisfies


Solution 1. Suppose that f(p)=f(q) with pq. Then a( p2 - q2 )+b(p-q)=0, from which p+q=-b/a. It follows from this (Explain!) that f(x) can take the same value at at most two distinct points. In particular, it is not possible that f(1)=f(2)=f(3). Nor can f(1), f(2), f(3) take three different values. Therefore, two of these take one value and the third a second value.
We make another preliminary observation. Suppose f(p)=f(q)=u, f(r)=v and f(u)=f(v), where p, q, r are different, and also u and v are different. Then, from the first paragraph, we have that p+q=u+v=-b/a.
Suppose, now, that (p,q,r)=(1,2,3) and that f(1)=u. Then

a+b+c =u 4a+2b+c =u 9a+3b+c =3-u

so that 2(5a+2b+c)=f(1)+f(3)=3, which is not possible, since a, b and c are integers.
Suppose that (p,q,r)=(2,3,1). Then we are led to 2(5a+2b+c)=5, again an impossibility.
Suppose that (p,q,r)=(1,3,2) and that f(1)=u. Then

a+b+c =u 9a+3b+c =u 4a+2b+c =4-u

so that 4a+b=0 and 5a+b=2u-4. This leads to the assignment


so that

f(x) =(2u-4)( x2 -4x)+(7u-12) =(2u-4)(x-2)2 -(u-4) =(2u-4)(x-1)(x-3)+u.

It can be checked that f(u) and f(4-u) are equal to 2 u3 -12 u2 +23u-12.
We can get a particular example by taking u=0 to obtain the polynomial f(x)=-4(x-1)(x-3), in which case f(1)=f(3)=0, f(2)=4 and f(0)=f(4)=-12.
Solution 2. Let f(x)= ax2 +bx+c. Then f(1)=a+b+c, f(2)=4a+2b+c and f(3)=9a+3b+c. Then

f(f(2))-f(f(1)) =a[(4a+2b+c)2 -(a+b+c)2 ]+b[(4a+2b+c)-(a+b+c)] =(3a+b)[a(5a+3b+2c)+b] =(3a+b)(5 a2 +3ab+2ac+b)

f(f(3))-f(f(1)) =a[(9a+3b+c)2 -(a+b+c)2 ]+b[(9a+3b+c)-(a+b+c)] =(8a+2b)[a(10a+4b+2c)+b] =2(4a+b)(10 a2 +4ab+2ac+b)

Suppose that f(f(1))=f(f(2))=f(f(3)). If b=-3a, then we must have 0=10 a2 +4ab+2ac+b=10 a2 -12 a2 +2ac-3a, whence c=a+(3/2). In this case, a and c cannot both be integers. However, if b=-4a, then 0=5 a2 +3ab+2ac+b=5 a2 -12 a2 +2ac-4a, whence c=(7a/2)+2. So we can get integer coefficients by taking (a,b,c)=(2t,-8t,7t+2) for some integer t.
Comment. To get a single solution quickly, just try to make f(1)=f(3)=1 and f(2)=3. This leads immediately to f(x)=-(x-2)2 +3=-2 x2 +8x-5.

Let ABCD be a concyclic quadrilateral. Prove that


Solution 1. [O. Bormashenko, P. Cheng] Let the diagonals intersect in M and assign the lengths: AB=a, BC=b, CD=c, DA=d, AM=r. BM=p, CM=s, DM=q. Since ABD=ACD and BAC=BDC, triangles MDC and MAB are similar, so that, for some k, q=kr, s=kp, c=ka. Wolog, we may assume that k1. Note that in triangle MAB, we have that p<r+a and r<p+a, whence -a<p-r<a or p-r<a.

AC-BD =(r+s)-(p+q)=(k-1)p-r (k-1)a=c-a=AB-CD.

Solution 2. Let the diagonals intersect in M and assign the lengths: AB=a, BC=b, CD=c, DA=d, AM=r. BM=p, CM=s, DM=q. Let BAC=BDC=β, ABD=ACD=δ and AMB=DMC=φ.
Applying the Law of Sines, we find that

p= asinβ sinφ q= csinδ sinφ

r= asinδ sinφ s= csinβ sinφ .


p-r= a(sinβ-sinδ) sinφ q-s= c(sinδ-sinβ) sinφ


(p+q)-(r+s) = (a-c)(sinβ-sinδ) sinφ = (a-c)2cos((β+δ)/2)sin((β-δ)/2) sin(β+δ) = (a-c)sin((β-δ)/2) sin((β+δ)/2) .

Since (β+δ)/2 90ˆ , the absolute value of the sine in the numerator is less than the sine in the denominator, and so we find that


as desired.
Solution 3. [R. Furmaniak] Let O be the circumcentre of ABCD with R the circumradius. Let AOB=α, BOC=β, COD=γ and DOA=δ. Wolog, we can let δ be the largest of these angles.
We have that

AB=2Rsin α 2 CD=2Rsin γ 2

AC=2Rsin α+β 2 BD=2Rsin β+γ 2 .


AB-CD =2R (sin α 2 -sin γ 2 ) =4Rsin α-γ 4 cos α+γ 4


AC-BD=4Rsin α-γ 4 cos α+γ+2β 4 .

Since (α+2β+γ)/4 and (α+γ)/4 both do not exceed (α+β+γ+δ)/4= 90ˆ , we have that

cos α+γ+2β 4 cos α+γ 4 ,

and this yields the desired result.

Let n2 be an integer and M={1,2,,n}. For every integer k with 1kn, let

xk ={minA+maxA:AM,Ahaskelements}

where min A is the smallest and max A is the largest number in A. Determine k=1 n(-1)k-1 xk .
Solution 1. For any set S={ a1 , a2 ,, ak } we define the related set S'={(n+1)- ak ,(n+1)- ak-1 ,,(n+1)- a1 }. As S runs through all the subsets of {1,2,,n} with k elements, S' also runs through the same class of subsets; the mapping SS' is one-one. If, say, a1 is the minimum element and ak the maximum element of S, then (n+1)- a1 is the maximum and (n+1)- ak the minimum element of S'. Hence the sum of the minima and maxima of the two sets is

( a1 + ak )+2(n+1)- a1 - ak =2(n+1).

The sum of the maxima and minima of all the sets SS' is equal to 2 xk =2(n+1)( n k ), so that xk =(n+1)( n k ). Hence

k=1 n(-1)k-1 xk =-(n+1) k=1 n(-1)k ( n k )=-(n+1)[(1-1)n -1]=n+1.

Solution 2. [R. Furmaniak] For a given k and m with 1k,mn, the number of k-subsets of M with m as the smallest element is ( n-m k-1 ), and the number of k-subsets of M with m as the largest element is ( m-1 k-1 ), We use the convention that ( 0 0 )=1 and ( x y )=0 when x<y. >From this, we see that

xk = [ m=1 n-k+1m( n-m k-1 ) ]+ [ m=k nm( m-1 k-1 ) ] = [ m=1 nm (( n-m k-1 )+( m-1 k-1 ) ) ].


k=1 n(-1)k-1 xk = m=1 n [m k=1 n(-1)k-1 ( n-m k-1 ) ]+ m=1 n [m k=1 n(-1)k-1 ( m-1 k-1 ) ]. = [ m=1 n-1m k=1 n(-1)k-1 ( n-m k-1 ) ]+n( 0 0 )+ [ m=2 n-1m k=1 n( m-1 k-1 ) ]+1( 0 0 ).

Now, when n-m1,

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

and, when m2,

k=1 n(-1)k-1 ( m-1 k-1 )=(1-1)m-1 =0.

It follows that the required sum is equal to n+1.
Solution 3. [O. Bormashenko] Denote by σ the quantity k=1 n(-1)k-1 xk . Let m be a number between 1 and n-1, inclusive. m is the minimum of a k-set for exactly ( n-m k-1 ) sets. For a particular k, m as minimum contributes n( n-m k-1 ) to the sum for xk . Fixing m, m as minimum contributes to σ the value

m k=1 n(-1)k-1 ( n-m k-1 )=0,

where ( i j )=0 when j>i. The only other possible minimum is n, and this is a minimum only for the singelton {n}, so that n as minimum contributes n to the sum σ.
By a similar argument, for any number m=2,3,,n, m as maximum contributes 0 to the sum σ. 1 is maximum only for the singleton {1} and contributes the value 1 to the sum σ. Hence σ=n+1.