Math 113 Homework Solutions

section 1.4

5. From the given condtion that each box contains either a snake or big bucks, there are three possibilities: 2 boxes of bucks, 1 box of bucks and 1 snake, or 2 snakes. If statement A is false, then there would be no bucks and hence two snakes. Then statement B would be true, contradicting the second condition that A and B are both true or both false. Thus statement A must be true. Statement B must be true also. There is a deadly snake in box A - choose B.

6. Only one trip is necessary to determine which switch is connected. Turn the first switch on for 5 minutes or so, then turn the first switch of f and turn the second switch on. Go into the other room. If the light is on, the 2nd switch is connected to the light. if the light is off, see if the bulb is warm. If the bulb is warm it's the first switch and a cold bulb means it's the third switch.

9. People: Smith - chair "Who spilled the beans?" Knows 3 always tell the truth. Shlock: "Wind or Pocket" Wind: "Neither Slie nor I." Pocket: "You are both lying," Greede: "One of Shlock and Wind is lying, the other truthing." Slie: "That's false, Greede." There are at least 3 truth tellers and at most 2 liars. The first 2 statements are about who did it, the other 3 are about who is truthing and who is a liar. Note that Greede and Slie are contradicting each other - exactly one of them is a liar. If Pocket is truthful, then Shlock, Wind are also lying - too many liars. Pocket then, and either Greede or Slie are the liars. Thus Schlock and Wind are truthing; Schlock says Wind or Pocket but Wind (truthfully) claims "not I." Pocket must be the source of the leak.

11. Bob goes 10 miles, Mary goes 20 and Ivan thirty miles. Cost is \$1.50 per mile. How much should each pay? There are several reasonable ways to split up the fares. The book's method (implied by the hint) is the most elegant. Decide how to split the fares at each of the three stopping points, as if there were 3 consecutive cab rides, At 10 miles, the fare is \$15 split 3 ways or \$5 each, At 20 miles split the next \$15 fare between Mary and Ivan \$7.50 each and Ivan pays \$15 for the last 10 miles, Bob pays \$5, Mary \$5 + \$12.50 = \$17.50 and Ivan pays \$5 + \$12.50 + \$15 = \$27.50 The total fare is \$45 as expected. Another way to split the fare is to count passenger miles. In this problem, Bob has 10, Mary 20 and Ivan 30 miles to travel for a total of 60 passenger miles. Each one pays their fraction of the total. Bob pays 1/6, Mary 1/3 and Ivan 1/2 of the total fare. So Bob pays \$7.50, Mary \$15 and Ivan \$22.50. You can also arrive at this solution by having each person pay half of their solo ride fare. There are many other ways to make 3 numbers sum to 45, but you should be able to justifiy your choice.

section 2.1                         top

7.

honest congressman (if you're cynical)
number of states in the US (50)
honest congressman (if you're not so cynical) 535 maximum
number of cars world wide
number of people on the planet
number of phones on the planet
grains of sand on the planet

I think there are more people than cars, and more phones than people. If every person in the US had 18 phones each (phones, not phone lines) this would be about 6 billion phones. Add in the rest of the world's phones, and I think there are more phones than people. Also there is talk of the US running out of area codes. With area codes, there are 8 billion possible phone numbers, which exceeds the world population. I'm sure there's at least one grain of sand in every phone.

9. A property of 29, that 27 doesn't have: 29 is prime, 27 is not, 29 is a sum of 2 squares, 29 = 25 + 4, 27 is not.

14. Socks, you have 5 black pairs and 5 blue pairs, a total of twenty socks. Pull 3 for a pair, 5 for 2 pairs, and 12 for a pair of black socks. (You may grab all of the blue socks.)

15 This is called the Collatz 3x+1 problem. No one knows if this sequence always reaches a 1, but is does reach 1 if you start with a number less than about 1 billion.

1) 19, 58, 29, 88, 44, 22, 11 and see below
2) 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
3) 22, 11 and see above
4) 30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, . . . and see the line 2.

5) One person claimed that if you start with 248, the sequence won't end. How long is this sequence?

section 2.2                         top

7. Determine a formula for (Fn+1)2 + (Fn)2

