Monday, November 27, 2006

Knuth's Lecture

I was going through Knuth's lectures in which he solves 5 problems that have not yet been solved.

First problem:
Monotonic squares: Find all positive integers n such that the decimal digits of n and
n2 are both in nondecreasing order from left to right

While solving this problem, Anil Gangolli pointed out
(6(m)7)2=4(m+1)8(m+1)9

where a(m) is series of a digits (something like Kleene's operator)
eg 3(5) is 33333.

Here is proof for above statement using mathematical induction:

Given: (6(m)7)2=4(m+1)8(m+1)9
TO prove:(6(m+1)7)2=4(m+2)8(m+1)9

Take lhs:(6(m+1)7)2

=(6(m)7+60(m+1))2

so i am now squaring
applying (a+b)2=a2+b2+2ab

= (6(m)7)2 + (60(m+1))2 + 2.6(m)7.60(m+1)

= 4(m+1)8(m)9 + 360(2m+2) +80(m)40(m+1)

Now this can be simplified as

4(m) 4 8(m) 9
8 0(m) 4 0(m) 0
36 0(m) 0 0(m) 0
Adding three equations gives us

44 4(m) 8 8(m) 9

Final equation is

4(m+2) 8(m+1) 9

Hence proved

No comments: