Problem for 2003 January

Proposed by Dan Jurca

Simplify the following expression.

3 æ Ö     4018030018+ Ö 16144565225549080325   + 3 æ Ö     4018030018- Ö 16144565225549080325

Solution by the proposer

Observing that 16144565225549080325=4018030018²+1 and writing x for the value of the given expression, we have

x= 3 æ Ö     u+ Ö u2+1   + 3 æ Ö     u- Ö u2+1

where u=4018030018. Then from (a+b)³=a³+3a²b+3ab²+b³, we have

x3 =u+ Ö   u2+1   +3 3 æ Ö     (u+ Ö   u2+1   )2(u- Ö   u2+1   )   +                      +3 3 æ Ö     (u+ Ö   u2+1   )(u- Ö   u2+1   )2   +u- Ö   u2+1   =2u+3 3 æ Ö     (2u2+1+2u Ö   u2+1   )(u- Ö   u2+1   )   +             3 3 æ Ö     (u+ Ö   u2+1   )(2u2+1-2u Ö   u2+1   )   =¼ =2u+3 é ë 3 æ Ö     -u- Ö u2+1   + 3 æ Ö     -u+ Ö u2+1     ù û =2u-3 é ë 3 æ Ö     u+ Ö u2+1   + 3 æ Ö     u- Ö u2+1     ù û =2u-3x.

Therefore the real number x satisfies the equation x³+3x-2u=0. Since the function f:R®R by f(t)=t³+3t-2u strictly increases on R (0 < 3t²+3=f¢(t)), the equation has a unique real root. When u=4018030018 one finds the unique real root equals 2003; therefore the given expression simplifies to the number 2003.

Also solved by Farid El-Mouchrif and Dangthu Ta

Problem for 2003 February

Communicated by Dan Jurca

Let

N =44444444, A =the sum of the (decimal) digits of N, and B =the sum of the (decimal) digits of A.

What is the sum of the (decimal) digits of B?

Solution by anonymous solver

For each natural number M=å_i=0ⁿd_i10ⁱ (0 £ d_i < 10) we have M º å_i=0ⁿd_i (mod 9) since 10ⁱ º 1 (mod 9) "i Î N. Let N=4444⁴⁴⁴⁴, so if A= sum of digits of N, B= sum of digits of A, and C= sum of digits of B, then N º A º B º C (mod 9). Using Euler's j-function theorem we have N º 7⁴⁴⁴⁴ º 7⁴ º 7 (mod 9) since 4444 º 7 (mod 9), j(9)=6, and 4444 º 4 (mod 6). Now N has 1+ëlog₁₀Nû = 16,211 digits, and so A £ 16,211×9 = 145,899, a 6-digit number, and therefore B £ 6×9 = 54, and consequently B Î {7,16,25,34,43,52}. Thus, the sum of the digits of B is 7.

Remark by Dan Jurca:

Computing N one finds that A=72,601, B=16, so that, finally, C=7, as shown above.

These computations were performed on a desktop PC with a 200 MHz Pentium Pro processor, and the times were as follows: 0.215512 seconds to compute N in base 2³², 0.519401 seconds to convert to decimal, and 0.000719 seconds to add the digits, obtaining A.

Solution also by James Dalton, Kurt Luoto, Farid El Mouchrif, Rosta Farzan, Gagan Sekhon, Michael Thompson

Problem for 2003 March

Proposed by Dan Jurca

Consider the sequence (t_n)_n=1^¥ of positive integers as follows. t₁=1; then we skip the next 1²=1 positive integers, and let t₂=3; then we skip the next 2²=4 positive integers, and let t₃=8; then we skip the next 3²=9 positive integers, and let t₄=18; etc. The following sketch shows the first few t_i.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ¼

Find a formula for the sum

n å i=1  ti

of the first n terms of this sequence.

We have t₁=1, t₂=3, t₃=8, t₄=18, ¼; precisely we have

t1 =1, 2 £ i Þ ti =ti-1+(i-1)2+1.

Eliminating the recursion we find

1 £ i Þ ti=(2i3-3i2+7i)/6.

Therefore

n å i=1  ti =  1 3 n å i=1  i3-  1 2 n å i=1  i2+  7 6 n å i=1  i =  1 3 · é ë  n(n+1) 2 ù û 2   -  1 2 ·  n(n+1)(2n+1) 6 +  7 6 ·  n(n+1) 2 =  (n2+n)2 12 -  (n2+n)(2n+1) 12 +  7(n2+n) 12 =  (n2+n)(n2+n-2n-1+7) 12 =  (n2+n)(n2-n+6) 12 =  n4+5n2+6n 12 .

Communicated by Dan Jurca

The following problem appears in the ``Mathematical Mayhem'' section of the 2003 March issue of the Canadian mathematics journal Crux Mathematicorum.