nFn(Fn)2 (Fn+1)2 + (Fn)2
1 1 1 2 = F3
2 1 1 5 = F5
3 2 4 13 = F7
4 3 9 34 = F9
5 5 25 89 = F11
6 8 64 233 = F13
7 13 169 610 = F15
8 21 441 1597 = F17
9 34 1156 4181 = F19
10 55 3025 10,946= F21
11 89 7921
It looks like (Fn+1)2 + (Fn)2 = F2n+1 And this is, in fact, true.

18, 19. Suppose you are playing Fibonacci nim and you start with 50 (or 100) sticks. What is your first move?

Write the starting number as a sum on non-consecutive Fibonacci numbers.

50 = 34 + 13 + 3
or 100 = 89 + 8 + 3
Then take the smallest number in the sum - 3 in both cases.

20. This is similar to 18 and 19. There are 24 sticks left and 24 = 21 + 3, so take 3 sticks again.

section 2.3                         top

3. If n is an odd number n >= 3 can n+1 be prime? What if n = 1? Since n+1 is even and greater than two, 2 is a proper divisor and n+1 is not prime.

7. What is the smallest n > 1 such that 1 · 2 · 3 · 4 · 5 · . . · n) + 1 is not prime?

n = 2:   (1 · 2 ) + 1 = 3, which is prime.
n = 3:   (1 · 2 · 3 ) + 1 = 7 is prime
n = 4:   (1 · 2 · 3 · 4 ) + 1 = 25 = 5 · 5 which is not prime. Note that all factors > 4.
n = 5:   (1 · 2 · 3 · 4 · 5) + 1 = 121 = 11 · 11 which is not prime. Note that all factors > 5
n = 6:   (1 · 2 · 3 · 4 · 5 · 6) + 1 = 721 = 7 x 103 which is not prime. Note that all factors > 6

8. Does a prime multiplied by a prime ever give a prime result? Never. Each of the two primes would be proper factors of the product. Does a nonprime multiplied by a nonprime ever give a prime result? Never. If as soon as one of the factors is not prime, the product is not prime. Even in the weird special case: 1 x 1 = 1, the product is 1, which is not prime.

17. Consider the sequence {11, 101, 1001, 10001, 100001, . . .} Are all these numbers prime? If not, find the first one that is not and write it as a product of primes.

The first non-prime is 1001 = 7 · 11 · 13

21. Consider the sequence of numbers 2n - 1 where n = 2, 3, 4, 5, 6 .. . Find the smallest value for which 2n - 1 is not prime.

22 - 1 = 3, 23 - 1 = 7, 24 - 1 = 15 which is not prime.
In fact, 2n - 1 is never prime unless n itself is prime.

28. Take a prime p > 3 and subtract 2. Is this new number always prime? Explain. are there infinitely many primes where the answer to this question is yes? How does this last question relate to a famous open question?

If p = 11, p-2 is not prime. If p = 5, 7, 13, 19, 31 . . . Then p-2 is prime. These are examples of twin primes. No one as yet knows if there are infinitely many pairs of twin primes or not.

35. Find a run of 6 consecutive numbers none of which are prime.

Using the hint, let n = (2 · 3 · 4 · 5 · 6 · 7) Look at the 6 numbers starting with n + 2:

n is divisible by 2 and so is n + 2. n + 2 us not prime.
n is divisible by 3 and so is n + 3; n + 3 us not prime.
n is divisible by 4 and so is n + 4; n + 4 us not prime.
This works up to 7, so the 6 numbers n+2 up to n+7 are not primes.

section 2.4                         top

9. The second code is the correct one, since the sum modulo 10 is zero.

 UPC codes 0   7 1 7 3 4   0 0 0 2 1   8 0   7 0 7 3 4   0 0 0 2 1   8 0   7 0 7 4 3   0 0 0 2 1   8 multipliers: 3   1 3 1 3 1   3 1 3 1 3   1 3   1 3 1 3 1   3 1 3 1 3   1 3   1 3 1 3 1   3 1 3 1 3   1 products (mod 10) 0   7 3 7 9 4   0 0 0 2 3   8 0   7 0 7 9 4   0 0 0 2 3   8 0   7 0 7 2 3   0 0 0 2 3   8 the sums(mod 10) 0+7+3+7+9+4+0+0+0+2+3+8 = 3 0+7+0+7+9+4+0+0+0+2+3+8 = 0 0+7+0+2+3+0+0+0+2+3+8 = 5

