Problem for 2005 January

Proposed by Dan Jurca

By a power we mean a real number p of the form p=a^b where

·

a is a positive integer;

·

b is an integer; and

·

2 £ b.

Suppose x is a real number and 1 £ x.

Then 1 £ a £ ëÖxû Þ a² £ x, so that ëÖxû £ P(x).
Next, if 2 £ a and a^b £ x, then blog₂a £ log₂x, so, since 1 £ log₂ a, we must have b £ log₂x/log₂a £ log₂x. It follows that there is no b-th power (other than 1^b) less than or equal to x if ëlog₂xû < b. Also, a^b £ x Þ a £ x^1/b. Therefore the number of b-th powers less than or equal to x is bounded by x^1/b. Hence

P(x) £ x1/2+x1/3+x1/4+¼+x1/ëlog2xû =Öx+(x1/3+x1/4+¼+x1/ëlog2xû) £ Öx+(x1/3+x1/3+¼+x1/3) =Öx+(ëlog2xû-2)·x1/3 £ Öx+log2x·x1/3.

Therefore

ëÖxû £ P(x) £ Öx+log2 x·x1/3,   whence  ëÖxû Öx £  P(x) Öx £ 1+  log2x·x1/3 Öx ,   so  ëÖxû Öx £  P(x) Öx £ 1+  log2x x1/6 .

From the ``squeeze theorem'' and l'Hôpital's rule it follows that

lim x®¥   P(x) Öx =1.

Remark. A more detailed analysis shows

1 £ x Þ p(x)=1- ëlog2xû å r=2  m(r)(ëx1/rû-1)

where m is the Möbius function.

Problem for 2005 February

Communicated by Dan Jurca

Show that there do not exist rational numbers x and y such that x²+y²=11.

We shall prove the more general result that if n is a positive integer and n º 3(mod 4), then there do not exist rational numbers x and y such that x²+y²=n. Assuming otherwise leads to a contradiction as follows. For there are sixteen possibilities for the pair of rational numbers: even/even and even/even, even/even and even/odd, etc., and if we suppose that each of x and y has been reduced to lowest terms, then there are only nine such possibilities. The six cases x= even/odd and y= even/odd, x= even/odd and y= odd/even, x= odd/even and y= even/odd, x= odd/even and y= odd/odd, x= odd/odd and y= odd/even, and x= odd/odd and y= odd/odd are all eliminated condidering parity. (We cannot have an even number equal to an odd number.) Consider the case x= even/odd and y= odd/odd. Then, squaring, we have even² odd²+odd² odd²=odd² odd²×n. But since each even number squared is an even number, and each odd number squared is odd, the left side here is congruent to 1 (mod 4), and the right side is congruent to 3. Of course the same holds for x= odd/odd and y= even/odd. Therefore there is but one remaining case: x= odd/even and y= odd/even. Thus there exist integers a,b,c,d,e,a, and g such that 1 £ a £ g and

é ë  2a+1 2a(2b+1) ù û 2   + é ë  2c+1 2g(2d+1) ù û 2   =4e+3,   so 22g(2a+1)2(2d+1)2+22a(2b+1)2(2c+1)2 =22(a+g)(2b+1)2(2d+1)2(4e+3),   so 22(g-a)(2a+1)2(2d+1)2+(2b+1)2(2c+1)2 =22g(2b+1)2(2d+1)2(4e+3),   whence a =g,   so (2a+1)2(2d+1)2+(2b+1)2(2c+1)2 =4g×an odd integer,

but here the left side is congruent to 2 (mod 4) and the right side is congruent to 0 (mod 4).

Generalization also solved by Massoud Malek

Problem for 2005 March

Communicated by Dan Jurca

Find the value of the following limit.

lim n®¥  é ë  n (n+1)2 +  n (n+2)2 +  n (n+3)2 +¼+  n (2n)2 ù û

Solution by Dan Jurca

The function f:(0,¥)®R by f(x)=1/x² strictly decreases, so that