Five balls numbered 1 to 5 are put into a box. A ball is drawn at random, its number recorded, and the ball is returned to the box. This process is repeated until five numbers have been recorded. If the sum of the numbers is 15, what is the probability that the number 3 was drawn each time?

The probability is clearly 1/N where N is the number of ways to write 15 as the sum of five positive integers, 15=x₁+x₂+x₃+x₄+x₅, where 1 £ i £ 5 Þ 1 £ x_i £ 5. To determine this number N we proceed as follows.

More generally, let N(S,n,m) be the number of ways to write S=x₁+x₂+¼+x_n where each x_i is an integer and 1 £ i £ n Þ 1 £ x_i £ m. Then we have

N(S,n,m)= ì ï ï ï í ï ï ï î 0 if n=1 and S < 1 or m < S 1 if n=1 and 1 £ S £ m m å i=1  N(S-i,n-1,m) if 2 £ n.

(For clearly x₁ equals either 1 or 2 or 3 or ¼ or m.)
Then evaluating N=N(15,5,5) we find N=381; hence the desired probability is 1/381.

The evaluation may be done easily and quickly by filling in the entries of the following table row by row.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1	1	1	1	1	0	0	0	0	0	0
2	0	1	2	3	4	5	4	3	2	1	0	0
3					6	10	15	18	19	18	15	10	6
4											68	80	85	80	68
5																381

Here in each row after row 1 each entry is the sum of the five entries which are in the previous row to the left of the entry being filled.

(The entry in row i and column j here is N(j,i,5); irrelevant entries are left blank.)

Also solved by Richie Hom, P. Horowitz, Yipkei Kwok, Joseph Rios, John Sayer, and Murray Stokely

Problem for 2003 May

Proposed by Dan Jurca

Prove that for each nonnegative integer n

e n+2 < ó õ 1 0  xnex dx <  e n+1 .

Solution by the proposer

Since the exponential function (x® e^x) is increasing we have x < 1 Þ e^x < e¹=e; hence 0 £ x £ 1 Þ xⁿe^x £ xⁿe (equality only if x=0 or x=1); therefore

ó õ 1 0  xnex dx < ó õ 1 0  exn dx   so that ó õ 1 0  xnex dx < e ó õ 1 0  xn dx=  e n+1 .

Next consider j:R®R by j(x)=e^x-ex. Then j¢(x)=e^x-e, so x < 1 Þ j¢(x) < 0 and 1 < x Þ 0 < j¢(x). Thus j\searrow in (-¥,1]; j\nearrow in [1,¥). Hence j_min=j(1)=0, so that x Î R Þ 0 £ e^x-ex. That is, ex £ e^x, with equality if and only if x=1. Therefore for each nonnegative n we have 0 £ x Þ ex·xⁿ £ xⁿe^x, with equality only if x=0 or x=1. It follows that

ó õ 1 0  exn+1 dx < ó õ 1 0  xnex dx   so  e n+2 < ó õ 1 0  xnex dx,

and this together with the inequality above yields

0 £ n Þ   e n+2 < ó õ 1 0  xnex dx <  e n+1 ,

as desired.

Remark. With a little more work one can show

ó õ 1 0  xnex dx=e ¥ å i=1   n!(n+2i-1) (n+2i)!

so that the integral can be computed easily and accurately.

Also solved by Farid El Mouchrif, James Farrell, Yipkei Kwok, Kurt Luoto, Massoud Malek, John M. Sayer, and Dangto Ta

Problem for 2003 June

Proposed by Dan Jurca

Consider the Fibonacci sequence

(fn)n=0¥=(0,1,1,2,3,5,8,13,21,¼).

That is,

fn= ì ï ï í ï ï î 0 if n=0 1 if n=1 fn-2+fn-1 if 2 £ n.

Then let

F(x) = ¥ å n=0  fnxn =f0+f1x+f2x2+f3x3+f4x4+¼ .

a.

For which x does the series above converge?

b.

Find a formula for the function F(x).

c.

Compute F(1/2).

d.

Sketch the graph of F.

Let j = (1+Ö5)/2 and observe that -1/j = (1-Ö5)/2. We recall the following formula.

0 £ n Þ fn=(jn-(-1/j)n)/Ö5

Now obviously 1 < j, so that by the root test the series above converges if |x| < 1/j and diverges if 1/j < |x|. Next we observe that (since 0 < j) f_n/jⁿ=1/Ö5[1-(-1)ⁿ/j²ⁿ] does not converge to 0 as n®¥; similarly, f_n/(-j)ⁿ=1/Ö5[(-1)ⁿ-1/j²ⁿ] does not converge to 0 as n®¥; thus the interval of convergence of the series is precisely (-1/j,1/j). We compute as follows.

