Problem for 2007 January

Problem for 2007 February

Problem for 2007 March

Proposed by Dan Jurca

One can define the ``Möbius'' function, m:P®C, from the set P of positive integers to C, the set of complex numbers, as follows.

n Î P Þ m(n)= ì ï ï í ï ï î 1 if n=1 0 if a2|n for some positive integer a (-1)k if n=p1p2¼pk, where the pi are distinct primes

A basic, important, and easily proved result in elementary number theory asserts that

å d|n  m(d)= ì ï í ï î 1 if n=1 0 if 1 < n.

Show that this characterizes the function m; i.e., prove the following proposition.

If f:P®C and

å d|n  f(d)= ì ï í ï î 1 if n=1 0 if 1 < n,

then f=m.

Letting n=1, we find

å d|1  f(d)=f(1)=1,

so that f(1)=m(1). Now suppose that 1 < n and 1 £ d < n Þ f(d)=m(d). Then since, obviously, n|n, we have

å d|n  f(d) =0,   so that, solving for f(n), f(n) =- å d < n and d|n  f(d) =- å d < n and d|n  m(d)   by the inductive hypothesis =m(n),   since  å d|n  m(d)=0,

whence f(n)=m(n). Therefore, by (the strong form of) mathematical induction we have 1 £ n Þ f(n)=m(n), and thus f=m.

Also solved by Grant Morgan and Jean Simutis

Problem for 2007 April

Proposed by Dan Jurca

a.

Suppose

f:[0,1]®R by f(x)= ì ï ï í ï ï î 0 if x=0 xsin  1 x if 0 < x £ 1.

Determine whether the length of the graph of f is finite or infinite.

b.

Suppose

g:[0,1]®R by g(x)= ì ï ï í ï ï î 0 if x=0 x2sin  1 x if 0 < x £ 1.

Determine whether the length of the graph of g is finite or infinite.

a.

The graph of f is of infinite length. For i=0,1,¼ let x_i=2/((2i+1)p) and y_i=f(x_i)=(-1)ⁱx_i. The graph of f is a curve in the x-y plane which contains the points (x_i,y_i), i=0,1,¼; it ``passes through'' (x₀,y₀), then (x₁,y₁), then (x₂,y₂), etc. The length of arc of the portion from (x_i-1,y_i-1) to (x_i,y_i) clearly exceeds |y_i-1|+|y_i|, i=1,2,¼. Thus

0 £ n Þ  ó õ 1 xn+1  Ö   1+(f¢)2   > |y0|+|yn+1|+2 n å i=1  |yi| =  2 p +  2 (2n+3)p +  4 p n å i=1   1 2i+1

and since the series 1/3+1/5+1/7+¼ diverges to ¥,

ó õ 1 0  Ö   1+(f¢)2   = lim a®0+  ó õ 1 a  Ö   1+(f¢)2   =¥,

and the graph of f is of infinite length.

b.

We have

g¢(x) = ì ï í ï î 0 if x=0, 2xsin(1/x)-cos(1/x) if 0 < x £ 1,    so that 0 < x £ 1 Þ  Ö   1+(g¢(x))2   = Ö   1+4x2sin2(1/x)-4xsin(1/x)cos(1/x)+cos2(1/x)   ,   and 0 £ x £ 1 Þ  Ö   1+(g¢(x))2   £ Ö   2+4x2+4x   ,   whence ó õ 1 0  Ö   1+(g¢)2   £ ó õ 1 0  Ö   4x2+4x+2     dx =  1 4 æ è -Ö2+3 Ö   10   -arcsinh(1)+arcsinh(3) ö ø =  1 4 æ ç è 3 Ö   10   -Ö2+ln 3+ Ö 10 1+Ö2 ö ÷ ø » 2.2524230726

so the graph of g is of finite length.

Remark. Numerical integration suggests that the length of the graph of g is approximately 1.9288.

Problem for 2007 May

Communicated by Dan Jurca

The following problem involves a well-known fact, but may make an interesting exercise.

Show that the sequence (x_n)_n=1^¥ where

xn= æ è 1+  1 n ö ø n

strictly increases.

We shall show somewhat more generally that if 0 < a and f:(0,¥)®R by

f(x)= æ è 1+  a x ö ø x

then f strictly increases. For 0 < f and

