Problem for 2006 January

Communicated by Dan Jurca

Evaluate the following sums, if they exist.

¥ å n=1  (arctan(n)-arctan(n-1))

¥ å n=1  arctan  1 n2-n+1

Solution by Dan Jurca

We show each series sums to p/2.

First we observe that

1 £ N Þ  N å n=1  (arctan(n)-arctan(n-1))=arctan(N).

This is obvious if N=1, since arctan(0)=0, and for 2 £ N follows by an easy induction on N. Therefore

¥ å n=1  (arctan(n)-arctan(n-1)) = lim N®¥  N å n=1  (arctan(n)-arctan(n-1)) = lim N®¥  arctan(N) =p/2.

Next from the formula tan(A-B)=(tanA-tanB)/(1+tanAtanB), with A=arctan(a) and B=arctan(b) we have

arctan(a)-arctan(b)=arctan  a-b 1+ab ,

whence with a=n and b=n-1 we find

arctan(n)-arctan(n-1) =arctan  n-(n-1) 1+n(n-1) =arctan  1 n2-n+1 ,

so that the series sum to the same value, since the terms are the same.

Problem for 2006 February

According to the 2005 December issue of the Canadian mathematics journal Crux Mathematicorum the following problem appeared in the 2005 Maritime Mathematics Competition.

Three students play a game with the understanding that the loser is to double the money of each of the other two. After three games, each has lost once and each has $24. How much did each student have to start?

a.

Solve the problem above.

b.

Generalize as follows. Suppose there are n players, say the players are P₁, P₂, ¼, P_n, and the notation is such that player P_i loses exactly once, the i-th game. Again suppose that the loser of a game doubles the money of each of the other players, that the n players play n games, and that after these n games each player has an amount A. For 1 £ i £ n and 0 £ j £ n let a_ij be the amount had by player P_i after j games have been played. Thus player P_i begins with a_i0, and for each i, 1 £ i £ n, a_in=A.

Determine a_ij.

By the conditions in the statement of the problem one has the following.

1 £ i £ n and 1 £ j £ n  Þ aij= ì ï ï í ï ï î 2ai,j-1 if j ¹ i, ai,j-1- n å k=1, k ¹ i  ak,j-1 if i=j.

Since after n games the total amount of money had by all the players equals nA, it follows that

0 £ j £ n Þ  n å k=1  akj =nA,   so that 0 £ j £ n Þ  n å k=1, k ¹ i  akj =nA-aij,

and one can restate the condition above as follows.

1 £ i £ n and 1 £ j £ n Þ aij= ì ï í ï î 2ai,j-1 if j ¹ i, 2ai,i-1-nA if i=j.

Now there exists a n×(n+1) matrix with rows 1,2,¼,n and columns 0,1,¼,n containing a_ij in row i and column j as follows.

æ ç ç ç ç ç ç ç ç ç è a10 2a10-nA 4a10-2nA 8a10-4nA ¼ 2na10-2n-1nA a20 2a20 4a20-nA 8a20-2nA ¼ 2na20-2n-2nA a30 2a30 4a30 8a30-nA ¼ 2na30-2n-3nA : : : : ··· : an0 2an0 4an0 8an0 ¼ 2nan0-nA ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø

It follows by inspection that

1 £ i £ n and 0 £ j £ n Þ aij= ì ï í ï î 2jai0 if j < i, 2jai0-2j-inA if i £ j.

Since 1 £ i £ n Þ a_in=A, we find

2nai0-2n-inA =A,   whence ai0 =  A+2n-inA 2n =  2n-in+1 2n A,   so that, finally 1 £ i £ n and 0 £ j £ n Þ aij = ì ï ï ï í ï ï ï î  2n-i+jn+2j 2n A if j < i,  2j 2n A if i £ j,

which one can verify by induction.

In the special case n=3, A=$24, we have a₁₀=$39, a₂₀=$21, and a₃₀=$12.

Problem for 2006 March

Proposed by Dan Jurca

Find a non-constant continuous function f:[0,¥)®R such that for each x, 0 £ x, if S_x is the surface obtained by revolving (about the x-axis) the graph of f from the y-axis to the vertical line through the point (x,0), then the volume enclosed by S_x (with ends at 0 and x) equals the surface area of S_x.

Remark. Here the surface area of S_x does not include the areas of the circles at the ends.

Using the formulas for volume and surface area the conditions in the problem require

0 £ x Þ p ó õ x 0  f2=2p ó õ x 0  f Ö   1+(f¢)2