13. Let x be the missing digit in the UPC code.

 UPC code 0   4 8 0 0 1   2 6 x 0 4   2 multipliers: 3   1 3 1 3 1   3 1 3 1 3   1 products (mod 10) 0   4 4 0 0 1   6 6 3x 0 2   2 the sum(mod 10) 0+4+4+0+0+1+6+6+3x+0+2+2 = 5 + 3x
Thus x must satisfy the equation 5 + 3x = 0 (mod 10) This reduces to 3x = 5(mod 10) and thus x = 5. Since 3 and 10 have no commen factors you can solve 3x = c(mod 10) for any value of c.

section 2.5                         top

4. The primes p = 5 and q = 19. Then m = (p – 1)(q – 1) = 4•18 = 72 and e = 11 has no factors in common with m. (Since e is prime, you can just check that 11 is not a factor orf 72.) Then d = 59 and ed = 11•59 = 649 = 7•72 + 1, so ed = 1(mod 72)

6. This is an example of Fermat's little theorem, n4 = 1 (mod 5) for n = 1, 2, 3, 4 since 5 is a prime number.

In the next three questions, n = 143 and e= 7.
8. To encrypt 4 you compute 47 = 82(mod 143) The encrypted message is 82. To decrypt 82, you compute 82103 = 4(mod 143)

10. To encrypt 11 you compute 117 = 132(mod 143) The encrypted message is 132. To decrypt 132, you compute 132103 = 11(mod 143)

13. To encrypt 83 you compute 837 = 8(mod 143) The encrypted message is 8. To decrypt 8, you compute 8103 = 83(mod 143)

22. To make a valid signature, let's assume you first send a message to Shlock using his public key: n = 143 and e = 7. You get a reply, but want to be certain it's actually from Shlock. Shlock would sign his message as follows: first he converts his name to numbers say 19,8,12,15,3,11. Then Shlock raises each number to his secret d power (103 here) (mod 143) and signs his letter, with those numbers: 72,83,12,141,16,132. When you receive this signature you verify that Shlock sent it by raising these numbers to the public exponent, e (7 here) Since (xe)d = x (mon n) so does (xd)e = x (mod n). This will give you the original set of numbers which translates to Shlock. An imposter would not be able to determine these numbers without breaking the code which amounts to factoring n. This is difficult if n is a product of 100 digit primes.

section 2.6                         top

8. Of the 6 numbers listed, is the only irrational number. and 3.14159 is not π, it's a rational 5-digit approximation of π

12. Show that is irrational. Suppose not. Then for some integers a and b, which are in lowest terms so they have no common prime factors. Square both sides and multiply by b2 to get

7 b2 = a2

Then a2 must be a multiple of 7 or a2 = 0 (mod 7) This means a = 0 (mod 7) since if a were not equivalent to zero, no power of a could be zero, as a6 = 1 (mod 7) by Fermat's little theorem since 7 is prime. a = 0 (mod 7) means a = 7c for some integer c. Substituting in a = 7c gives:

7 b2= (7c)2 = 7 7 c2 and

b2 = 7c2

This means b2 is a multiple of 7 and thus b is a multiple of 7 also, by the argument above. This contradicts the lowest terms condition on a and b. They cannot both be divisible by 7. Thus there are no such a and b and is irrational.

19. If 14E = 9 , prove that E is irrational. The outline of the proof is like problem 12, assume that E is rational and get a contradiction. Suppose E = a/b for some integers a and b. Then 14a/b = 9 and if you raise both sides of this equation to the b power, you get: 14a = 9b. This equation only involves integers and since the left side is even and the right side is odd, it can't be true. Thus E is irrational.

20. 8E = 4. The solution to this is e = 2/3. The reason E is rational here is that both 4 and 8 have the same single prime factor, 2.

section 2.7                         top

