Problem for 2004 January

Proposed by Matthew Hubbard

There are three non-abelian groups of order 12:

i.

the symmetries of the tetrahedron, A₄;

ii.

the dihedral group of the hexagon, D₆; and

iii.

a group known as T or as Q₆, which has generators a and b with relations

a6=1, b2=a3=(ab)2.

What is the least n such that Q₆ can be embedded in S_n?

Since a is a permutation of order six it must be a disjoint union of 6-cycles, 3-cycles, and 2-cycles; if there is no 6-cycle, there must be at least one 3-cycle and one 2-cycle, and a³ is made up of disjoint 2-cycles. Since b is of order four it is made up of disjoint 4-cycles and 2-cycles, and b² is made up of disjoint 2-cycles generated by the 4-cycles of b; likewise, ab is of order four, and (ab)² is made up of disjoint 2-cycles. The smallest number of elements we can use to create a, b, and ab meeting our criteria is seven, and an example follows.

a =(123)(46)(57),   so a3=(46)(57) b =(12)(4567),      so b2=(46)(57) ab =(13)(4765),   so (ab)2=(46)(57)

All the generating relations are satisfied, so a and b generate Q₆.

Problem for 2004 February

Proposed by Dan Jurca

Problem number 174 (from Murray Klamkin) in the book Which Way did the Bicycle Go? by Joseph D. E. Konhauser, Dan Velleman, and Stan Wagon appears as follows.

Find, with an error of no more than 5%, the numerical value of

ó õ 100 1  xx dx.

The answer 1.80086·10¹⁹⁹ is given on page 211.

Find a more accurate approximation.
Precisely, find an approximation A of the above integral I with a relative error less than 10^-6; i.e., we require

|I-A| I < 10-6.

Solution by the proposer

We begin by observing (x^x)¢=x^x(1+lnx), and next by l'Hôpital's rule and the fundamental theorem of calculus

lim x®¥  ó õ x 1  tt dt xx/(1+lnx) = lim x®¥  (1+lnx) ó õ x 1  tt dt xx = lim x®¥   1 x ó õ x 1  tt dt+xx(1+lnx) xx(1+lnx) =1+ lim x®¥  ó õ x 1  tt dt x·xx(1+lnx) =1+ lim x®¥   xx xx(1+lnx)+x[xx(1+lnx)2+xx-1] =1+0 =1.

One writes

ó õ x 1  tt dt ~  xx 1+lnx ,

and this suggests that for large x one may approximate

ó õ x 1  tt dt

with x^x/(1+lnx); for example

ó õ 100 1  tt dt »  100100 1+ln100 =  10200 1+ln100 » 1.7841×10199.

This approximation, however motivated, provides no information about the error of the approximation; hence we argue as follows.

For each a, 1 < a < 100, we write

ia= ó õ a 1  xx dx   and    Ia= ó õ 100 a  xx dx.

Then obviously

I = ó õ 100 1  xx dx = ó õ a 1  xx dx +  ó õ 100 a  xx dx =ia+Ia,   and ia < (a-1)·aa.

(We shall later choose a=e^4.5 » 90.02, and then i_a < 7.5×10¹⁷⁷. Hence it will remain to approximate I_a.)

Next with u₁=1/(1+lnx) and dv=x^x(1+lnx) dx we have

du1=-  1 x(1+lnx)2  dx   and    v=xx,

so using integration by parts

Ia=xx·  1 1+lnx ê ê 100 a   +  ó õ 100 a   1 x(1+lnx)2 ·xx dx;

now with u₂=1/[x(1+lnx)³] and dv as before we have

du2=-  4+lnx x2(1+lnx)4  dx   and    v as before,

so again using integration by parts

Ia=xx æ è  1 1+lnx +  1 x(1+lnx)3 ö ø ê ê 100 a   +  ó õ 100 a   4+lnx x2(1+lnx)4 ·xx dx;

finally, with u₃=(4+lnx)/[x²(1+lnx)⁵] and dv as before,

du3=-  27+14lnx+2(lnx)2 x3(1+lnx)6  dx   and    v as before,

so once again using integration by parts

Ia=xx æ è  1 1+lnx +  1 x(1+lnx)3 +  4+lnx x2(1+lnx)5 ö ø ê ê 100 a   +  ó õ 100 a   27+14lnx+2(lnx)2 x3(1+lnx)6 ·xx dx.

Now with j:[a,100]®R by

j(x) =  27+14lnx+2(lnx)2 x3(1+lnx)6 we find   j¢(x) =-  229+189lnx+56(lnx)2+6(lnx)3 x4(1+lnx)7

so that j¢ < 0 whence j\searrow, and j_max=j(a); therefore

ó õ 100 a  j(x)·xx dx < j(a) ó õ 100 a  xx dx=j(a)Ia.

Now let

