Problems of the Month 2001

Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec




Problem for 2001 January

Communicated by Dan Jurca

The following occurs as problem 2.5.17 in
Problems in Mathematical Analysis I
by W. J. Kaczor and M.T. Nowak.

Let
an=3- n
å
k=1 
  1
k(k+1)(k+1)!
 ,    n Î N.

(a)
Show that limn®¥an=e.
(b)
Show also that 0 < an-e < [ 1/((n+1)(n+1)!)].



Problem for 2001 February
Proposed by Dan Jurca

The largest circle in the sketch below has a radius of 1; inside it and tangent to it is a circle of radius 1/2; then there is a circle tangent to these two with radius 1/3; finally there is a circle with radius 1/4 tangent to the largest one and the one with radius 1/3. Suppose this construction is repeated indefinitely; is there, in any sense, a limiting position? Or do the circles keep going on forever?

NO FIGURE AVAILABLE


Solution by the proposer

For 1 £ n let Cn be the center of the circle with radius 1/n, and for 3 £ n let qn be the angle defined by Cn-1C1Cn. (For example, q3 is the angle at the center of the biggest circle subtended by radii to the centers of the circles with radii 1/2 and 1/3.) Then for 3 £ n there is a triangle with sides 1-1/(n-1), 1-1/n, and 1/(n-1)+1/n, where qn is the angle opposite the side of length 1/(n-1)+1/n. By the law of cosines we have
æ
è 		 1
n-1
 +  1
n
 ö
ø 		2

 
 = æ
è 		1-  1
n-1
 ö
ø 		2

 
 + æ
è 		1-  1
n
 ö
ø 		2

 
 -2 æ
è 		1-  1
n-1
 ö
ø 		æ
è 		1-  1
n
 ö
ø 		cosqn
and solving for cosqn we find
cosqn
=1-  2
(n-1)(n-2)
 ,from which
sinqn
=  2
(n-1)(n-2)
Ö
 
n2-3n+1
 
 .
Now from
3
£ nwe get
n2-4n+4
£ n2-3n+1so that
n-2
£
Ö
 
n2-3n+1
 
 ;therefore
 2
n-1
£  2
(n-1)(n-2)
Ö
 
n2-3n+1
 
 ,   whence
 2
n-1
£ sinqn.
But since 0 £ q Þ sinq £ q, we have
3 £ n Þ   2
n-1
 £ qn.
It follows (from the divergence of the harmonic series) that ån=3¥qn diverges; hence the sequence (Cn)n=1¥ of the centers of the circles does not converge to a point in the plane.


A simpler argument is based on the observation that, for 2 £ n, the length of the polygonal path from C1 to Cn is
 1
2
 + æ
è 		 1
2
 +  1
3
 ö
ø 		+ æ
è 		 1
3
 +  1
4
 ö
ø 		+¼+ æ
è 		 1
n-1
 +  1
n
 ö
ø 		=2Hn- æ
è 		2+  1
n
 ö
ø
where Hn=åi=1n1/i. Again, since Hn®¥, (Cn)n=1¥ diverges.


Also solved by Matthew Hubbard



Problem for 2001 March

Proposed by Matthew Hubbard

Prove that if 0 £ n, then
n
å
m=0 
 æ
è 		n
m
 ö
ø 		2= æ
è 		2n
n
 ö
ø 		.




Problem for 2001 April

Proposed by Dan Jurca

Suppose that A is a 2×2 matrix with entries in a field.

Prove: If A2 ¹ O, then 0 £ n Þ An ¹ O .



Problem for 2001 May

Communicated by Dan Jurca

Prove

lim
n®¥ 
 é
ë 		 1
Ön
 æ
è 		 1
Ö1
 +  1
Ö2
 +¼+  1
Ön
 ö
ø 		ù
û 		= ó
õ 		1

0 
  dx
Öx
 =2;
and use a similar method to determine the value of

lim
n®¥ 
 é
ë 		 1
n
 æ
è 		(n+1)×(n+2)×¼×(2n) ö
ø 		1/n

 
 ù
û 		.

Solution by Dan Jurca

First we observe that
ó
õ 		1

0 
  1
Öx
 dx
=
lim
a®0+ 
 ó
õ 		1

a 
  dx
Öx
=
lim
a®0+ 
 2Öx ê
ê 		1

a 
=
lim
a®0+ 
 (2-2Öa)
=2,
so that the integral exists. Next we observe that for each positive integer n the integral is approximated by
 1
n
 n
å
i=1 
  1

Ö
i/n
 ,
and in fact
ó
õ 		1

0 
  dx
Öx
=
lim
n®¥ 
  1
n
 n
å
i=1 
  1