2 £ k Þ  ó õ k+1 k   1 x2  dx <  1 k2 < ó õ k k-1   1 x2  dx;

hence by summing we find

1 £ n Þ  ó õ 2n+1 n+1   1 x2  dx <  1 (n+1)2 +¼+  1 (2n)2 < ó õ 2n n   1 x2  dx   so that  1 n+1 -  1 2n+1 <  1 (n+1)2 +¼+  1 (2n)2 <  1 n -  1 2n       from which  n 2n2+3n+1 <  1 (n+1)2 +¼+  1 (2n)2 <  1 2n ;hence 1 £ n Þ   n2 2n2+3n+1 <  n (n+1)2 +¼+  n (2n)2 <  1 2 ,

so that by the squeeze theorem

lim n®¥  é ë  n (n+1)2 +  n (n+2)2 +  n (n+3)2 +¼+  n (2n)2 ù û =  1 2 .

Also solved by:

Jan van Delden (The Netherlands), Dennis Eichhorn, Massoud Malek, and Bill Nico

Problem for 2005 April

Communicated by Dan Jurca

Prove that for each positive integer m there exists an integer solution x of the following congruence.

(x2-5)(x2-401)(x2-2005) º 0  (mod m)

Solution by Gagan Sekhon and an anonymous solver, edited by Dan Jurca

We prove the somewhat more general result: if u and v are distinct odd primes, and v º 1 (mod 8), and v is a quadratic residue (mod u), then for each positive integer m there exists an integer x such that (x²-u)(x²-v)(x²-uv) º 0 (mod m). (By the law of quadratic reciprocity it follows that also u is a quadratic residue (mod v).) This will certainly prove the assertion above, since 5 and 401 are distinct odd primes, 401=50×8+1, 2005=5×401, and 1² º 401 (mod 5). (Also 178² º 5 (mod 401).)

Reference: Ivan Niven and H.S.Zuckerman, An Introduction to the Theory of Numbers, 4th edition, sections 2.3, 2.5, 2.6, and 3.2.

Our proof consists of the following steps.

1.

We show that for each positive integer r there exists a positive integer x such that

(x²-u)(x²-v)(x²-uv) º 0 (mod 2^r).

2.

We show that for each odd prime p there exists a positive integer x such that

(x²-u)(x²-v)(x²-uv) º 0 (mod p).

3.

We show that for each odd prime p and each positive integer r there exists a positive integer x such that (x²-u)(x²-v)(x²-uv) º 0 (mod p^r).

4.

Finally, by the Chinese remainder theorem it will follow that for each positive integer m there exists a positive integer x such that (x²-u)(x²-v)(x²-uv) º 0 (mod m).

1.

We shall use the following lemma and its corollary.

Lemma. Suppose that e is an even integer, and r is a nonnegative integer; then there exists a nonnegative integer i such that 2^r|(i²+i-e).

Proof.

We shall use induction on r, the assertion being clear if r=0 or if r=1, since then 2^r|(0²+0-e), as e is even. Now suppose 2 £ r and 2^r-1|(j²+j-e), say (j²+j-e)=2^r-1·n. Then let

i= ì ï í ï î j+2r if n is even, j+2r-1 if n is odd.

Then if n is even, say n=2m, we find

i2+i-e =(j+2r)2+(j+2r)-e =(j2+j-e)+2r(2j+2r+1) =2r-1·n+2r(2j+2r+1) =2r-1·2m+2r(2j+2r+1) =2r(m+2j+2r+1);

and if n is odd, say n=2m+1, we find

i2+i-e =(j+2r-1)2+(j+2r-1)-e =(j2+j-e)+2r-1(2j+2r-1+1) =2r-1·n+2r-1(2j+2r-1+1) =2r-1(2m+1+2j+2r-1+1) =2r(m+j+2r-2+1);

so that in either case 2^r|(i²+i-e). Thus the lemma follows by induction on r.

Corollary. If q º 1 (mod 8), and r is a nonnegative integer, then there exists an integer x such that x²-q º 0 (mod 2^r).