Aa=xx é ë  1 1+lnx +  1 x(1+lnx)3 +  4+lnx x2(1+lnx)5 ù û 100 a  ;

then we have A_a < I_a < A_a+j(a)I_a, and we shall show that A_e^4.5 is a sufficiently accurate approximation of I.

Now clearly A_a < i_a+A_a < i_a+I_a=I, so that 0 < I-A_a and |I-A_a|=I-A_a.

Next, I=i_a+I_a < i_a+A_a+j(a)I_a, so I-A_a < i_a+j(a)I_a. It therefore follows that

|I-Aa| I =  I-Aa I <  ia+j(a)Ia I =  ia I +j(a)  Ia I <  ia Aa +j(a),

since A_a < I and I_a < I.

Now with a=e^4.5 we recall i_a < 7.5×10¹⁷⁷ and find (using a HP-42S calculator) that

Aa » 1.784636555×10199 so that  ia Aa < 5×10-22 andj(a) » 6.46336778×10-9, so that     |I-Aa| I < 7×10-9.

Hence we have I » 1.7846366×10¹⁹⁹ with a relative error less than 5×10^-8, so that each digit in this approximation is significant.

Problem for 2004 March

Communicated by Dan Jurca

Suppose a Î R, b Î R, a < b, f:[a,b]®R, and

x Î [a,b] Þ 0 < f¢¢(x).

Find all values c Î [a,b] such that the area of the region bounded by

the graph of y=f(x),

the line tangent to the graph at the point (c,f(c)), and

the lines x=a and x=b is minimum.

Problem for 2004 April

Communicated by Dan Jurca

According to the 2004 March issue of the Canadian mathematics journal Crux Mathematicorum the following problem appeared in the 2003 Croatian Mathematical Society National Competition, Junior Level.

Prove that if the product of the positive real numbers x, y, and z is equal to 1, and

x+y+z £  1 x +  1 y +  1 z ,

then for each nonnegative integer n

xn+yn+zn £  1 xn +  1 yn +  1 zn .

Solution by Dan Jurca

Assume 0 < x £ y £ z, so that x £ 1, else 1 < xyz. Since xyz=1, we have z=1/(xy); next from

x+y+  1 xy £  1 x +  1 y +xy   we have x2y+xy2+1 £ y+x+x2y2,   so 0 £ (x2-x)y2-(x2-1)y+(x-1)   whence 0 £ (x-1)[xy2-(x+1)y+1].

Now if x=1, then yz=1 so z=1/y and the inequality to be shown becomes simply yⁿ+(1/y)ⁿ £ 1/(yⁿ)+yⁿ, which is obvious; hence assume x < 1. Now xy²-(x+1)y+1=0 iff y=1 or y=1/x, so since xy²-(x+1)y+1 £ 0, we deduce that 1 £ y £ 1/x.

Now suppose a is a positive real number, let S={(u,v) Î R² | 0 < u £ 1 and  1 £ v £ 1/u}, and consider f:S®R by f(u,v)=u^a+v^a+1/(uv)^a-1/u^a-1/v^a-(uv)^a. We observe that (x,y) Î S and

f(u,1) =0, f æ è u,  1 u ö ø =0;   and 1 < v Þ  lim u®0+  f(u,v) =-¥,   and  ¶f ¶u (u,v) =aua-1-a  1 ua+1va +a  1 ua+1 -aua-1va =  a(1-va) ua+1va [(uv)a ua-1],

and since 1-v^a £ 0 and (uv)^a u^a-1 £ 0, it follows that 0 £ ¶f/¶u, so that for each v₀, 1 < v₀, the function g:(0,1/v₀]®R by g(u)=f(u,v₀) increases from -¥ at 0+ to 0 at 1/v₀, so we have f(u,v) £ 0 for each (u,v) Î S. Hence (with u=x and v=y)

xa+ya+  1 (xy)a £  1 xa +  1 ya +(xy)a,

and the desired inequality holds for each nonnegative real number n.

Problem for 2004 May

Communicated by Matthew Hubbard

This problem appeared in the MSRI newsletter.

There are 101 points (ants) on the interval [0,1], and one of them, call it p^*, is at 1/2. Each point has its own randomly selected starting direction, either left or right, and each point moves at the rate of one unit per minute. When two points collide they bounce off in opposite directions without losing speed; and when a point collides with an endpoint of the interval, 0 or 1, it bounces back without losing speed.

What is the probability that after one minute p^* is back at the point 1/2?

Problem for 2004 June

According to the 2004 May issue of the Canadian Mathematics journal Crux Mathematicorum the following problem appeared in the National Round of the XXXVI Spanish Mathematical Olympiad.

Show that there exists no function f:N®N such that for each n

f(f(n))=n+1.

Solution by Dan Jurca

Suppose otherwise; i.e., f:N®N and for each n Î N: f(f(n))=n+1. Then