so that by equating the derivatives of the two sides of the equation we have (by the fundamental theorem of calculus)

0 £ x Þ p(f(x))2=2pf(x) Ö   1+(f¢(x))2   ,

which holds if f satisfies

0 £ x Þ f(x)=2 Ö   1+(f¢(x))2   .

Writing y=f(x) we have the differential equation y=2Ö{1+(y¢)²}, or y²=4(1+(y¢)²), so that we have the separable equation

dy Ö y2-4 =  dx 2 .

Hence ln|y+Ö{y²-4}|=x/2+C, some C. Setting y(0)=2 we find C=ln2, so that

ln|y+ Ö   y2-4   | =x/2+ln2 =ln2ex/2,      so that y+ Ö   y2-4   =2ex/2,      whence, solving for y, y =ex/2+e-x/2 =2cosh(x/2).

One easily checks that f(x)=2cosh(x/2) satisfies the conditions in the problem. Other solutions exist.

Problem for 2006 April

Proposed by Dan Jurca

The following problem is a variation of problem 11209 which appears in the 2006 March issue of The American Mathematical Monthly.

Show that there do not exist positive real numbers x₁, x₂, and x₃ which satisfy the following system of equations.

(x1+x2+x3)x1 =6/7 (x1+x2+x3)x2 =7/8 (x1+x2+x3)x3 =8/9

Solution by the proposer

Assuming that there exist x₁, x₂, and x₃ which satisfy the given system we obtain a contradiction as follows. With X=x₁+x₂+x₃ we find the product of the equations yields the equation

Xx1×Xx2×Xx3 =6/7×7/8×8/9,   so that Xx1+x2+x3 =6/9,or XX =2/3.

However, if j:(0,¥)®R by j(x)=x^x, we find

j¢(x) =xx(1+lnx) =0 if and only if x=1/e,

and that j_min=j(1/e)=(1/e)^1/e. Since 2/3 < (1/e)^1/e » 0.6922, there exists no real X such that X^X=2/3; hence there exists no solution of the system.

Also solved by Massoud Malek, Craig Prescott, John M. Sayer, and Nathan Speed

Problem for 2006 May

Communicated by Dan Jurca

a.

Show that there exists a bijection R^N®R; i.e., from the set of sequences of real numbers to the set of real numbers.

Here N={0,1,2,¼}, the set of natural numbers,

and R= the set of real numbers.

b.

Deduce that if I is a non-empty real interval, then C(I), the set of continuous functions I®R, has the cardinality of R.

Remark. The proof shows more generally that if X is a non-empty separable Hausdorff space, then the cardinality of C(X) equals the cardinality of R.

We recall the definitions: for sets A and B the set B^A equals the set of all functions from A to B, and a sequence in a set S is an element of S^N; i.e., a sequence in S is a function N® S. One way to verify the existence of a bijection R^N®R is to recall that there exists a bijection R®2^N={0,1}^N, where 2^N={0,1}^N is the set of binary sequences-sequences of 0s and 1s. (A nice argument is in chapter 2 of Notes on Set Theory by Yiannis Moschovakis.) Now a function j:B® C induces j_*^A:B^A® C^A by f®j°f, and it is trivial to verify that if j:B® C is a bijection with inverse y:C® B, then y_*^A:C^A® B^A is the inverse of j_*^A, so that j_*^A is also a bijection. Thus it suffices to show that there exists a bijection ({0,1}^N)^N®{0,1}^N; i.e., there exists a bijection from the set of sequences of binary sequences to the set of binary sequences. We can do this using Cantor's ``first diagonal method''.

So suppose X Î ({0,1}^N)^N; say X=(x_i)_i=0^¥, where each x_i is a binary sequence, say x_i=(x_i,j)_j=0^¥, where each x_i,j Î {0,1}. We consider the doubly infinite array as follows.

x0 =(x0,0    x0,1    x0,2    x0,3   ¼) x1 =(x1,0    x1,1    x1,2    x1,3   ¼) x2 =(x2,0    x2,1    x2,2    x2,3   ¼) x3 =(x3,0    x3,1    x3,2    x3,3   ¼) : ::::···

We associate with this sequence X of binary sequences the binary sequence y, where

y=(x0,0    x0,1    x1,0    x0,2    x1,1    x2,0    x0,3    x1,2    x2,1    x3,0   ¼).

