Problem for 2002 January

Proposed by Dan Jurca

Modified from a problem in the Canadian mathematics journal Crux Mathematicorum

Suppose there are two players, say A and B; A tosses a fair coins, and B tosses b fair coins; let P(a,b) be the probability that B gets more heads than A.

1.

Find a formula for P(n,n).

2.

Show that

a.

0 £ P(n,n) < ¹/₂;

b.

(P(n,n))_n=0^¥\nearrow; i.e., the sequence (P(n,n)) increases;

c.

lim_n®¥P(n,n)=¹/₂.

3.

Determine P(n,n+1).

The probability that in a toss of n fair coins, 1 £ n, exactly i heads occur is

æ è n i ö ø æ è  1 2 ö ø n   ,   0 £ i £ n.

Therefore the probability that in two tosses of n fair coins the same number of heads occurs both times is

æ è n 0 ö ø æ è  1 2 ö ø n   × æ è n 0 ö ø æ è  1 2 ö ø n   + æ è n 1 ö ø æ è  1 2 ö ø n   × æ è n 1 ö ø æ è  1 2 ö ø n   +¼+ æ è n n ö ø æ è  1 2 ö ø n   × æ è n n ö ø æ è  1 2 ö ø n   = æ è  1 2 ö ø 2n   n å i=0  æ è n i ö ø 2   = æ è  1 2 ö ø 2n   æ è 2n n ö ø ,

the last equality following from the 2001 March ``problem of the month''. It follows that the probability that in two tosses of n fair coins there are more heads in the second toss is

P(n,n)=  1 2 é ë 1- æ è  1 2 ö ø 2n   æ è 2n n ö ø ù û .

It is now clear that 0 £ n Þ 0 £ P(n,n) < 1/2. Next, from

æ è 2n n ö ø 22n =  (2n)(2n-1) nn æ è 2n-2 n-1 ö ø 2·2·22n-2 =  2n-1 2n æ è 2n-2 n-1 ö ø 22n-2 < æ è 2n-2 n-1 ö ø 22n-2

we see that the sequence ((¹/₂)²ⁿ(2n || n))_n=0^¥ decreases, so that the sequence (P(n,n)) increases. Finally from the recursion formula

ó õ p/2 0  sin0q dq =  p 2 ;      2 £ n Þ  ó õ p/2 0  sinnq dq =  n-1 n ó õ p/2 0  sinn-2q dq,

which follows from an application of integration by parts, we have

2 p ó õ p/2 0  sin2nq dq =  (2n-1)×(2n-3)×¼×1 (2n)×(2n-2)×¼×2 = æ è  1 2 ö ø 2n   æ è 2n n ö ø ,