xF(x) =f0x+f1x2+f2x3+f3x4+¼ x2F(x) = f0x2+f1x3+f2x4+¼ thus     xF(x)+x2F(x) =f0x+f2x2+f3x3+f4x4+¼ =F(x)-x; hence    F(x) =  x 1-x-x2 .

(One might find it amusing to actually carry out this division.)

Therefore F(1/2)=[(1/2)/(1-1/2-1/4)]=2.

Also solved by Walt Becker, James Farrell, Massoud Malek, and John Sayer

Problem for 2003 July

Communicated by Dan Jurca

Recall that a function j:R®R is additive if

"x,y Î R:   j(x+y)=j(x)+j(y).

The following problem appears on page 36 of Conjecture and Proof by Miklós Laczkovich.

Let f:R®R be a function such that

f æ è  x+y 2 ö ø =  f(x)+f(y) 2

for every x,y Î R. Prove that there is a constant c such that f-c is additive.

Let j:R®R by j(x)=f(x)-f(0). We claim that x Î R Þ j(2x)=2j(x). For

j(x) =j æ è  2x+0 2 ö ø =f æ è  2x+0 2 ö ø -f(0) =  f(2x)+f(0) 2 -f(0) =  f(2x)-f(0)+f(0)-f(0) 2 =  f(2x)-f(0) 2 =  j(2x) 2 so   j(2x) =2j(x).

But then x,y Î R Þ

j(x+y) =j æ è  2x+2y 2 ö ø =f æ è  2x+2y 2 ö ø -f(0) =  f(2x)+f(2y) 2 -f(0) =  f(2x)-f(0)+f(2y)-f(0) 2 =  j(2x)+j(2y) 2 =  2j(x)+2j(y) 2 =j(x)+j(y).

Therefore with c=f(0) the function f-c is additive.

Also solved by Kirk Demlinger, James Farrell, Kurt Luoto, and Massoud Malek

Problem for 2003 August

Proposed by Dan Jurca

It is well-known (and easy to prove) that if 1 £ n, then for each pair A, B of n×n matrices trace(AB)=trace(BA).

Show that if 2 £ n, then there exist n×n matrices A, B, C such that trace(ABC) ¹ trace(ACB).

Let A, B, and C be n×n martices as follows.
(Each matrix entry not explicitly shown is a zero.)

A= æ ç ç ç ç ç è 1 0 ¼ 0 0 ¼ : : ··· ö ÷ ÷ ÷ ÷ ÷ ø    B= æ ç ç ç ç ç è 0 1 ¼ 0 0 ¼ : : ··· ö ÷ ÷ ÷ ÷ ÷ ø    C= æ ç ç ç ç ç è 0 0 ¼ 1 0 ¼ : : ··· ö ÷ ÷ ÷ ÷ ÷ ø

Then one has immediately that AB=B, and BC=A, so that ABC=A, whence trace(ABC) = trace(A)=1; however, AC=O, so that ACB=O, whence trace(ACB) = trace(O)=0, so that trace(ABC) ¹ trace(ACB).

Also solved by James Farrell, Bolin Hsu, Massoud Malek, Anurag Sethi, and Winston Teitler

Problem for 2003 October

Proposed by Dan Jurca

For subsets A and B of some (universal) set S the symmetric difference A\triangle B is defined as follows.

A\triangle B =(AÈB)-(AÇB) ={x Î AÈB | x Ï AÇB}

It is well-known that this is an associative operation on S; i.e., for three subsets A, B, and C of S

A\triangle(B\triangle C)=(A\triangle B)\triangle C.

Find a proof of this associative property which is not too tedious to read.

We observe that A\triangle B=(AÈB)Ç(AÇB)¢, where ¢ is set complement, recall the following notation

P(S) ={A | A Ì S},   the set of subsets of S 2S ={f:S®{0,1} | f is a function},   the set of functions from S to {0,1} A Ì S  Þ cA:S®{0,1} by cA(x)= ì ï í ï î 0 if x Ï A 1 if x Î A , the characteristic function of A,

and observe that c:P(S)®2^S by c(A)=c_A is a bijection. Also one has at once that

cA¢ =1-cA cAÈB =cA+cB-cAcB cAÇB =cAcB   so that cA\triangle B =c(AÈB)Ç(AÇB)¢ =cAÈBc(AÇB)¢ =cAÈB(1-cAÇB) =cAÈB-cAÈBcAÇB =cA+cB-cAcB-(cA+cB-cAcB)cAcB =cA+cB-2·cAcB.

Therefore