It is easy to see that y is well-defined, and that X can be recovered from y; i.e., ({0,1}^N)^N®{0,1}^N by X®y is a bijection. Thus there exists a bijection R^N®R.

Also solved by Bill Nico

Problem for 2006 June

Proposed by Dan Jurca

Prove that of all right triangles with given perimeter the isosceles right triangle has maximum area.

One can easily do this using techniques from calculus; can you find a proof which does not use calculus?

We find the perimeter p and area A of a right triangle with base x and height y.

p =x+y+ Ö   x2+y2   A =xy/2,      so that y =  p2-2px 2p-2x    and A =  p2x-2px2 4p-4x

Iff x=y, then x=p/(2+Ö2) and A=x²/2=p²/(12+8Ö2). Thus we show that

x < p Þ   p2x-2px2 4p-4x £  p2 12+8Ö2 .

Now

0 £ (p-(2+Ö2)x)2, (equality iff p=(2+Ö2)x),   so 0 £ p2-(4+2Ö2)px+(6+4Ö2)x2,   so (4+2Ö2)px-(6+4Ö2)x2 £ p2,   so 4px+2Ö2px-(6+4Ö2)x2 £ p2,   so 3px+2Ö2px-6x2-4Ö2x2 £ p2-px,   so (3+2Ö2)(px-2x2) £ p2-px,   so (12+8Ö2)(px-2x2) £ 4p2-4px,   so (12+8Ö2)(p2x-2px2) £ (4p-4x)p2,   and (since x < p)  p2x-2px2 4p-4x £  p2 12+8Ö2 ,

as desired; clearly equality holds if and only if x=p/(2+Ö2).

Problem for 2006 July

Communicated by Dan Jurca

The following appears as problem C on page 76 of General Topology by John L. Kelley.

A topological space is a door space iff every subset is either open or closed. A Hausdorff door space has at most one accumulation point, and if x is a point which is not an accumulation point, then {x} is open. (If U is an arbitrary neighbrhood of an accumulation point y, then U ~ {y} is open.)

Suppose that X is a Hausdorff door space and a Î X is an accumulation point. We shall show that if x Î X and x ¹ a, then {x} is open, so that x is not an accumulation point.

Since X is Hausdorff and a ¹ x there exist open subsets U and V of X such that a Î U, x Î V, and UÇV=Æ. Let A={a}È(V-{x}). If A is open, then AÇU={a} is open. This is impossible, since if {a} is open then the open set {a} contains a but no other point of X, contradicting the hypothesis that a is an accumulation point. Since X is a door space and A is not open, it follows that A is closed, so that X-A is open; hence (X-A)ÇV is also open. Now clearly x Î (X-A)ÇV, since x Ï A but x Î V; i.e., {x} Ì (X-A)ÇV. But if y Î (X-A)ÇV, then y Î V; also y Î X-A, so that y Ï V-{x}. Hence y Î V-(V-{x})=VÇ{x}={x}. That is, (X-A)ÇV Ì {x}. Hence the open set (X-A)ÇV={x}, so that {x} is open, and x is not an accumulation point.

Also solved by Massoud Malek

Problem for 2006 August

Proposed by Dan Jurca

Prove the following.

lim n®¥  ó õ p/2 0  sinnq dq = 0

Solution by the proposer

Suppose 0 < e < p/2. Let a=(p-e)/2, so 0 < a < p/2. Now

ó õ p/2 0  sinnq dq = ó õ a 0  sinnq dq+ ó õ p/2 a  sinnq dq.

Since 0 < sina < 1, sinⁿa®0 as n®¥; hence there exists n₀ such that 1 £ n₀ and n₀ £ n Þ sinⁿa £ e/(2a), so n₀ £ n Þ asinⁿa £ e/2. Therefore, since 1 £ n Þ sinⁿ increases on the interval [0,a],

n0 £ n Þ  ó õ a 0  sinnq dq < (a-0)sinna £ e/2.

Also

ó õ p/2 a  sinnq dq < (p/2-a)sinn(p/2) =(p/2-a)×1 =e/2.

Therefore

n0 £ n Þ  ó õ p/2 0  sinnq dq < e,   whence lim n®¥  ó õ p/2 0  sinnq dq =0.

Also solved by Massoud Malek and John M. Sayer

Problem for 2006 September

Proposed by Dan Jurca

The following program written in C/C++ can be used to (recursively) compute the Fibonacci numbers F_n, where F₀=0, F₁=1, and 2 £ n Þ F_n=F_n-2+F_n-1.