Ö
i/n
=
lim
n®¥ 
  1
n
 n
å
i=1 
   æ
Ö
 n
i
 
=
lim
n®¥ 
  1
Ön
 n
å
i=1 
   æ
Ö
 1
i
 
 ,
so that

lim
n®¥ 
  1
Ön
 n
å
i=1 
  1
Öi
 = ó
õ 		1

0 
  dx
Öx
 =2.
Next, let
pn
=  1
n
 æ
è 		(n+1)×(n+2)×¼×(2n) ö
ø 		1/n

 
=  1
n
 æ
è 		n(1+  1
n
 )×n(1+  2
n
 )×¼×n(1+  n
n
 ) ö
ø 		1/n

 
=  1
n
 ·n æ
è 		(1+  1
n
 )×(1+  2
n
 )×¼×(1+  n
n
 ) ö
ø 		1/n

 
so that lnpn
=  1
n
 n
å
i=1 
 ln(1+  i
n
 ).
Therefore

lim
n®¥ 
 lnpn
= ó
õ 		1

0 
 ln(1+x)dx
= é
ë 		(x+1)ln(x+1)-(x+1) ù
û 		ê
ê 		1

0 
=2ln2-2-0+1
=ln4-1
=ln  4
e
 ,
so that 
lim
n®¥ 
 pn
=  4
e
 .


Also solved by Yi Shen and Yang Li Tang.



Problem for 2001 June

Communicated by Dan Jurca

Find all functions f:R®R such that
x ¹ y Þ f¢ æ
è 		 x+y
2
 ö
ø 		=  f(x)-f(y)
x-y
 .




Problem for 2001 July

Proposed by Dan Jurca

For 0 £ n let
In= ó
õ 		1

0 
 xnexdx.
Prove In ~ e/n; i.e., show that

lim
n®¥ 
    In
e/n
 =1.


Solution by the proposer

Using integration by parts one finds
I0=e-1=-1-(-1)e;   1 £ n Þ In=e-nIn-1=-nIn-1+e.
We write 0 £ n Þ In=an-bne; then a0=-1=b0, and
1 £ n Þ an
=-nan-1,
bn
=-(1+nbn-1).
Solving these recurrences we have
0 £ n Þ an
=(-1)n+1n!
bn
=(-1)n+1n! n
å
i=0 
  (-1)i
i!
as one checks by induction on n. Hence
0 £ n Þ In
=(-1)n+1n! é
ë 		1-e n
å
i=0 
  (-1)i
i!
 ù
û
=(-1)n+1n!e é
ë 		e-1- n
å
i=0 
  (-1)i
i!
 ù
û 		.
Now
e-1- n
å
i=0 
  (-1)i
i!
=  (-1)n+1
(n+1)!
 +  (-1)n+2
(n+2)!
 +  (-1)n+3
(n+3)!
 +¼
=  (-1)n+1
(n+1)!
 é
ë 		1-  1
n+2
 +  1
(n+2)(n+3)
 -+¼ ù
û
=  (-1)n+1
(n+1)!
 sn
where
1-  1
n+2
 =  n+1
n+2
 < sn < 1.
Hence
1 £ n Þ In
=  n!e
(n+1)!
 sn
=  e
n+1
 sn
=  e
n
 ·  n
n+1
 sn,
so that, finally,
1 £ n Þ   n
n+2
 <  In
e/n
 <  n
n+1
 ,
from which the assertion follows by the squeeze theorem.
It is clear that the quantity In/(e/n) may be bounded more accurately.


Also solved by Walt Becker and Yi Shen



Problem for 2001 August

Proposed by Dan Jurca

The elf problem

The following problem has appeared before, but not recently.

a.
In a certain house there are 100 pounds of gold dust. One night elves sneak into the house and steal 1% of the gold, and leave the remaining 99%. The next night the elves return and steal 2% of the gold, and leave the rest. The next night the elves return and steal 3% of the gold, and leave the rest. This continues until the 100th night, when the elves finally steal 100% of the gold, leaving none. On which night did the elves steal the most gold?


b.
Generalize; that is, suppose that n is a positive integer, and that for i between 1 and n, inclusive, on the i-th night the elves steal i/n of something, leaving the rest. On which night do the elves steal the most?




Problem for 2001 September

Proposed by Dan Jurca

An observer at distance h above the surface of a spherical planet with diameter d can see what fraction of the area of the planet?

Solution by the proposer

We recall that by a spherical zone we mean the portion of a sphere between two parallel planes; and that the area of a spherical zone of height w on a sphere of diameter d equals pdw. Next, from the figure below we see that
 r
r+h
=  r-w
r
       so that
w
=  hr
h+r
=  hd
2h+d
 .