8. Any non-zero decimal stuck to the end of 12.0345691 like .0000000123 will be strictly between the 2 given numbers.

13. The smallest XXXXX value is 00000, the largest is 99999.

33. You start at 1 and go half the distance to zero at each step. You are at 1/2, 1/4, 1/8, . . . 1/2n . . . This sequence will never reach zero, but it will get arbitrarily close to zero.

34. You approach zero as in 33, but now you are at the center of a small (length = 10-11) interval. Eventually zero will be in the interval, since the center gets arbitrarily close to zero, it will get below 1/2 of the length. Then zero will be in the interval.

section 3.2                         top

6. To correspond the even numbers E to odd numbers O, add one to each odd number or subtract one from each even number. One formula would be: n <--> n + 1; where n is any odd number. These sets have the same cardinality.

7. To correspond E with all natural numbers, simply halve each element in E. To go the other way, double each natural number. A formula would be: n <--> 2n; where n is any natural number. These sets have the same cardinality.

Note: In view of Cantor's theorem in section 3.3, you may not simply say, "these sets are both infinite and hence there is a 1 - 1 correspondence between them." Not all infinities are created equal.

19. Most proofs of the finiteness of sand grains were by contradiction. For example, "sand has volume. If the number of grains were infinite, the volume would be infinite and at least cover the earth. This is not true. Hence the number of grains of sand is finite." Another proof is that you could in theory count the grains of sand. Estimate the number of grains in a teaspoon of sand, and calculate how many teaspoons would cover the earth. This was the approach taken by Archimedes in the The Sand Reckoner, written around 200 BCE. See http://www.math.uwaterloo.ca/navigation/ideas/reckoner.shtml

20. There are infinities greater than the real numbers. For example, the set of all sets of real numbers has a greater cardinality. This means there is no 1-1 correspondence between this larger set and the real numbers, just as there is no 1-1 correspondence between the reals and the natural numbers.

section 3.3                         top

13. Show that the set of all possible 2 color circle colorings has a greater cardinality than the set of all natural numbers.

Suppose there were such a correspondence. Then there would be a way to list all of the circle colorings, the coloring matched with 1, then 2, then 3 etc. But there must be a coloring that's not on this list. To show this, we'll construct a coloring (call it M) using this list of colorings. Color the nth circle of M with the opposite color of the nth circle of the nth coloring. Then by construction, M doesn't match the nth coloring in the listing since M's nth color is different. Thus M is missing from the alleged complete list so there cannot be a one to ont correspondence from the natural numbers onto the set of circle colorings.

20. There are sets even larger than the set of real numbers! This was also proved by Georg Cantor. He showed, using an argument like the diagonal method, that for any set the set of all subsets of that set has a larger cardinality. There are infinitely many sets, each of which has a larger cardinality the the ones preceding it.

section 4.1                         top

8. There is no 1, 2, 3 right triangle, since 12 + 22 = 5 ≠ 32. There isn't even a 1, 2, 3 triangle, since 1 + 2 = 3. (Try to draw one.) The 2, 4, 5 right triangle is all consecutive integers 32 + 42 = 52.

10. The hypotenuse of the triangle is 130 ft. and the base is 50 ft. The height is thus 120 ft. since 1302 - 502 = 1202.

13. The first triangle has lengths 1, 1, √2; the second one is 1, √2, √3, since 12 + (√2)2 = (√3)2. This pattern continues: the nth triangle has a hypotenuse of length √(n + 1).

14. Since 2.62 + 8.12 = 72.37 < 73.96 = 8.62, this is not a right triangle. In fact, it's obtuse.

15. If one mile of track expanded by 2 feet, you would have 2 right triangles each with a base of 2,640 ft; height h and hypotenuse 2641 ft. (There are 2,649 ft. in 1/2 a mile.) Then h would be the square root of: 2,6412 - 2,6402 = 5,281 which is about 73 ft. That's one tall bump!

19. Since the area of a circle or a pizza is proportional to the square of the diameter and the price of the small + the medium equals the large, you could draw a triangle whose lengths are the 3 dianmeters. If the angle between the small and the medium is obtuse, then the large is the better deal. (Just like in problem 14.) If the angle is acute, get small + medium. If it's right, get the small + the medium - same area but more choices of toppings.