unsigned int
fib(unsigned int n)
{
return( n < 2 ? n : fib(n-2) + fib(n-1) );
}

Let C_n be the number of times this function is entered when it is used to compute F_n. For example, C₀=C₁=1 and C₂=3. Determine C_n as a function of n.

Proposition. 0 £ n Þ C_n=2F_n+1-1.

Proof.

We have

C0 =1=2·1-1=2F1-1=2F0+1-1      and C1 =1=2·1-1=2F2-1=2F1+1-1,

so the proposition certainly holds if n=0 or n=1. Suppose now that 2 £ n, C_n-2=2F_n-1-1, and C_n-1=2F_n-1. Then since, obviously,

Cn =1+Cn-2+Cn-1,      we have Cn =1+(2Fn-1-1)+(2Fn-1) =2(Fn-1+Fn)-1 =2Fn+1-1,

so the proposition follows by induction on n.

Problem for 2006 October

Communicated by Dan Jurca

One may compute the value of a commonly occurring function f of two positive integers by the following formula.

f(m,n)=m+n-mn+2 n-1 å k=1  ê ë  km n ú û

Identify this function, and prove the correctness of your result.

The following three propositions will show that f=gcd.

Proposition 1. If x Î R, then ëxû+ë-xû = 0 if x Î Z and ëxû+ë-xû = -1 if x Ï Z.
Proof.
Suppose x Î R. Then there exists (a unique) q such that 0 £ q < 1 and x=ëxû+q. Clearly q = 0 iff x Î Z. Now

-x=-ëxû-q = -ëxû-1+(1-q)

and since 0 < 1-q £ 1 while 1-q = 1 iff x Î Z, (else 0 < 1-q < 1) we have

ë-xû = ì ï í ï î -ëxû if x Î Z -ëxû-1 if x Ï Z    whence    ëxû+ë-xû = ì ï í ï î 0 if x Î Z -1 if x Ï Z.

Proposition 2. f(m,n)=|{k Î N : 1 £ k £ n and n|km}|.
Proof.

2 n-1 å k=1  ê ë  km n ú û = n-1 å k=1  æ è ê ë  km n ú û + ê ë  (n-k)m n ú û ö ø . Now  ê ë  km n ú û + ê ë  (n-k)m n ú û = ê ë  km n ú û +m+ ê ë  -km n ú û , and  ê ë  km n ú û + ê ë  -km n ú û = ì ï í ï î 0 if n|km -1 if n\not|km.

Therefore with g=g(m,n)=|{k Î N : 1 £ k £ n and n|km}|, we have (since n|nm but n-1 < n)

2 n-1 å k=1  ê ë  km n ú û =(g-1)m+(n-g)(m-1) =gm-m+mn-n-gm+g =-m-n+mn+g,

so that f(m,n)=g=g(m,n).

Proposition 3. 1 £ m and 1 £ n Þ g(m,n)=|{k Î N : 1 £ k £ n and n|km}|=gcd(m,n).
Proof.
Let k₀=min{k : 1 £ k £ n and n|km}, so 1 £ k₀ £ n, and n|k₀m. Clearly, since n|k₀m, then 1 £ q Þ n|(qk₀)m. Moreover, if n|km, then $q such that k=qk₀. For say n|km and k=k₀q+r, where 0 £ r < k₀. Then since n|km we have n|(k₀q+r)m, so, since n|k₀qm, it follows that n|rm as well; then since r < k₀, it follows that r=0. Thus n|km iff k equals some multiple of k₀. Therefore, since n|nm, we have k₀|n, and g(m,n)=n/k₀. Therefore g(m,n)|n. Obviously (n/k₀)|m, since n|(k₀m). It follows that g(m,n)|m as well. Now since g(m,n)|m and g(m,n)|n, we have g(m,n)|gcd(m,n), so g(m,n) £ gcd(m,n).

Now suppose n/gcd(m,n)=k₁, so 1 £ k₁ £ n. Then

k1m n =  m n/k1 =  m gcd (m,n) Î N

so that k₁ equals some multiple of k₀. Hence k₀ £ k₁, whence gcd(m,n)=n/k₁ £ n/k₀=g(m,n), so that gcd(m,n) £ g(m,n).

Thus g(m,n)=gcd(m,n).

By propositions 1, 2, and 3 it follows that f(m,n)=gcd(m,n); i.e., f=gcd.

Problem for 2006 Novemeber

Proposed by Istvan Simon