Proof.

If r=0, then any integer x will do; if r=1, then any odd x will do. Suppose 2 £ r. Then if q=8s+1, there exists an integer i such that 2^r-2|(i²+i-2s). With x=2i+1 we have x²-q=4i²+4i+1-8s-1=4(i²+i-2s), which is clearly divisible by 2^r, so that x²-q º 0 (mod 2^r).

Since by hypothesis v º 1 (mod 8), this completes step 1.

2.

The assertion in step 2 follows at once if p=u or p=v, so suppose p ¹ u and p ¹ v.

Recall the Legendre symbol where p is an odd prime and a is relatively prime to p:

æ è  a p ö ø = ì ï í ï î 1 if a is a quadratic residue mod p, -1 if a is not a quadratic residue mod p,

and the relation

æ è  a p ö ø æ è  b p ö ø = æ è  ab p ö ø .

Each of these equals 1 or -1, so with a=u and b=v at least one of them equals 1, completing step 2.

3.

We shall use this lemma, proved using the method in section 2.6 of the text cited above.

Lemma. Suppose p is an odd prime, p does not divide w, and a²-w º 0 (mod p). Then for each positive integer r there exists an integer x such that x²-w º 0 (mod p^r).

Proof.

We shall use induction on r, the case r=1 being given in the hypothesis. Suppose 2 £ r and b²-w º 0 (mod p^r-1), say b²-w=q·p^r-1. Since p does not divide w, it follows that p does not divide b; and of course p does not divide 2. Therefore, since Z_p is a field, there exists an integer c such that 2b·c º 1 (mod p), say 2b·c=d·p+1. Then with t=-q·c we have

(b+tpr-1)2-w =b2+2btpr-1+t2p2r-2-w =(b2-w)+2btpr-1+(t2pr-2)pr =qpr-1+2btpr-1+(t2pr-2)pr =(q+2b·t)pr-1+(t2pr-2)pr =(q+2b·-qc)pr-1+(t2pr-2)pr =q(1-2bc)pr-1+(t2pr-2)pr =q(1-dp-1)pr-1+(t2pr-2)pr =(-dq+t2pr-2)pr,

whence with x=b+tp^r-1 we have x²-w º 0 (mod p^r), and the lemma follows from induction on r.

Now if p=u we can use this lemma and the fact that v is a quadratic residue (mod u) to deduce that for each positive integer r there exists an integer x such that x²-v º 0 (mod p^r); and similarly in the case p=v. In case p ¹ u and p ¹ v we use the fact that at least one of u, v, uv is a quadratic residue (mod p), proved in step 2, and hence for each positive integer r there exists x such that (x²-u)(x²-v)(x²-uv) º 0 (mod p^r). This completes step 3.

4.

Now suppose the positive integer m=p₁^e₁×p₂^e₂×¼×p_k^e_k where the p_i are distinct primes and the e_i are positive integers. By steps 1 and 3 for each i, 1 £ i £ k, there exists x_i such that

(x_i²-u)(x_i²-v)(x_i²-uv) º 0 (mod p_i^e_i). By the Chinese remainder theorem there exists an integer x such that

x º x1 (mod p1e1)   and x º x2 (mod p2e2)   and : x º xk (mod pkek);

clearly for this x we have

(x2-u)(x2-v)(x2-uv) º 0 (mod m),

as desired.

Problem for 2005 May

Proposed by Dan Jurca

Suppose f:[-1,1)®R as follows.

f(x)=   æ Ö  1+x 1-x

Write the Maclaurin series for f(x).

We have

f(x) =1·   æ Ö  1+x 1-x   =   æ Ö  1+x 1+x   ·   æ Ö  1+x 1-x   =(1+x)·  1 Ö 1-x2 =(1+x)·  1 Ö 1-u ,

if -1 < x < 1 and u=x². Now with j(u)=(1-u)^-1/₂, we have, by an easy induction on n, that

0 £ n Þ j(n)(u) =  (2n)! 22nn! (1-u)-(2n+1)/2,   so that 0 £ n Þ j(n)(0) =  (2n)! 22nn! .