(Wallis's product), from which it follows that

lim n®¥  æ è  1 2 ö ø 2n   æ è 2n n ö ø =0,

whence lim_n®¥P(n,n)=¹/₂. In fact

P(n,n) ~  1 2 é ë 1-  1 Ö pn æ è 1-  1 8n +  1 128n2 -¼ ö ø ù û .

Now for 0 £ a and 0 £ b we clearly have

P(a,b) = a å i=0  æ è a i ö ø æ è  1 2 ö ø a   b å j=i+1  æ è b j ö ø æ è  1 2 ö ø b   = æ è  1 2 ö ø a+b   a å i=0  æ è a i ö ø b å j=i+1  æ è b j ö ø ,   so that P(n,n+1) = æ è  1 2 ö ø 2n+1   n å i=0  æ è n i ö ø n+1 å j=i+1  æ è n+1 j ö ø = æ è  1 2 ö ø 2n+1   n å i=0  æ è n i ö ø n+1 å j=i+1  é ë æ è n j-1 ö ø + æ è n j ö ø ù û = æ è  1 2 ö ø 2n+1   n å i=0  æ è n i ö ø é ë n+1 å j=i+1  æ è n j-1 ö ø + n+1 å j=i+1  æ è n j ö ø ù û = æ è  1 2 ö ø 2n+1   n å i=0  æ è n i ö ø é ë n å j=i  æ è n j ö ø + n å j=i+1  æ è n j ö ø ù û = æ è  1 2 ö ø 2n+1   n å i=0  æ è n i ö ø é ë æ è n i ö ø +2 n å j=i+1  æ è n j ö ø ù û = æ è  1 2 ö ø 2n+1   é ë n å i=0  æ è n i ö ø 2   +2 n å i=0  æ è n i ö ø n å j=i+1  æ è n j ö ø ù û = æ è  1 2 ö ø 2n+1   ì í î æ è 2n n ö ø + é ë n å i=0  æ è n i ö ø ù û 2   - n å i=0  æ è n i ö ø 2   ü ý þ = æ è  1 2 ö ø 2n+1   é ë æ è 2n n ö ø +(2n)2- æ è 2n n ö ø ù û = æ è  1 2 ö ø 2n+1   ×22n =  1 2 .

We have used here the facts that

1.

å_i=0ⁿ(n || i)=2ⁿ; and

2.

for any n+1 real numbers (or complex numbers, or elements of a commutative ring) x₀,x₁,¼,x_n one has

2 n å i=0  xi n å j=i+1  xj= æ è n å i=0  xi ö ø 2   - n å i=0  xi2,

as one shows by induction on n or by considering (x₀+x₁+¼+x_n)².

Problem for 2002 February

Proposed by Dan Jurca

Does there exist a continuous function f:R®R such that each value attained by f is attained precisely twice?

That is, does there exist a function f:R®R such that

1.

f is continuous; and

2.

x Î R Þ $ ! y Î R such that

i.

y ¹ x, and

ii.

f(y)=f(x)?

There does not exist such a function. For suppose f is such a function; we derive a contradiction as follows.

First let f₀:R®R by f₀(x)=f(x)-f(0). Then f₀ is continuous and f₀(0)=0. Next there exists y ¹ 0 such that f(y)=f(0); let f₁:R®R by f₁(x)=f₀(y·x). Then f₁ is continuous, and f₁(1)=f₀(y)=f(y)-f(0)=0=f₀(0) = f₁(0). Now f₁|_[0,1] is continuous, so attains a minimum and a maximum in [0,1]; let us say a minimum occurs at u Î [0,1] and a maximum occurs at v Î [0,1]. Now clearly either f₁(u) < 0 or 0 < f₁(v), as otherwise f attains the value 0 at more than two points. Now define

f2= ì ï í ï î f1 if 0 < f1(v), -f1 if f1(v)=0.

Then f₂ is continuous, f₂(0)=0=f₂(1), and f₂|_[0,1] attains a maximum value different from 0 in the interval [0,1], let us say at the point a Î [0,1]. Now there exists a point b Î R such that b ¹ a and f₂(b)=f₂(a). We consider two cases.

First suppose b Î [0,1]. Again there are two cases: b < a and a < b. We will consider a < b, as the other case is similar. Now there exists c such that a < c < b, and 0 < f₂(c) < f₂(a)=f₂(b). By the intermediate value theorem there exist x₁ between 0 and a such that f₂(x₁)=f₂(c), x₂ between a and c such that f₂(x₂)=f₂(c), x₃ between c and b such that f₂(x₃)=f₂(c), and x₄ between b and 0 such that f₂(x₄)=f₂(c). But it now follows that f(x₁)=f(x₂)=f(x₃)=f(x₄), and of course x₁, x₂,x₃, and x₄ are distinct. Thus f attains some value at least four times, a contradiction.

A similar (and similarly tedious) argument holds if b Ï [0,1].

Hence no such f exists.

Problem for 2002 March

Proposed by Dan Jurca

For 0 £ n let H_n be the sum of the first n terms of the harmonic series; i.e.,

Hn= ì ï ï í ï ï î 0 if n=0; n å i=1   1 i if 1 £ n.

Find a formula for

n å i=0  iHi.

The proposer encountered this sum when analyzing a certain variation of the quicksort algorithm.

Proposition.

0 £ n Þ  n å i=0  iHi=  n2+n 2 Hn-  n2-n 4

Proof.

The formula obviously holds if n=0; now suppose that 1 £ n and

n-1 å i=0  iHi =  (n-1)2+(n-1) 2 Hn-1-  (n-1)2-(n-1) 4 =  n2-2n+1+n-1 2 Hn-1-  n2-2n+1-n+1 4 =  n2-n 2 æ è Hn-  1 n ö ø -  n2-3n+2 4 =  n2-n 2 Hn-  n-1 2 -  n2-3n+2 4 =  n2-n 2 Hn-  n2-3n+2+2n-2 4 =  n2-n 2 Hn-  n2-n 4 ; then n å i=0  iHi =  n2-n 2 Hn+nHn-  n2-n 4 =  n2+n 2 Hn-  n2-n 4 ,

so the proposition follows by induction on n.

Problem for 2002 April

Proposed by Dan Jurca

Find a formula for the following sum, where n is a nonnegative integer.

å 1 £ i < j £ n  ij

Solution by the proposer

We show that the sum equals [(n(3n+2)(n²-1))/24]. For with

Sn = å 1 £ i < j £ n  ij,   we have Sn = ì ï ï í ï ï î 0 if n=0, å 1 £ i < j £ n-1  ij+ æ è n-1 å i=1  i ö ø ×n if 1 £ n; so that Sn = ì ï ï í ï ï î 0 if n=0, Sn-1+  (n-1)n2 2 if 1 £ n.

Now the asserted formula obviously holds if n=0; suppose that 1 £ n and

Sn-1 =  (n-1)[3(n-1)+2][(n-1)2-1] 24 ;   then Sn =Sn-1+  (n-1)n2 2 =  (n-1)(3n-1)(n2-2n)+12(n-1)n2 24 =  (n-1)n[(3n-1)(n-2)+12n] 24 =  (n-1)n[3n2-7n+2+12n] 24 =  (n-1)n(3n2+5n+2) 24 =  (n-1)n(n+1)(3n+2) 24 =  n(3n+2)(n2-1) 24 ,

so that by induction the formula holds for each nonnegative integer n.

Problem for 2002 May

Communicated by Dan Jurca

The following problem in the 2002 April issue of the Canadian mathematics journal Crux Mathematicorum is from the Swiss Mathematical Contest, May 17, 1999.

Find all solutions (x,y,z) Î R×R×R of the system

4x2 1+4x2 =y,        4y2 1+4y2 =z,        4z2 1+4z2 =x.

Solution by Dan Jurca

It is clear that (0,0,0) and (1/2,1/2,1/2) are solutions; we show these are the only solutions.
Consider f:R®R by

f(t) =  4t2 1+4t2 .   We find f¢(t) =  8t·(1+4t2)-4t2·8t (1+4t)2 =  8t (1+4t2)2 ,

so t < 0 Þ f¢(t) < 0, 0 < t Þ 0 < f¢(t). Thus

f(0)=0, 0 £ f < 1,  lim ¥  f=1, f\searrowon (-¥,0], f\nearrowon [0,¥).

Now we have x=f(z)=f(f(y))=f(f(f(x))), so that with g=f°f°f, x is a fixed point of g; i.e., g(x)=x. Since f\nearrow on [0,¥), it follows that g\nearrow on [0,¥). Observe that

t-f(t)=  t(1-2t)2 1+4t2 =0 if and only if t=0 or t=1/2,

and 0 < t < 1/2 or 1/2 < t Þ t < f(t). Thus 0 < t < 1/2 or 1/2 < t Þ

t < f(t), so f(t) < f(f(t)), (since f\nearrow), so t < f(f(t)), (since t < f(t)), so f(t) < f(f(f(t))), (since f\nearrow), so t < g(t), (since t < f(t).)

Hence t ¹ 0 or t ¹ 1/2 Þ g(t) ¹ t. Thus the only fixed points of g are 0 and 1/2. Therefore x=0 or x=1/2. Now

x=0 Þ y=0 Þ z=0,   and x=1/2 Þ y=1/2 Þ z=1/2.

Hence the only solutions are (0,0,0) and (1/2,1/2,1/2), as asserted.

Problem for 2002 June

Communicated by Dan Jurca

This is an old problem, but has not appeared here for a long time.

There are one million dots (points) in the plane; prove that there exists a (straight) line such that exactly half of the dots are on each side of the line.

We generalize to the case that there are 2n dots, where n is a positive integer. Let us call this set of points S. Consider the set of all

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

(not necessarily distinct) lines determined by each pair of points chosen from S. These lines do not cover the entire plane-the plane is not the union of finitely many lines. Hence there exists a point, say P, which does not lie on any of the lines, and furthermore lies to the left of some disk the interior of which includes S. Now for each point Q in S the line determined by P and Q contains no point of S other than Q. Therefore as the point Q varies through S we may mark the n-th and the (n+1)-th lines; each line through P between these lines has n points of S on each side.

Also solved by Matthew Hubbard and John Sayer.

Problem for 2002 July

Proposed by Dan Jurca

Suppose n is a positive integer and A_n is the n×n matrix as follows.

An= æ ç ç ç ç ç ç ç ç ç ç ç è 2 1 0 0 ¼ 0 1 2 1 0 ¼ 0 0 1 2 1 ¼ 0 0 0 1 2 ¼ 0 : : : : ··· : 0 0 0 0 ¼ 2 ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø

That is, A_n=(a_ij)_{1 £ i £ n, 1 £ j £ n} where

aij= ì ï ï í ï ï î 2 if i=j, 1 if |i-j|=1, 0 if 2 £ |i-j|.

Compute the determinant det(A_n).

Let d_n=det(A_n); then we find at once d₁=2 and d₂=3. If 3 £ n, then by expanding along column 1 in A_n we find d_n=2d_n-1-d_n-2. Thus 1 £ n Þ d_n=n+1. For this is clear if n=1 or n=2; if 3 £ n, d_n-1=n, and d_n-2=n-1, then by the recursion relation we have d_n=2×n-(n-1)=n+1; hence by induction on n we have 1 £ n Þ d_n=n+1, as asserted.

Also solved by Walt Becker, Christopher Doi, John M. Sayer, and Murray Stokely

Problem for 2002 August

Proposed by Dan Jurca

Suppose K is a field, and V is a vector space over K; a bilinear form on V is a function

b:V×V® K

which is linear (additive and homogeneous) in each ``slot''; i.e., u,v,w Î V and k Î K Þ

b(u+v,w) =b(u,w)+b(v,w), and b(u,v+w)=b(u,v)+b(u,w); and       b(ku,v) =kb(u,v)=b(u,kv).

One finds immediately that for each bilinear form b on V

v Î V Þ b(0,v)=0=b(v,0).

The following is a standard exercise in linear algebra.

Suppose V is a finite-dimensional vector space over the field K, and b:V×V® K is a bilinear form on V; then the following conditions are equivalent.

a.

{u Î V | b(u,v)=0 " v Î V}={0};

b.

{v Î V | b(u,v)=0 " u Î V}={0};

c.

for each basis {v₁,v₂,¼,v_n} of V over K the n×n matrix B=(b_ij)_{1 £ i £ n,1 £ j £ n}, where b_ij=b(v_i,v_j), is nonsingular.

Show that the hypothesis that dim_K(V) < ¥ above is essential. That is, show that if V is an infinite dimensional vector space over the field K, then there exists a bilinear form b:V×V® K such that

{u Î V | b(u,v)=0 " v Î V} ={0}; but   {v Î V | b(u,v)=0 " u Î V} ¹ {0}.

Suppose V is a vector space over the field K, dim_K(V)=¥, and {v_a | a Î A} is a K-basis of V. Thus A is an infinite set and if v Î V, then for each a Î A there exists k_a Î K and there exists a finite subset S_v Ì A such that

i.

å{ k_av_a | a Î A }=v    and

ii.

a Ï S_v Þ k_a=0.

(One can see, using DeMorgan's laws, that the conditions here are complementary.)

The following sketch shows what the matrix B=(b_ab)_{(a,b) Î A×A} where b_ab = b(v_a,v_b) looks like. (Of course without a well-ordering on A the matrix B does not really look like anything.)

B= é ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ë 1 ¼ 0 ¼ ¼ 1 ¼ 0 ¼ ¼ 1 ¼ 0 ¼ ¼ ··· : ¼ 1 1 1 ¼ 0 ¼ 1 1 ¼ ¼ : ··· ¼ ¼ 0 ¼ 1 ¼ ¼ 0 ¼ 1 ¼ ¼ : ¼ ··· ù ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú û

Here the missing entries are all 0's; the a₀-th column is all 0's; and the a₀-th row is all 1's except that the diagonal entry is 0; and each diagonal entry is 1, except of course the one in the a₀-th row and column.

We claim that if u Î V and b(u,v)=0 for each v Î V, then u=0. For suppose that u=å{k_av_a | a Î A}, where a Ï S_u Þ k_a=0. If a₀ Î S_u, then choose b ¹ a₀ such that k_b=0; then b(u,v_b)=0, from which k_a0b(v_a0,v_b)=0, whence k_a0=0. Next, for each a Î S_u, if a ¹ a₀, since b(u,v_a)=0, then k_a0b(v_a0,v_a)+k_a b(v_a,v_a)=0, so that k_a=0 (since k_a0=0 whether a₀ Î S_u or a₀ Ï S_u). Therefore a Î A Þ k_a=0, and this shows u=0. However, it is clear that u Î V Þ b(u,v_a0)=0; and of course v_a0, being an element of a basis, is non-zero.

Thus for this particular bilinear form b, we have

{u Î V | b(u,v) =0 " v Î V}={0}, but va0 Î {v Î V | b(u,v) =0 " u Î V} ¹ {0},

as desired.

Problem for 2002 October

Proposed by Dan Jurca

The following is a variation on a problem which, according to the 2002 September issue of the Canadian mathematics journal Crux Mathematicorum, appeared in one of the St. Petersburg contests, from 1965 to 1984.

Suppose that you have a calculator which may be used to

i.

add any two real numbers;

ii.

subtract any real number from any real number;

iii.

divide any real number by 24;

iv.

raise any real number to the fourth power.

By repeated addition one can compute nx for each positive integer n and real number x; hence one can compute x/2=(12x)/24, x/3=(8x)/24, x/8=(3x)/24 for each real number x. Thus one can use this calculator to divide by 2, 3, and 8. Next, from (x+y)²=x²+2xy+y² one has xy=[(x+y)²-x²-y²]/2, so that if one can compute squares, then one can compute products. Next, from (x+1)³=x³+3x²+3x+1 one finds x²=[(x+1)³-x³-3x-1]/3, so that if one can compute cubes, then one can compute squares. Next, from

(x+1)4 =x4+4x3+6x2+4x+1      and (x-1)4 =x4-4x3+6x2-4x+1

one finds x³=[(x+1)⁴-(x-1)⁴-8x]/8, so that if one can compute fourth powers, then one can compute cubes. Hence if one can compute sums and differences, can divide by 24=4!, and can compute fourth powers, then one can compute products.

We remark that from

(x+1)5 =x5+5x4+10x3+10x2+5x+1      and (x-1)5 =x5-5x4+10x3-10x2+5x-1

one finds x³=[(x+1)⁵+(x-1)⁵-2x⁵-10x]/20, so that if one can compute sums, differences, fifth powers, and can divide by 5!, then one can compute products.

Does this continue?

Problem for 2002 November

Communicated by Matthew Hubbard

Find a polynomial p(x,y) such that

(x,y) Î R2 Þ 0 < p(x,y)

and

inf { p(x,y) | (x,y) Î R2 }=0.

Consider the following polynomial, p.

p(x,y) =x2y2+y2+2xy+1 =y2+(xy+1)2

Obviously "(x,y) Î R²: 0 £ p(x,y); and clearly p(x,y)=0 if and only if both y=0 and xy+1=0, which is impossible, so that

(x,y) Î R2 Þ 0 < p(x,y).

Next, if 0 < e, then

p(  1 Ö e ,- Ö   e   )=e

so that im p=p(R²)={ t Î R | 0 < t }, and therefore

inf { p(x,y) | (x,y) Î R2 }=0.

Problem for 2002 December

Communicated by Dan Jurca

The following problem appears on page 59 of A Course of Modern Analysis by E.T. Whittaker and G.N. Watson.

Show that the series

¥ å n=1   zn-1 (1-zn)(1-zn+1)

is equal to [ 1/((1-z)²)] when |z| < 1 and is equal to [ 1/(z(1-z)²)] when 1 < |z|.

First suppose |z| ¹ 1. We shall show

1 £ N Þ  N å n=1   zn-1 (1-zn)(1-zn+1) =  1-zN (1-z)2(1-zN+1) .

(We take 0⁰=1 here.) First suppose N=1. Then

N å n=1   zn-1 (1-zn)(1-zn+1) =  z1-1 (1-z1)(1-z1+1) =  1 (1-z)(1-z2) =  1-z (1-z)2(1-z2) ,

so the assertion certainly holds if N=1. Next suppose 2 £ N and

N-1 å n=1