lnf(x) =xln æ è 1+  a x ö ø =xln æ è  x+a x ö ø ,      so  1 f(x) f¢(x) =ln æ è  x+a x ö ø +x·  x x+a ·  -a x2 =ln æ è  x+a x ö ø -  a x+a

With j:(0,¥)®R by

j(x) =ln æ è  x+a x ö ø -  a x+a ,      we have j¢(x) =  x x+a ·  -a x2 +  a (x+a)2 =  -a2 x(x+a)2 < 0,

so that j strictly decreases. Since

lim 0+  j = ¥   and    lim ¥  j = 0

it follows that 0 < j, and since 0 < f it follows that 0 < f¢ as well. Thus f strictly increases, as asserted.

Also solved by Massoud Malek and John M. Sayer

Problem for 2007 June

Proposed by Dan Jurca

The following problem appears on page 235 of The IMO Compendium.

Let n be a positive integer. Show that

(Ö2+1)n=Öm+ Ö   m-1

for some positive integer m.

If a and b are positive integers, then for each positive integer n there exists a positive integer m such that

(Öa+Öb)n=Öm+ Ö   m-(a-b)n   .

Solution by the proposer

We shall solve for m and from the resulting expression will deduce that m is indeed a positive integer. First, write n=2q+r, where q is a nonnegative integer and r=0 or r=1. Next from

(Öa+Öb)n =Öm + Ö   m-(a-b)n      we have (Öa +Öb)n-Öm = Ö   m-(a-b)n   ,   so by squaring, (Öa+Öb)2n-2(Öa+Öb)nÖm+m =m-(a-b)n,   so Öm =  (Öa+Öb)2n+(a-b)n 2(Öa+Öb)n =  (Öa+Öb)n 2 +  1 2 æ è  a-b Öa+Öb ö ø n   =  (Öa+Öb)n 2 +  1 2 æ è  (Öa-Öb)(Öa+Öb) Öa+Öb ö ø n   =  (Öa+Öb)n 2 +  (Öa-Öb)n 2 =  1 2 n å i=0  æ è n i ö ø (a(n-i)/2bi/2+(-1)ia(n-i)/2bi/2) = ën/2û å i=0  æ è n 2i ö ø a(n-2i)/2bi = ën/2û å i=0  æ è n 2i ö ø an/2-ibi = ën/2û å i=0  æ è n 2i ö ø a(2q+r)/2-ibi =ar/2 q å i=0  æ è n 2i ö ø aq-ibi,   whence m =ar æ è q å i=0  æ è n 2i ö ø aq-ibi ö ø 2   ,   a positive integer.

Problem for 2007 July

Communicated by Dan Jurca

By the repunit R_n one means the integer written in base 10 as 111¼111, the string of n 1's; i.e.,

Rn=  10n-1 9 .

Let S={p | p is a prime number and $n such that p divides R_n}; determine the set S.

Obviously 2 Ï S and 5 Ï S. We show S consists of all other primes. For suppose that p is a prime, p ¹ 2, and p ¹ 5. For each positive integer k we clearly have R_k º r (mod p) for some r Î {0,1,2,¼,p-1}, and since this set is finite there exist positive integers m and n such that m < n and R_n º R_m (mod p). Therefore p|(R_n-R_m). But

Rn-Rm =  10n-1 9 -  10m-1 9 =  10n-1-10m+1 9 =  10n-10m 9 =  10m(10n-m-1) 9 =10m×  10n-m-1 9 =10m×Rn-m

and since p does not divide 10^m, we have p|R_n-m, whence p Î S.

Problem for 2007 August

Communicated by Dan Jurca

The following problem appears on page 158 of The IMO Compendium by Dusan Djuki\'c, Vladimir Jankovi\'c, Ivan Mati\'c, and Nikola Petrovi\'c.

Consider the set Q² of points in R², both of whose coordinates are rational.

a.

Prove that the union of segments with vertices from Q² is the entire set R².

b.

Is the convex hull of Q² (i.e, the smallest convex set in R² that contains Q²) equal to R²?

i.

Show that the assertion of a. is incorrect by exhibiting a point (x,y) Î R² which is not contained in the union of segments each endpoint of which is a point in Q².

ii.

Show that if Á={a Î R | a Ï Q} then the union of segments with endpoints in Á² equals R².