Hence the fraction of the area of a sphere of diameter d visible from a point h above the surface of the sphere equals A(h), where
A(h)
=
pd·  hd
2h+d
pd2
=  h
2h+d
 .
Then we observe that, as expected,
0
£ A(h) <  1
2
 ,
A(0)
=0,      and

lim
¥ 
 A
=  1
2
 ,
and we also observe that
A¢(h)
=  d
(2h+d)2
 ,      so that
A¢(0)
=  1
d
 ,      and, also as expected,

lim
¥ 
 A¢
=0.


This was also solved by Walter Becker and Richie Hom.



Problem for 2001 October

Communicated by Dan Jurca

Compute
ó
õ 		¥

0 
  x50
x100+1
 dx.
More generally, discuss
ó
õ 		¥

0 
  xa
xb+1
 dx.


Solution by Dan Jurca (also solved by Rudy Horne)

We consider the second integral. One can show that the integral exists if and only if b < 0 and b-1 < a, or if 0 < b and a < b-1; moreover, evaluating the integral in the first case reduces to the second case. Therefore assume that 0 < b. Let t=1/(xb+1). Then xb=1/t-1, so that bxb-1dx=-1/t2dt, from which
dx
=-  1
b
 ·  1
t2
 ·  (1-t)1/b-1
t1/b-1
 dt,   whence
ó
õ 		¥

0 
  xa
xb+1
 dx
=  1
b
 ó
õ 		1

0 
 æ
è 		 1
t
 -1 ö
ø 		a/b
 
 ·t·  1
t2
 ·(1-t)1/b-1·  1
t1/b-1
 dt
=¼
=  1
b
 ó
õ 		1

0 
 t-(a+1)/b(1-t)(a-b+1)/bdt
=  1
b
 ó
õ 		1

0 
 t(b-a-1)/b-1(1-t)(a+1)/b-1dt
=  1
b
 B(  b-a-1
b
 ,  a+1
b
 )   if 0 <  a+1
b
  and 0 <  b-a-1
b
where B is the Beta function [1, p.258]
=  1
b
  G((a+1)/b)G((b-a-1)/b)
G(1)
    by [1], 6.2.2
=  1
b
 G æ
è 		 a+1
b
 ö
ø 		G æ
è 		 b-a-1
b
 ö
ø
=  1
b
 G æ
è 		 a+1
b
 ö
ø 		G æ
è 		1-  a+1
b
 ö
ø
=  1
b
 ·pcsc æ
è 		p  a+1
b
 ö
ø 		   by the reflection formula [1],  p. 256
=  p
bsin æ
è 		(a+1)/b·p ö
ø
.\C

Hence, if 0 < b and -1 < a < b-1, then
ó
õ 		¥

0 
  xa
xb+1
 dx=  p
bsin æ
è 		(a+1)/b·p ö
ø
.
In particular
1 < a Þ  ó
õ 		¥

0 
  xa
x2a+1
 dx
=  p
2asin æ
è 		(a+1)/2a·p ö
ø
=  p
2acos(p/2-(a+1)/2a·p)
 =  p
2a
 ·sec  p
2a
 , so
ó
õ 		¥

0 
  x50
x100+1
 dx
=  p
100
 ·sec  p
100
» 0.03143143605220806588651577.
We may also observe that
ó
õ 		¥

0 
  xa
x2a+1
 dx
~  p
2a
 ; i.e.,

lim
a®¥ 
ó
õ 		¥

0 
  xa
x2a+1
 dx
 p
2a
=1.

[1] Handbook of Mathematical Functions, edited by Milton Abramowitz and Irene Stegun





Problem for 2001 November

Proposed by Matthew Hubbard

Prove: If d is an odd integer greater than 5, then there exist positive integers a, b, and c such that

a2 + b2 + c2 = d2.

You may use Lagrange's theorem, which asserts that each positive integer is the sum of not more than four squares.



Problem for 2001 December

Proposed by Dan Jurca

Write a computer program (or design an algorithm) which one can use to display all ways of associating a product of n factors. (For example, if n=3, there are two ways- A(BC) and (AB)C.) Of course if the associative law holds, then all these ways of associating yield the same product. (This happens, for example, if the factors are matrices of such dimensions that the product exists.)

The attached output is from the proposer's program (written in C++) for the cases n=1,2,3,4,5,6.

It may be helpful to know that the number of ways of associating a product of n factors, say Pn, is given by
Pn
= ì
ï
ï
í
ï
ï
î
1
if n=1,
n-1
å
i=1 
 PiPn-i
if 1 < n;
=  1
n
 æ
è 		2n-2
n-1
 ö