Therefore

1 Ö 1-u = ¥ å n=0   (2n)! 22nn!n! un,   so that -1 < x < 1 Þ   1 Ö 1-x2 = ¥ å n=0   1 4n æ è 2n n x2n,   whence -1 < x < 1 Þ f(x) =(1+x) ¥ å n=0   1 4n æ è 2n n x2n = ¥ å n=0  anxn   where an =  1 4ën/2û æ è 2ën/2û ën/2û .

Since

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

the series above is valid for x=-1 also.

Problem for 2005 June

Communicated by Dan Jurca

On page 15 of An Introduction to Modern Cosmology by Andrew Liddle appears the following integral.

ó õ ¥ 0   y3 dy ey-1

The author asserts, ``The integral is not particularly easy to compute, but you might like to try it as a challenge. The answer is p⁴/15,¼ ''. Thus, the problem becomes the following: Prove

ó õ ¥ 0   y3 dy ey-1 =  p4 15 .

Solution

The following is taken from pages 59 and 60 of Gamma by Julian Havil.

We have

G(x)= ó õ ¥ 0  tx-1e-t dt   for x > 0

and make the change of variable t=ru to get

G(x)= ó õ ¥ 0  (ru)x-1e-rur du=rx ó õ ¥ 0  ux-1e-ru du.

Hence

1 rx =  1 G(x) ó õ ¥ 0  ux-1e-ru du

and

z(x) = ¥ å r=1   1 rx =  1 G(x) ¥ å r=1  ó õ ¥ 0  ux-1e-ru du =  1 G(x) ó õ ¥ 0  ux-1 ¥ å r=1  e-ru du,

having pushed the sigma through the integral, and summing the infinite geometric series results in

z(x)=  1 G(x) ó õ ¥ 0  ux-1  e-u 1-e-u  du

so we get ``a beautiful formula".

z(x)G(x)= ó õ ¥ 0   ux-1 eu-1  du

which is valid for x Ï {¼,-2,-1,0,1}; ¼ .

¼¼¼¼¼¼¼¼¼¼

Since z(4)=p⁴/90 and G(4)=3!=6 we therefore have (with x=4)

ó õ ¥ 0   y3 dy ey-1 =  p4 15 .

Also solved by Jan van Delden and Massoud Malek

Problem for 2005 July

Communicated by Dan Jurca

Suppose that a, b, and c are real numbers; evaluate the following limit.

lim t®0  ln æ è  1 t ó õ t 0  (1+asinbx)c/x dx ö ø

Solution by Dan Jurca

Using continuity of the natural logarithm function, l Hôpital's rule, and the fundamental theorem of calculus we find

lim t®0  ln æ è  1 t ó õ t 0  (1+asinbx)c/x dx ö ø = ln lim t®0  ó õ t 0  (1+asinbx)c/x dx t =ln lim t®0   d dt ó õ t 0  (1+asinbx)c/x dx  d dt  t =ln lim t®0   (1+asinbt)c/t 1 = lim t®0  ln((1+asinbt)c/t) = lim t®0   c t ln(1+asinbt) =c lim t®0   ln(1+asinbt) t =c lim t®0   d dt ln(1+asinbt)  d dt  t =c lim t®0   1 1+asinbt ·abcosbt 1 =c lim t®0   abcosbt 1+asinbt =c·ab =abc.

Problem for 2005 August

Communicated by Dan Jurca

According to the Hungarian Problem Book II the following problem appeared as number 3 in the 1911 Eötvös competition.

Prove that 3ⁿ+1 is not divisible by 2ⁿ for any integer n > 1.

We shall show that if n is even, then 3ⁿ+1 equals 2 times an odd integer; and if n is odd, then 3ⁿ+1 equals 4 times an odd integer. Precisely, we define integer sequences (a_k)_k=0^¥ and (b_k)_k=0^¥ as follows:

a0 =0; 1 £ k Þ ak =9ak-1+2 0 £ k Þ 32k+1 =2(2ak+1)       b0 =0; 1 £ k Þ bk =9bk-1+3,      and claim 0 £ k Þ 32k+1+1 =4(2bk+1).

For we have

30+1 =1+1=2=2×1 = 2×(2·0+1)=2(2a0+1),   and 31+1 =3+1=4=4×1 = 4×(2·0+1)=4(2b0+1).

Next, if 1 £ k, and

32k-2+1 =2(2ak-1+1),   then 32k-2     =4ak-1+1,   so 32k        =36ak-1+9,   and 32k  +1 =36ak-1+10 =2[18ak-1+5] =2[2(9ak-1+2)+1] =2(2ak+1)                    32k-1+1 =4(2bk-1+1),   then 32k-1     =8bk-1+3,   so 32k+1     =72bk-1+27,   and 32k+1+1 =72bk-1+28 =4(18bk-1+7) =4[2(9bk-1+3)+1] =4(2bk+1),

whence the claims follow by induction on k.

It follows at once that 2 £ n Þ 2ⁿ does not divide 3ⁿ+1.

Also solved by Kelly Hubble.

Problem for 2005 September

Problem for 2005 October

The following puzzle welcomes our new faculty member.

It seems that Professor Gandhi needs to be added to the list of MCS faculty members. What number should be listed next to her name?

Bansiya 81 Christianson 138 Frey 65 Hann 61 Keller 99 Merris 83 Reiter 105 Simon 57 Yang 51 Billard 107 Daley 73 Holz 80 Lippman 90 Morgan 88 Roby 49 Smith 85 Yu 14 Brown 55 Doering 93 Glass 56 Johnson 87 Malek 82 Nico 34 Roohparvar 125 Thibault 145 Callahan 121 Ertaul 100 Grewe 75 Jurca 54 Marut 81 Ouyang 67 Sagahyroon 125 Wolitzer 130

Problem for 2005 November

Problem for 2005 December

Proposed by Jennifer Jean Jurca

Suppose that n is a positive integer, and n married couples attend a party. Naturally there is some handshaking going on, although no person shakes hands with herself or himself, or with her or his spouse. One woman decides to find out how many hands each person has shaken, so she has each person-excluding herself-write down the number of hands she or he has shaken. Unfortunately, no person wrote down a name. However, she observes that each number is a nonnegative integer strictly less than 2n-1, and no number occurs more than once. She asks how many hands her husband has shaken.

Can you help her?

Her husband shook n-1 hands.

This is immediate in the case n=1, and we use induction to show the same if 1 < n. So suppose that 1 < n, and that at any party as in the problem statement with n-1 couples the husband shook n-2 hands. For convenience let Q be the woman asking the question, and for each person P at the party, suppose that P¢ is the spouse of P; thus Q asks how many hands Q¢ has shaken. Let X be the person who shook the greatest number of hands; i.e., X is the person who shook 2n-2 hands (and wrote 2n-2). Thus X is not Q, since X wrote something, but Q did not. We claim that X¢ shook 0 hands (and wrote 0). For there were 2n persons at the party but X shook the hand of neither X nor X¢, so must have shaken the hand of each of the 2n-2 persons other than X or X¢; it follows that each person other than X or X¢ shook at least one hand, so each person other than X or X¢ (and other than Q) wrote a number different from 0. Hence the person who wrote 0 must be X¢.

Now suppose that X and X¢ are excused from the party, they take the numbers (0 and 2n-2) which they have written, and each other number is decremented by 1 to the value it would have been had X and X¢ not been in attendance but all other hand-shaking had been as before. Thus the 1 becomes 0, the 2 becomes 1, etc. The situation now is precisely what it would have been if only n-1 couples had attended the party originally. Therefore, by the inductive hypothesis, Q¢ shook n-2 hands of the 2n-2 remaining persons (and wrote n-2). Now recalling X and X¢ we see that Q¢ shook n-1 hands, as asserted.

Also solved by Massoud Malek and Victor Manjarrez.