f(f(f(n))) =f[f(f(n))]=f[n+1]   and =f(f[f(n)])=f(n)+1,   so that

n Î N Þ f(n+1)=f(n)+1.

It follows by an easy induction on k that 1 £ k Þ f(n+k)=f(n)+k. Now suppose f(1)=y. Then

f(n) =f(1+(n-1)) =f(1)+(n-1) =y+(n-1),   so that f(n) =y+n-1;   but then f(y) =2y-1   and f(f(n)) =f(y+n-1) =f(y)+n-1 =(2y-1)+n-1 =2y+n-2,   and also f(f(n)) =n+1,   whence 2y+n-2 =n+1,   and 2y =3,

which contradicts y=f(1) Î N; therefore no such f exists.

Problem for 2004 July

Proposed by Dan Jurca

Suppose that x_i Î R for i=1,2,¼,n, and 1 £ x_i for each i.

Prove the following.

3n n Õ i=1  (xi2-xi) £ n Õ i=1  (xi3-1)

Solution by the proposer

If t is a nonzero real number, then

t+  1 t =  t2+1 t =  2t+t2-2t+1 t =2+  (t-1)2 t ,   so that if 0 < t, then 2 £ t+  1 t .   Hence, for each i 3 £ xi+  1 xi +1   so (since 0 < xi) 3xi £ xi2+1+xi,   whence (since 0 £ xi-1) 3xi(xi-1) £ (xi-1)(xi2+xi+1)   so that 3(xi2-xi) £ xi3-1,

from which, by taking the product of all n factors, the desired inequality follows.

Problem for 2004 Aug

Communicated by Dan Jurca

Let P, Q, R, and S be four distinct points on a circle in clockwise order, and let A, B, C, and D be the midpoints of the arcs PQ, QR, RS, and SP, respectively. Prove that the line segments AC and BD are perpendicular.

Problem for 2004 September and October

Proposed by Dan Jurca

For each positive integer n define S(n) as follows.

S(n) = n å b=2  logbn =log2n+log3n+log4n+¼+lognn

Determine whether

lim n®¥   S(n) n

exists; and if it exists, determine its value.

We have

S(n)= n å b=2  logbn= n å b=2   lnn lnb =lnn n å b=2   1 lnb .

The function (1,¥)®R by t®1/lnt assumes only positive values and strictly decreases, so

1 < x Þ   1 ln(x+1) < ó õ x+1 x   dt lnt <  1 lnx ;

hence (by summing)

3 £ n Þ  ó õ n 2   dt lnt + ó õ n+1 n   dt lnt < n å b=2   1 lnb =  1 ln2 + n å b=3   1 lnb <  1 ln2 + n å b=3  ó õ b b-1   dt lnt =  1 ln2 + ó õ n 2   dt lnt

whence

3 £ n Þ   lnn n · ó õ n 2   dt lnt <  S(n) n <  lnn n ·  1 ln2 +  lnn n · ó õ n 2   dt lnt .

Now

lim x®¥   lnx x =0   and  ó õ ¥ 2   dt lnt =¥   (since 1 < t Þ   1 t <  1 lnt )

so by l'Hôpital's rule and the fundamental theorem of calculus

lim x®¥   lnx x · ó õ x 2   dt lnt =1;

therefore by the squeeze theorem

lim n®¥   S(n) n =1.

Problem for 2004 November

Communicated by Dan Jurca

Show that

æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+5Ö{1+¼}}     =3.

Remark. This problem probably originated with Ramanujan. For some interesting background material see Robert Kanigel, The Man Who Knew Infinity, page 86.

3 =Ö9 = Ö   1+8   = Ö   1+2·4   =   æ Ö 1+2 Ö 16   =   æ Ö 1+2 Ö 1+15   =   æ Ö 1+2 Ö 1+3·5   =   æ Ö 1+2   æ Ö 1+3 Ö 25     =   æ Ö 1+2   æ Ö 1+3 Ö 1+24     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4·6     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{36}     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+35}     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+5·7}     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+5Ö{49}}     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+5Ö{1+48}}     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+5Ö{1+6·8}}     =   æ Ö 1+2   æ Ö 1+3 Ö 1+4Ö{1+5Ö{1+¼}}

Problem for 2004 December

Proposed by Bill Nico

Prove that the following construction of a regular pentagon is correct.

1.

Draw a (unit) circle centered at O.

2.

Draw a line (extended diameter) through O meeting the circle in points A and B.

3.

At B construct a perpendicular to the line AOB and mark on it a point C such that length OB= length BC; i.e., 1.

4.

With center A and radius AC draw an arc meeting line AOB in point D (beyond B).

5.

Bisect line segment OD, calling the midpoint E.

6.

Construct the perpendicular bisector of segment OE, calling the midpoint F and the point where the perpendicular bisector meets the circle G.

7.

The chord GB is one side of the pentagon inscribed in the circle; complete it in the obvious way.