Department of Math and Computer Science
Problems of the Month 1999

Communicated by Dan Jurca

Suppose that n is a positive integer, and that A is an n×n matrix with the following two properties:

i.

each entry a_ij of A is an integer; and

ii.

in each row and each column of A there is exactly one odd number.

Proposed by Professor Emeritus Victor Manjarrez

Prove that if A is a finite subset of C, the set of complex numbers, and if

êê å a Î A  a êê = å a Î A  |a|,

then for each subset B of A

êê å b Î B  b êê = å b Î B  |b|.

Solution by the proposer

If C=A\B, then

å a Î A  |a| = êê å a Î A  a êê = êê å b Î B  b +  å c Î C  c êê £ êê å b Î B  b êê  +  êê å c Î C  c êê £ å b Î B  |b| +  êê å c Î C  c êê £ å b Î B  |b| +  å c Î C  |c| = å a Î A  |a|.

It follows that all these are equal, so that

êê å b Î B  b êê  +  êê å c Î C  c êê = å b Î B  |b| +  êê å c Î C  c êê ,

whence |å_{b Î B}b|=å_{b Î B}|b|, as asserted.

Proposed by Professor Massoud Malek

Communicated by Dan Jurca

Suppose 2 £ n; find the inverse of the following n×n matrix.

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

Communicated by Dan Jurca

Determine whether

lim n®¥     n 2n nå k=1   2k k

exists; and, if so, determine the limit.

Proposed by Dan Jurca

Let N={1,2,3,¼}, the set of natural numbers, and P={2,3,5,7,11,¼}, the set of prime numbers. For each subset S Ì P let

N(S)={n Î N  êê  p Î P and p|n Þ p Î S}.

Equivalently,

N(S)={ nÕ i=1  piki  êê  0 £ n, pi Î S, and 0 £ ki}.

Thus N(S) is the set of positive integers the only prime divisors of which are in S. Thus, for example, S Ì P Þ 1 Î N(S), even if S=Æ. Again,

N({2,3})={1,2,3,4,6,8,9,12,16,18,24,27,32,36,¼}.

(*)

1.

Compute

R({2,3})= å n Î N({2,3})   1 n .

I.e., determine the sum of the reciprocals of the integers in the set (*).

2.

Show that if S is finite, then

R(S)= å n Î N(S)   1 n < ¥;

that is, if S is a finite subset of P, then the sum of the reciprocals of all the positive integers whose only prime divisors are in S exists.

(Since å_n=1^¥1/_n diverges, this shows that P is infinite.)

3.

Find a formula for R(S), where S Ì P and S is finite.

Remark-It can be shown that there exists an infinite S (and hence uncountably many infinite S) such that R(S) < ¥.

Suppose that two triangles have the same area and also have the same perimeter. Does it follow that the triangles are congruent?

If so, give a proof; otherwise, give a counterexample.

We observe that

122+352 =144+1225 =1369 =372,      and 202+212 =400+441 =841 =292;

so that the isosceles triangle with base 24 and equal sides 37 has area 1/2×24×35 = 420 and perimeter 24+37+37=24+74=98; similarly the isosceles triangle with base 40 and equal sides 29 has area 1/2×40×21 = 420 and perimeter 40+29+29=40+58=98. The triangles are not congruent.

Proposed by Dan Jurca

The Fibonacci sequence

(Fn)n=0¥=(0,1,1,2,3,5,8,13,21,34,55,¼)

may be defined as follows.

F0 =0; F1 =1; 2 £ n Þ Fn =Fn-2+Fn-1.

1.

Find the sum of the first n terms of (F_i)_i=0^¥; i.e., evaluate

n-1å i=0  Fi=F0+F1+¼+Fn-1.

2.

Find the sum of the first n terms of (F_i²)_i=0^¥; i.e., evaluate

n-1å i=0  Fi2=F02+F12+¼+Fn-12.

Proposed by Dan Jurca

It is well-known that the set of finite subsets of the set

N={1,2,3,4,5,¼}

of natural numbers (positive integers) is denumerable; hence these subsets can be listed in an infinite sequence. Design an algorithm (or write a computer program) which has the following two properties.

1.

If S is a finite subset of N, then the algorithm (or program) will eventually display S.

2.