i.

We show that the point (Ö2,Ö3) Î R² is not in a segment each endpoint of which lies in Q². For suppose (a,b) Î Q², (c,d) Î Q², and that (Ö2,Ö3) Î l, where l is the segment from (a,b) to (c,d). Then clearly a ¹ c, else Ö2 = a Î Q; similarly b ¹ d, else Ö3 = b Î Q. Hence with m=(b-d)/(a-c), l is included in the line with equation y-b=m(x-a), so that Ö3 = mÖ2-(ma-b). Now if ma-b=0, then Ö3 = mÖ2; hence Ö3/Ö2 = m=Ö6/2, from which Ö6 = 2m Î Q, which is false, since Ö6 is irrational. But if (ma-b) ¹ 0, then by squaring we find

3=2m2+(ma-b)2-2m(ma-b)Ö2,

and this yields (since m Î Q and m ¹ 0)

Ö2 =  3-2m2-(ma-b)2 -2m(ma-b) Î Q,

another contradiction.

ii.

We shall show that in fact each point (x,y) Î R² is the midpoint of a segment each endpoint of which lies in Á². There are four possibilities, as follows.

1.

x Î Á, y Î Á. Consider the segment from (x-1,y) to (x+1,y).

2.

x Î Á, y Î Q. Consider the segment from (x,y-Ö2) to (x,y+Ö2).

3.

x Î Q, y Î Á. Consider the segment from (x-Ö2,y) to (x+Ö2,y).

4.

x Î Q, y Î Q. Consider the segment from (x-Ö2,y-Ö2) to (x+Ö2,y+Ö2).

Problem for 2007 September

Proposed by Dan Jurca

Dawson's function F is defined by the following integral.

F(x)=e-x2 ó õ x 0  et2dt

Determine whether

ó õ ¥ 0  F  converges; i.e., whether  lim x®¥  ó õ x 0  F  exists.

Solution by the proposer

The integral does not converge. We have by l'Hôpital's rule and the fundamental theorem of calculus

lim x®¥  xF(x) = lim x®¥   x ex2 ó õ x 0  et2dt = lim x®¥  x ó õ x 0  et2dt ex2 = lim x®¥  ó õ x 0  et2dt+xex2 2xex2 = lim x®¥   ex2+ex2+2x2ex2 2ex2+4x2ex2 = lim x®¥   2+2x2 2+4x2    so that lim x®¥  xF(x) =1/2.

Therefore there exists x₀ such that 0 < x₀ and x₀ £ x Þ 1/4 £ xF(x).
It follows that x₀ £ x Þ 1/(4x) £ F(x). Hence x₀ £ x Þ

ó õ x x0   1 4t  dt £ ó õ x x0  F   so that  1 4 (lnx-lnx0) £ ó õ x x0  F   whence lim x®¥  ó õ x 0  F =¥.

Remark. We can now express this another way, as follows. We have

lim x®¥  ó õ x 0  F lnx = lim x®¥   F(x) 1/x = lim x®¥  xF(x) =1/2.

Therefore

ó õ x 0  F ~  1 2 lnx=lnÖx.

That is,

lim x®¥  ó õ x 0  F lnÖx =1.

Problem for 2007 October

Problem for 2007 November

Proposed by Dan Jurca

Since there exists no elementary function F such that F¢(x)=e^x2, one computes approximations of integrals such as

ó õ 10 0  ex2 dx

using some numerical method. Similarly (or otherwise), find an accurate approximation (with at least four significant digits) of the following definite integral.

ó õ 10 0  e2x dx

Solution by the proposer

Suppose 0 < a, 1 £ ab, and

I= ó õ b 0  eeax dx.

(With a=ln2 and b=10 we recover the given problem.)

Proposition 1. 0 £ n Þ

ó õ b 0  eeax dx= é ë  eeax a n å i=1   (i-1)! eiax ù û b 0  +n! ó õ b 0  e-naxeeax dx

Proof.

The equation obviously holds if n=0, so suppose that 1 £ n and

I= é ë  eeax a n-1 å i=1   (i-1)! eiax ù û b 0  +(n-1)! ó õ b 0  e-(n-1)axeeax dx.

Let u=e^-nax/a and dv=e^eax·ae^ax dx; then du=e^-nax·-n dx and v=e^eax. Hence by parts

