Problem Set 8 Solutions

Problem 2

a)

One posible injection from the unit line to the unit sphere is f(x) = (cos(x), sin(x)), where f(x) maps onto RxR. This gives us an arc of length 1 along the surface of the sphere.

b)

One posible injection from the unit spere to the unit line is as follows.

The unit sphere in sperical coordinates (r, theta, phi) is r = 1, phi = [-pi/2,pi/2], and theta = [0,2pi).
Define p = phi/2pi + 1/4 = [0,1/2] and define t = theta / 2pi = [0,1).
Let the decimal expansion of p be 0 . p1 p2 p3 p4 p5 ...
Let the decimal expansion of t be 0 . t1 t2 t3 t4 t5 ...
Finaly, define f(r, theta, phi) = x = 0 . t1 p1 t2 p2 t3 p3 ...

c)

Lemme 8.2.c.1 : f(x) is a bijection on the real numbers which maps [0,1) to [0,1].
Let {r0, r1, r2, r3, ...} be any infinate set of real numbers in [0,1).
Define f(x) = {
1, if x = r0
r(n-1), if x = r(n>0)
x, otherwise }

Proof : Map the unit line [0,1] to [-1,1] by multiplying by 2 and subtracting 1. Let the decimal expansion of x on [-1,1] be +- x0 . x1 x2 x3 ...
Define p = +- x0 . x2 x4 x6 ... and t = 0 . x1 x3 x5 ...
Note that when p = +- 1.0, t = 0.
Define phi = pi/2 * p.
Define t' as t mapped from [0,1) to [0,1] by lemme 8.2.c.1.
Define theta = {
2pi * t, if p != 0.
pi * t', if p = 0 and x >= 0.
pi * (t + 1), otherwise. }
Now f(x) = (1, theta, phi) in spherical coordinates.

Problem 6

100! ends in k zeros where k is the largest element of the set, K, f powers of ten which divide 100!. That is,

(x memberof K) iff ((x | 100!) and (x = 10^n for n member of N))
k member of K
((y memberof K) and (y != k)) implies (y < k)

Since 10 = (2)(5), we know that k is of the form (2^n)(5^n). So, we are looking for the largest n such that (2^n)(5^n) | 100!. Clearly, (2^n) | 100! is true for larger n than (5^n) | 100! since multiples of two are more common than multiples of five. So, we just need to find the largest n such that (5^n) | 100!.
Each multiple of 5 less than or equal to 100 will contribute one to n such that 5^n | 100!. There are 20 such multiples: 5, 10, 15, ..., 95, 100. Each multiple of 25 will contribute two since 25^n = (5^n)(5^n). Of these, there are 4: 25, 50, 75, 100. So, multiples of 25 contribute a total of 8. But, we have double counted and must use inclusion/exclusion on the intersection of multiples of 5 and multiples of 25. Of these, there are also four, since x | 25 -> x | 5.

Finally, we have 20 + 8 - 4 = 24 zeros.

Problem 7

Since natural numbers are either composite or prime, we can instead show that there are at least 210,000 - 50,000 = 160,000 composite numbers. Let's count composite numbers by counting the multiples of 2, 3, 5, and 7.

2 105,000
3  70,000
5  42,000
7  30,000

  247,000
However, we have double counted the numbers which are multiples of two of {2, 3, 5, 7}. So, using inclusion/exclusion, we subtract these back out.

6  35,000
10 21,000
14 15,000
15 14,000
21 10,000
35  6,000

 -101,000
Now, we must add back in the numbers which are multiples of three of {2, 3, 5, 7}.

30  7,000
42  5,000
70  3,000
105 2,000

   17,000
And subtract out the multiples of (2)(3)(5)(7) = 210.

210 1,000

   -1,000
Totaling, we get 247,000 - 101,000 + 17,000 - 1,000 = 162,000.