No finite subset of N is displayed more than once.

Communicated by Dan Jurca

In the right triangle sketched above the altitude perpendicular to the hypotenuse has length h. Express the length of the hypotenuse c as a function of the perimeter (and h).

Proposed by Dan Jurca

Part a. here is problem 1978 from the 1994 October issue of Crux Mathematicorum.

a.

An experimenter E tosses a fair coin until the coin comes up heads for the first time, and counts that exactly k tosses were made; E then chooses randomly an integer from 1 to k. What is the probability that E chooses the number 1?

b.

E begins anew, but now tosses until the coin comes up heads for the second time, and counts that exactly k tosses were made; again E chooses randomly an integer from 1 to k. What is the probability that E chooses the number 1?

c.

Generalize. Suppose that n is a positive integer; suppose that E tosses a fair coin until it comes up heads for the n-th time, and E observes that exactly k tosses were made; again E chooses randomly an integer from 1 to k. As a function of n what is the probability P_n that E chooses the number 1?

The following is a solution of part c. Parts a. and b. are special cases.

Suppose that 1 £ n. If the coin comes up heads for the n-th time on the k-th toss, then in the first k-1 tosses there were exactly n-1 heads and hence k-n tails. The number of sequences consisting of n-1 heads and k-n tails is given by the following expression.

æè k-1 n-1 öø

Thus the probability that the coin comes up heads for the n-th time on the k-th toss is

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

so that the probability that the coin comes up heads for the n-th time on the k-th toss and that E chooses the number 1 is

æè k-1 n-1 öø æè  1 2 öø k   ×  1 k ;

so that the probability that E chooses the number 1 is

Pn= ¥å k=n  æè k-1 n-1 öø  1 k æè  1 2 öø k   .

We next compute this sum. First we observe that

Pn= ¥å i=0  æè n-1+i n-1 öø  1 n+i æè  1 2 öø n+i   .

Now consider

fn(x)= ¥å i=0  æè n-1+i n-1 öø xn-1+i

and observe that

óõ 1/2 0  fn= ¥å i=0  æè n-1+i n-1 öø  1 n+i xn+i êê 1/2 0

so that

Pn= óõ 1/2 0  fn.

Now it is well-known [1, page 199] that

¥å i=0  æè m+i m öø zi=  1 (1-z)m+1 ,

so that

fn(x)=  xn-1 (1-x)n

Therefore

Pn= óõ 1/2 0   xn-1 (1-x)n dx,      1 £ n.

This integral is easily computed. We have

P1= óõ 1/2 0   1 1-x dx=ln2,

and if 2 £ n, then

u=xn-1, dv=  dx (1-x)n  Þ du=(n-1)xn-2dx, v=  1 n-1  1 (1-x)n-1

so that

2 £ n Þ Pn =  1 n-1  xn-1 (1-x)n-1 êê 1/2 0  - óõ 1/2 0   xn-2 (1-x)n-1 dx =  1 n-1 -Pn-1.

To eliminate the recursion here we write A₀=0, and

1 £ n Þ An=1-  1 2 +  1 3 -  1 4 +-¼+  (-1)n-1 n ,

the n-th partial sum of the alternating harmonic series. Then one easily proves by induction that

1 £ n Þ Pn=(-1)n(An-1-ln2).

Now writing H_n=1+1/2+1/3+1/4+¼+1/n, the n-th partial sum of the harmonic series, we have at once A_n=H_n-H_ën/2û. Since it is known [1, page 264] that

1 £ n Þ Hn=lnn+g+  1 2n -  1 12n2 +  en 120n4 ,   0 < en < 1,   g = 0.5772156649¼,

we can, after some tedious but straightforward calculation, deduce, for example, that

Pn ~  1 2n ;  i.e.,  lim n®¥   Pn 1/(2n) =1,

which probably agrees well with what one would expect. That is, one might expect that heads will turn up for the n-th time after about 2n tosses, so that for large n we expect k to be about 2n; hence the probability of choosing the number 1 is approximately 1/(2n).

[1]: Concrete Mathematics, by Graham, Knuth, and Patashnik

One other solution was received, in which the solver considered the case of an unfair coin as well. Unfortunately, this solution was misplaced. It is hoped that the solver will resubmit the solution.