I = é ë  eeax a n-1 å i=1   (i-1)! eiax ù û b 0  +(n-1)! é ë  eeax·e-nax a ê ê b 0  +n ó õ b 0  e-naxeeax dx ù û = é ë  eeax a n å i=1   (i-1)! eiax ù û b 0  +n! ó õ b 0  e-naxeeax dx,

and the proposition follows by induction on n.

Now we let

An=  eeab a n å i=1   (i-1)! eiab        sn=  e a n å i=1  (i-1)!      and       Rn=n! ó õ b 0  e-naxeeax dx.

Then I=A_n-s_n+R_n, and we show next that I » A_n for some values of n. By this we mean that with

rel errn=  I-An I

one can find a small n for which |rel err_n| < 5×10^-4, for example.

Proposition 2.

1 £ n and   n+2 n e(n+1)ab+1 £ eeab Þ 0 < rel errn <  n!ab e(n-1)ab

Proof.

First we observe that if the conditions on n above hold, then e^(n+1)ab+1 < e^eab, so that (n+1)ab+1 < e^ab, whence nab < e^ab, so that (since 1 £ ab) we have n < e^ab. It follows that 0 £ lnn/a < b.

Now let j:[0,b]®R by j(x)=e^-naxe^eax. Then j(0)=e, j(b)=e^-nabe^eab, and

j¢(x) =(-na+aeax)j(x) =a(eax-n)j(x).

Thus j\searrow in [0,(lnn)/a], j\nearrow in [(lnn)/a,b], so that j_max=max{j(0),j(b)}=max{e,e^-nabe^eab}=e^-nabe^eab; for from n < e^ab we have n < (e^ab-1)/(ab), (since 1 £ ab) so nab < e^ab-1 and nab+1 < e^ab, whence e^nab·e < e^eab, so that e < e^-nabe^eab. It follows that R_n < n!be^-nabe^eab.

We next show that with n as in the hypothesis it follows that 0 £ R_n-s_n. First by an easy induction on n it follows that s_n £ (e/a)·2(n-1)!. Next with u=e^-naxe^-ax/a, dv=e^eaxe^axa dx and by parts again

ó õ b 0  e-naxeeax dx = é ë  e-(n+1)ax a ·eeax ù û b 0  +(n+1) ó õ b 0  e-(n+1)axeeax dx =  e-(n+1)ab·eeab a -  e a +(n+1) ó õ b 0  e-(n+1)axeeax dx;   therefore n! æ è  e-(n+1)ab·eeab a -  e a ö ø < Rn,   and since -(e/a)·2(n-1)! £ -sn   we have n! æ è  e-(n+1)ab·eeab a -  e a ö ø -  e a ·2(n-1)! £ Rn-sn,   so  (n-1)! a (ne-(n+1)ab·eeab-(n+2)e) £ Rn-sn,

and since (n+2)/n·e^(n+1)ab+1 £ e^eab, it follows that 0 £ R_n-s_n. Hence

I-An I =  (An-sn+Rn)-An An-sn+Rn =  Rn-sn An+(Rn-sn)    so that 0 £  I-An I £  Rn An .   But since (obviously)  eeab a ·  1 eab £ An,   we have 0 £  I-An I <  n!be-nabeeab eeab/a·(1/eab) =  n!ab e(n-1)ab ,

proving proposition 2.

Now with a=ln2, b=10, and 1 £ n £ 146 the conditions in the hypothesis of proposition 2 hold; in particular we let n=8. Then I » A₈ with a relative error less than 3×10^-16; hence with at least sixteen significant digits we have

ó õ 10 0  e2x dx » A8 =  eeln2 × 10 ln2 8 å i=1   (i-1)! ei × ln2 × 10 =  e1,024 ln2 × é ë  1 210 +  1 220 +  2 230 +  6 240 +  24 250 +  120 260 +  720 270 +  5,040 280 ù û » 7.35950813976599166¼×10441.

Remark 1. A₁₄₆ approximates the integral with at least 182 significant digits.

Remark 2. The function y: [1,¥)®R by y(x)=(x+2)/x·e^(x+1)ab+1 strictly increases and (obviously) approaches ¥. Therefore there exists a maximum n satisfying the conditions in proposition 2.

Problem for 2007 December