One sunny day Mary did the following experiment on the Hayward campus of the California State University, East Bay: she marked the end of the shadow of a vertical flagpole on a piece of paper placed on the horizontal ground every five minutes for four hours. She was astonished to discover that the forty-eight points that she had marked on the paper were all on a straight line. Explain what Mary observed.

Solution by the proposer

1.

The Sun is very far from the Earth. As a result of this, any two of the Sun's rays that hit the Earth simultaneously can be considered to be parallel for all practical purposes.

2.

Imagine you are standing on the North Pole at the height of summer, on June 21. Because you are on axis with the Earth's rotation the rays of the Sun during the day will form a cone. The vertex of this cone is the tip of your head, and the end of your shadow will describe a circle. Now imagine you repeat the same experiment on the Hayward Campus, that is you stand in the parking lot for a while on June 21. What will you see?

3.

Because the Sun's rays are always parallel everywhere, the rays of the Sun will form a cone parallel to the cone at the North Pole mentioned above. The difference is that the cone will be cut by the horizontal plane which is now at an angle with the cone, no longer perpendicular to the cone's axis, and the exact angle depends on the latitude where you are standing. It follows that the end of your shadow describes a conic section, that is the intersection of a cone and a plane. Depending on your latitude, the end of your shadow will describe a circle (at the North Pole), an ellipse at high latitudes, or an arc of a hyperbola, as you move further South from the North Pole. On the Hayward Campus it will be an arc of a hyperbola on June 21.

4.

It follows from the above discussion that what Mary observed does not occur on every day. In particular, we just proved that on June 21, the shadow would not describe a straight line, as she observed, but a hyperbola.

5.

To understand what Mary observed it is helpful to return to the North Pole and repeat the experiment on June 22, June 23, June 24, etc. ¼ every day of the year. As the Earth moves around the Sun the angle of the cone will change, because the axis of the Earth is inclined 23.5 degrees off the perpendicular to the ecliptic, the plane of the orbit of the Earth. What you would see as a result is that the cone would open up as the Sun would move down closer to the horizon at the North Pole. Your shadow would be still on a circle every day, but the circle would be opening up and becoming larger and larger with each passing day. During the equinox, the Sun is perpendicular at the equator. Therefore, at that point the cone degenerates into a plane perpendicular to the axis of the Earth. The intersection of this plane with the horizontal plane in Hayward is a straight line, and that is what Mary observed. Note that during the equinox (which occurs twice in a year), the shadow describes a straight line everywhere on Earth, as proved in this section.

6.

To be absolutely precise, the shadow would describe a spiral on the North Pole, but we can ignore the small motion of the Earth around the Sun in its orbit on any one day as a very good approximation, as done in the discussion above. There is also the wobbling effect of the axis of the Earth, with a period of 22,000 years but this minute effect can be safely ignored on any one day of observations.

7.

An interesting corollary of our proof is that we can infer that Mary'e experiment must have occurred on September 22 or March 22 approximately, the dates for the equinox in most years. (Note that the date of the equinox changes very slowly due to the wobbling of the axis of the Earth mentioned above in (6).)

Problem for 2006 December

Proposed by Dan Jurca

The following is a slight variation on Mathematical Mayhem problem 213, which appeared (with solution) in the 2006 November edition of the Canadian mathematics journal Crux Mathematicorum.

Suppose x and y are (real or complex) numbers, and P equals the following product of n factors.

P=(x+y)(x2+y2)(x4+y4)(x8+y8)(x16+y16)¼

Find the value of P.

First suppose x=y; then

P =2x×2x2×2x4×¼×2x2n-1 =2nx1+2+4+¼+2n-1 =2nx2n-1.

Next

(x-y)P =(x-y)(x+y)(x2+y2)(x4+y4)(x8+y8)¼(x2n-1+y2n-1) =(x2-y2)(x2+y2)(x4+y4)(x8+y8)¼(x2n-1+y2n-1) =(x4-y4)(x4+y4)(x8+y8)¼(x2n-1+y2n-1) =(x8-y8)(x8+y8)¼(x2n-1+y2n-1) : =x2n-y2n.

Hence

P= ì ï ï í ï ï î 2nx2n-1 if x=y,  x2n-y2n x-y if x ¹ y.

Remark. One observes that if f(y)=y²ⁿ-x²ⁿ, then

lim y® x   x2n-y2n x-y = lim y® x   y2n-x2n y-x =f¢(x) =2nx2n-1.

Also solved by Grant Morgan