ø 		,1 £ n,
the (n-1)-th Catalan number. 

 1     1  A			 6     1  A(B(C(D(EF))))
				       2  A(B(C((DE)F)))
 2     1  AB			       3  A(B((CD)(EF)))
				       4  A(B((C(DE))F))
 3     1  A(BC)			       5  A(B(((CD)E)F))
       2  (AB)C			       6  A((BC)(D(EF)))
				       7  A((BC)((DE)F))
 4     1  A(B(CD))		       8  A((B(CD))(EF))
       2  A((BC)D)		       9  A(((BC)D)(EF))
       3  (AB)(CD)		      10  A((B(C(DE)))F)
       4  (A(BC))D		      11  A((B((CD)E))F)
       5  ((AB)C)D		      12  A(((BC)(DE))F)
				      13  A(((B(CD))E)F)
 5     1  A(B(C(DE)))		      14  A((((BC)D)E)F)
       2  A(B((CD)E))		      15  (AB)(C(D(EF)))
       3  A((BC)(DE))		      16  (AB)(C((DE)F))
       4  A((B(CD))E)		      17  (AB)((CD)(EF))
       5  A(((BC)D)E)		      18  (AB)((C(DE))F)
       6  (AB)(C(DE))		      19  (AB)(((CD)E)F)
       7  (AB)((CD)E)		      20  (A(BC))(D(EF))
       8  (A(BC))(DE)		      21  (A(BC))((DE)F)
       9  ((AB)C)(DE)		      22  ((AB)C)(D(EF))
      10  (A(B(CD)))E		      23  ((AB)C)((DE)F)
      11  (A((BC)D))E		      24  (A(B(CD)))(EF)
      12  ((AB)(CD))E		      25  (A((BC)D))(EF)
      13  ((A(BC))D)E		      26  ((AB)(CD))(EF)
      14  (((AB)C)D)E		      27  ((A(BC))D)(EF)
				      28  (((AB)C)D)(EF)
				      29  (A(B(C(DE))))F
				      30  (A(B((CD)E)))F
				      31  (A((BC)(DE)))F
				      32  (A((B(CD))E))F
				      33  (A(((BC)D)E))F
				      34  ((AB)(C(DE)))F
				      35  ((AB)((CD)E))F
				      36  ((A(BC))(DE))F
				      37  (((AB)C)(DE))F
				      38  ((A(B(CD)))E)F
				      39  ((A((BC)D))E)F
				      40  (((AB)(CD))E)F
				      41  (((A(BC))D)E)F
				      42  ((((AB)C)D)E)F

Solution 

/*	assoc.c		2001 dec 03	last modified 2002 jan 07
 *
 *	Returns in the string s the m-th way of associating a product
 *	of n factors, where the first factor is 'A', etc.
 *	Here 1 <= n <= MAXN, and 1 <= m <= p[n-1].
 */

#define MAXN 11

void
assoc( int n,unsigned int m,char *s )
{
	void assoc0( int n,unsigned int m,int,char * );

	*s = '\0';
	assoc0( n,m,0,s );
}
void
assoc0( int n,unsigned int m,int a,char *s )
{
	void appendc( char *,char ),appends( char *,char * );

	unsigned int i,j,k,p[]={1,1,2,5,14,42,132,429,1430,4862,16796,58786},
		q,r,s0,s1;
	char t[3*(MAXN-1)];

	if ( n < 3 ) { 
		appendc( s,'A'+a );			// n == 1 or n == 2
		if ( 1 < n ) {
			appendc( s,'B'+a );		// n == 2
		}
		return;
	}
	for ( s1 = 0, i = 1;  i < n;  i++ ) {
		s0 = s1;
		s1 += p[i-1]*p[n-i-1];
		if ( m <= s1 ) {
			break;
		}
	}
	q = (m-s0)/(j = p[n-i-1]);
	r = (m-s0)-q*j;
	if ( r == 0 ) {
		--q;
		r = j;
	}
	if ( 1 < i ) {
		appendc( s,'(' );
	}
	*t = '\0';
	assoc0( i,q+1,a,t );
	appends( s,t );
	if ( 1 < i ) {
		appendc( s,')' );
	}
	if ( 1 < n-i ) {
		appendc( s,'(' );
	}
	*t = '\0';
	assoc0( n-i,r,a+i,t );
	appends( s,t );
	if ( 1 < n-i ) {
		appendc( s,')' );
	}
}
void
appendc( char *s,char ch )
{
	while ( *s ) {
		s++;
	}
	*s++ = ch;
	*s = '\0';
}
void
appends( char *s,char *t )
{
	while ( *s ) {
		s++;
	}
	while ( *t ) {
		*s++ = *t++;
	}
	*s = '\0';
}