cA\triangle(B\triangle C) =cA+cB\triangle C-2·cAcB\triangle C =cA+cB+cC-2·cBcC-2·cA(cB+cC-2·cBcC) =cA+cB+cC-2·cBcC-2·cAcB-2·cAcC+4·cAcBcC =cA+cB-2·cAcB+cC-2·cAcC-2·cBcC+4·cAcBcC =cA+cB-2·cAcB+cC-2(cA+cB-2·cAcB)cC =cA\triangle B+cC-2·cA\triangle BcC =c(A\triangle B)\triangle C,

so that c(A\triangle(B\triangle C))=c((A\triangle B)\triangle C), and since c is one-to-one it follows that A\triangle(B\triangle C)=(A\triangle B)\triangle C, proving associativity of \triangle.

Problem for 2003 November

Communicated by Dan Jurca

Prove that there exists no regular pentagon in the plane such that each vertex of the pentagon has integer coordinates.

Suppose P is a polygon such that each coordinate of each vertex is an integer. Then the area of P is either an integer or 1/2 times an integer. Here are two ways to verify this.

1.

One can use Green's lemma (or the two-dimensional version of Green's theorem, or Green's theorem in the plane) which asserts that if P(x,y), Q(x,y), and the partial derivatives ¶P/¶y and ¶Q/¶x are continuous functions over the closed region R bounded by the curve C, then

ó õ C  (P dx + Q dy)= ó õ ó õ R  æ è  ¶Q ¶x -  ¶P ¶y ö ø  dx dy.

Then with P(x,y)=0 and Q(x,y)=x we have

area of R= ó õ ó õ R  dx dy= ó õ C  x dy.

Now if the vertices of P have coordinates (x₁,y₁), (x₂,y₂), ¼, (x_n,y_n), in order, then with C the curve defined by traversing the edges: (x₁,y₁) to (x₂,y₂) to (x₃,y₃) to ¼ to (x_n,y_n) and back to (x₁,y₁), one finds by evaluating the line integral above that the area A of P is given by

A=  1 2 ê ê n å i=1  (xiyi+1-xi+1yi) ê ê ,   where (xn+1,yn+1)=(x1,y1).

Therefore if each x_i is an integer and each y_i is an integer, it follows that 2A is an integer.

2.

One can use Pick's theorem: Suppose that P is a polygon each vertex of which is an integer lattice point. Assume there are I lattice points in the interior of P and B lattice points on the boundary of P. Then the area of P equals I+B/2-1. (See http://www.cut-the-knot.org/ctk/Pick_proof.shtml). Thus twice this area is an integer.

Next one finds that the area of a regular n-gon with side s is given by

A=  ns2 4 cotp/n.

Now if a regular n-gon has vertices with rational coordinates, then clearly the length of a side, s, is the square root of a rational number, so that s² is a rational number, and the area is a rational multiple of cotp/n. In the case n=5 we have

cot  p 5 = Ö 25+10Ö5 5 ,

which is irrational (else its square is rational, so that Ö5 is rational). Therefore if P is a regular pentagon and the length of a side of P is rational, then the area of P is irrational.

It follows that no regular pentagon has vertices with rational coordinates; in particular, no regular pentagon has vertices with integer coordinates.

Also solved by Kurt Luoto

Problem for 2003 December

Suppose that k is a real number, 1 < k, and f:\Rⁿ®\Rⁿ is a surjection with the following property.

x Î \Rn and y Î \Rn Þ k·||x-y|| £ ||f(x)-f(y)||

Show that there exists a unique fixed point of f.

First we show that f is injective. For if f(x)=f(y), then k·||x-y|| £ ||f(x)-f(y)||=||0||=0, so that ||x-y||=0, whence x=y. Now since f is injective and surjective, it follows that f is bijective; hence there exists a unique inverse, say g:\Rⁿ®\Rⁿ, of f. We next show that g is a contraction. For if x Î \Rⁿ and y Î \Rⁿ, then if g(x)=u and g(y)=v, then f(u)=x and f(v)=y; hence k·||g(x)-g(y)||=k·||u-v|| £ ||f(u)-f(v)||=||x-y||, so that ||g(x)-g(y)|| £ 1/k·||x-y||, and 1/k is a constant less than 1. Hence g is a contraction. Since \Rⁿ is a complete metric space, it follows from the Banach contraction theorem that there exists a (unique) fixed point, say p, of g. But if g(p)=p, then f(g(p))=f(p), so that (since f°g=id_\Rⁿ) f(p)=p. Thus there exists a fixed point of f. Uniqueness follows at once, since if f(p₁)=p₁ and f(p₂)=p₂, then k·||p₁-p₂|| £ ||f(p₁)-f(p₂)||=||p₁-p₂|| so (k-1)||p₁-p₂||=0; since k ¹ 1, it follows that ||p₁-p₂||=0, so that, finally, p₁=p₂.

Thus there exists a unique fixed point of f.

Also solved by Massoud Malek and John Sayer