section 4.2                         top

5. Place a single camera at one of the interior angles, and this will cover all of the interior. With 12 vertices, the theorem guarantees that 4 cameras will suffice, but that applies to all possible configurations.

20. See the shapes in problem 19 for possible solutions.

section 4.3                         top

9. The folded, golden rectangle will have dimensions which are half the length of the original, so the ratio of base to height the same as the original - φ.

12. Suppose you have a golden rectangle with height h and base hφ. If you add a square of length hφ to it you will get a rectangle that is hφ by hφ + h. The ratio of the sides of the larger rectangle is:

(hφ + h)/hφ = (φ + 1)/φ = φ2/φ = φ.

13. Even if your initial rectangle is far from golden, if you add on 4 or 5 squares you will get a ratio of the dimensions that is pretty close to the golden ratio. The reason for this is that the side lengths grow by the same formula as the Fibonacci numbers - the new largest dimension is the sum of the last two. The actual numbers will be different than the Fibonacci numbers unless you start with a 1 by 2 rectangle. Recall that the ratio of consecutive Fibonacci numbers approaches the golden ratio - the same is true for any similar formula regardless of how you start.

16. The ratio of the areas will be φ2. This is because both of the sides of rectangle G shrink by a factor of φ to make the sides of G'. Since the area is the product of the sides, it drops by a factor of φ2.

section 4.4                         top

10. The larger, four unit triangle is upside down compared to the original. This is a symmetry of scale, since 16 triangles would have the same orientation as the original.

17. The rectangle, hexagon and the right triangle can all tessellate the plane, but the octagon will not. The octagon angles are all 135°, so no multiple will add up to 360° The hexagon has 120° angles, so three of them fit nicely around a point. The simplest way to tile with a right triangle is to form two of them into a rectangle.

20. If the square tiling doesn't distinguish among any of the squares, the two operations will produce the same square tiling so the order of the operations doesn't matter. But if you label the corners of the square, then the order does matter. First flip, then rotate: Next rotate, then flip:

section 4.5                         top

4. To get the dual of a cube, put a vertex in the center of each face and connect the each vertex to the four vertices on adjacent faces. This will produce an octahedron. If you apply the same procedure to the octahedron, you will get 8 vertices connected to three adjacent vertices making a cube. The symmetry of duality will turn each of the Platonic solids into another Platonic solid. The dodecahedron and the icosahedron and duals and the tetrahedron is self-dual.

5. The first figure is a tetrahedron viewed from above at a vertex, the second is a cube viewed from the center of a face in the inside and the third is an octahedron wiewed from above a vertex.

15. The stellated cube has 24 faces (add 4 x 6 and subtract the 6 original, 14 vertices (add 6 to the original 8) and 36 edges ( add 4 x 6 to the original 12). Note that the Euler characteristic is 24 + 14 - 36 = 2.

section 5.1                         top

9. Yes the dollar and the straw are both solids with holes in them, so they are equivalent. Thicken the straw and smash it flat and it will look like the coin.

11. A coffee mug has a handle, so it's equivalent to the donut. The useful part of the mug (the part that holds the coffee) can be distorted into a flat disk with a handle attached. Then shrink the disk until it looks edible.

14. We did this one in class. If you pull out the loop that's around the ring and then put it around the ring, the ring will com free.

16. This one is best done with pencil, paper and scissors. Two of them are topologically equivalent to each other.

section 5.2                 top

8. Try it and see! A strip with two half-twists will be a 2 sided, orientable strip. When you cut it down the middle, you get two linked rings. Some people in the class did this with the original Moebius strip. After cutting it down the middle, you get a single strip with a full twist in it. Cutting this strip down the middle is the same exercise as this one.

13. Try it and see! The most common result is two pieces - one a strip that's not a loop and the other is a Moebius strip.

14. Try it and see! When you tape the strips together, it's still a 2 sided strip. There is an inside and and outside. If you run a pencil along it, you won't reach the inside where paper touches paper. The result of the cut is very much like number 8.