### 475 Homework Assignments

May 9 2008: Posted extra credit HW11

Apr 28 2008: Posted HW10.

Homeworks should be submitted through e-mail. We may add problems during the week, depending on what happens in class. Feel free to ask for ideas and hints in class before next Monday. You are encouraged to work together on HW, but please write up responses separately.

Homework 1. Due Monday Jan 28.
1. Write a brief math autobiography (aim for a page).
2. Select from the following list of values two or three that are most important to you: Athletic ability, being good at art, creativity, independence, living in the moment, membership in a social group (such as your community, racial group, or school club), music, politics, relationships with friends or family, religious values, and sense of humor.
3. Write about one or more times in your life when these values were important to you. Write a few sentences about why they were important to you.
Homework 2. Due Monday February 4th.

If you have as many 3c stamps and 5c stamps as you want, you could make 9c postage, and 11c postage. (How?) But you can't make 1c or 2c in postage. Let's call postage like 9c or 11c possible postage for 3c and 5c stamps, and let's call 1c and 2c impossible postage.
1. Find the highest impossible postage for 3c and 5c stamps.
2. Write a convincing argument that it is the highest impossible postage.
3. Now experiment with different pairs of Nc and Mc stamps. Find a method, for any specific pair of Nc and Mc stamps, for determining whether there is a highest impossible postage, and if there is a highest one, a formula for what it is.
Homework 3. Due Monday, February 11th

Most of this HW is actually not for turning in (unless indicated explicitly), but you should do it for your own effectiveness as a teacher, as these are questions a future student will ask you.
1. Explain with symbols and pictures of cubes WHY the three subtraction methods work: American, European and Make It Nice.
2. Explain WHY Lattice Multiplication works.
3. Consider this model of the integers. Every integer is an IOU, either a check or bill in dollars. So 20 means we are owed \$20 (a \$20 check), -20 means we owe \$20 (a \$20 bill). Explain in words using this model what is a reasonable value for:
1. 20 + (-20)
2. 20 - (-20)
3. (-20) + (-20)
4. -20 + 0
4. Modeling multiplication is more complex. Let's model M x N as follows. For a positive N, we say it's getting an IOU worth \$M, N times. For a negative N, we say it's losing an IOU worth \$M, N times. Explain in words using this model what is a reasonable value for:
1. 20 x 1
2. 1 x 20
3. 20 x 0
4. 0 x 20
5. 20 x -3
6. (20 x 3) + (20 x (-3))
7. -20 x 3
8. -20 x -1
9. (turn in) -20 x -3
5. Formally, we can quickly demonstrate for positive M, N that

0 = 0 x (-N) = (-M+M) x (-N) = (-M x -N) + (M x -N).
Therefore,
(M x N) = (-M x -N) + (M x -N) + (M x N) = (-M x -N) + (M x (-N + N)) = (-M x -N).

This uses only the definition of -N as N's additive inverse, and properties inherited from whole numbers: a product with zero is zero, the distributive property, and the additive property of equality. Notably, this last piece is the only property of negative numbers assumed.
• (turn in) Comment on the advantages and disadvantages of this demonstration compared to using the model above.

6. French Hand Multiplication. In Butterworth's What Counts, p.205, he writes:

• To this day [about 1930], the peasant of central France (Auvergne) uses a curious method for multiplying numbers above 5. If he wished to multiply 9 x 8 he bends down 4 fingers on his left hand (4 being the excess of 9 over 5) and 3 fingers on his right hand (8-5=3) . Then the number of bent-down fingers gives him the tens of the result (4+3=7) while the product of the unbent fingers gives him the units (1x2=2).

(turn in) Does this method work for multiply any numbers between 6 and 9? Justify why, or give a counter-example.

7. Doubling/Halving Multiplication. I showed you in class how to multiply two numbers A x B, by making two columns. In the first column, halve A (discarding the remainder), the next column, double B. Go to the next line and repeat the process. Stop when you halve A down to 1. Then you circle each line with an odd A. Add up all the numbers in the B column.
• (turn in) Why does this work?
(Hint: Why isn't the last line the right answer?)
Homework 4. Due Monday Feb 25.
1. In a condominium, 2/3 of the women are married to 3/5 of the men. What fraction of all people there are married? (You can assume people are only married to others in the condo, and marriages in this condo are between people of opposite sexes.) Explain your answer. Try to solve it with more than one method.
2. (don't turn in) Divide 128 by 7 using relaxed repeated subtraction.
3. Explain why in class we called our long division algorithm abbreviated uptight repeated subtraction. Explain this using the example of 128 divided by 7.
4. Henry spends 3/14 of his monthly income for rent and 2/11 of what is left on food. If he has \$540 left, what is his monthly income ? (Hint: Pictures really help).
5. Describe 128 divided by 7 using
1. a partitive model (sharing)
2. a measurement model (taking out bundles)
6. (don't turn in) Multiplying Improper Fractions. Draw a picture of 4 1/2 x 2 1/3 using an area model. Separate the whole number parts from the fraction parts and find a tidy algorithm for multiplying improper fractions. Explain in words what your algorithm is.
Homework 5. Due Monday Mar 10. (Extension until Friday March 14.)
1. Recall the Tulie Numbers class activity.
1. Show that every rational number is dull, i.e. not endless.
2. Show that every dull number is rational.
3. Explain why the last two statements imply that a number has an infinite continued fraction representation if and only if it is irrational.
Homework 6. Due Monday Mar 17.
1. Prove that every rational number has a repeating decimal representation (here repeating includes a repeating zero at the end, which is usually called a terminating decimal).
2. Prove that every repeating decimal representation represents a rational number.
3. Give an example of a non-repeating decimal representation and argue that it is not a rational number. Be sure you can prove your chosen number never repeats, so don't say "Pi".
1. Consider an infinite decimal representation .d1 d2 d3 ...
1. Write it as a limit of a sequence of truncated ("cut-off") decimal representations.
2. Prove your sequence is Cauchy (with respect to the natural metric here, the absolute value of the difference of numbers).
3. (don't turn in) Remind yourself what a completion of a metric space is, and convince yourself that the real numbers are the completion of the rational numbers.
Midterm Big Problems. Due by Spring Break. Turn in three of the 7 listed Big Problems.

Homework 7. Due Monday Mar 31.
1. Convince me that e is irrational by finding a pattern in its continued fraction expansion.
2. The word "short" is short. The word "long" is not long. That is kind of hypocritical of that adjective, isn't it? We call an adjective hypocritical if it doesn't describe itself. So, the words "green", "French" and "vowelless" are all hypocritical, while "English" and "unnecessarily-hyphenated" are not hypocritical. So... comment on the following question: is "hypocritical" hypocritical? Explain why this is like the American Idol/Barber Paradox.
Homework 8. Due Monday Apr 14.
1. A set S has N distinct elements. How many distinct subsets are there? (Be sure to include S and { }.) Explain why your formula works.

2. The power set of S, written P(S), is the set of subsets of S. Prove that the cardinality of P(S) is strictly larger than the cardinality of S when S is finite.

3. Consider the general case of a possibly infinite set S. To deal with comparing cardinalities of infinite sets, recall from class that sets A and B "have the same cardinality" if and only if A fits into B and B fits into A. Recall that "A fits into B" means there is an injection from A to B.

4. Consider the power set of the rational numbers, P(Q). Show that the real numbers fit into P(Q). Use this fact, and our previously established uncountability of the reals, to give a proof that P(Q) does not fit into Q.

5. There is a theorem called the Bernstein-Schroeder Theorem which says that A and B have the same cardinality if and only if there is a bijection between them. The theorem is annoyingly complicated to prove and not too edifying, so you can prove that to yourself on your own time. You are allowed to use that theorem for this problem set.

Prove that the cardinality of P(S) is always larger than the cardinality of S. (Hint: Suppose there is a bijection from S into P(S). Now construct a contradictory subset using a variation of the American Idol paradox.)
Homework 9. Due Monday Apr 21.
1. Derive our class solution for x2 + Bx + C = 0 by completing the square. Explain how you can solve ANY quadratic equation using this special case.
2. Suppose we have a table for an in-out function that, when you plug in 0, 1, 2, 3, ... always gives you results with a constant (first) difference of M.
1. Find a formula for a linear function that matches this data.
2. Prove that any linear function has an in-out table with constant first differences.
3. (don't turn in) Find a quadratic function that matches the following data:
 IN OUT 1 5 2 9 3 17 4 29 5 45

(Next week I'll ask you to model a constant second difference table with a quadratic.)
Homework 10. Due Monday May 5.

1. Prove that the first difference of an Nth degree polynomial has at most degree N-1.
2. Prove an Nth degree polynomial has constant Nth differences.
1. The nth tetrahedral number is the sum of the first n triangular numbers. (It's also the balls in first n layers of a tetrahedral ball pyramid.) Find a closed formula for it using our analysis of functions and their first, second, third, etc. differences.
2. Prove that a function with constant Nth differences can be modeled with some Nth degree polynomial (you can leave your polynomial in a very messy form).
Homework 11. Due by Fri May 23 for extra credit.

1. Prove log_2 (5) is irrational.
2. Writing e as a series
1. Write (1 + (1/n))^n using the binomial theorem for positive integers n.
2. Look at the coefficients of the terms involving (1/n), (1/n)^2 and (1/n)^3. What are their limits as n goes to infinity?
3. Now find the limit of each term as n tends to infinity, and derive a formula for e as an infinite series.
4. Repeat the above treatment for (1 + (x/n))^n.
5. Assuming that e is genuinely equal to the infinite series, prove e is irrational. (Hint: if e = p/q, multiply through by (q!).)
3. Write me a formula for sums of cubes using our difference table trick.
4. Use change of base formula to decide what log_i (x) should be. (That's right, log base i.)

### Big Problems List

Three Big Problems are due by the Midterm mark.

Big Problem 1. Prove that your formula in HW 2.3 always works. I.e. explain why it has the form it does.

Big Problem 2. We've dealt with base 10 and base 4 arithmetic. Now imagine a number system that is base 2i, where i is the square root of -1, and only uses the symbols 0, 1, 2, 3 (in that order) and a radix point (known as a decimal point in base 10 ).
• Write as many numbers as you can in base 2i.
• (Hint: You may want to break it into smaller questions like what natural numbers you can write, what imaginary numbers, what fractions, etc.)

Big Problem 3.
1. Give me an algorithm for adding two numbers in base 2i. What is the analogue to our "carrying" in base 10?
2. Give me an algorithm for multiplying two numbers in base 2i.
3. Explain why your algorithms work.
Big Problem 4. Consider the case of Minnie Camel - the enterprising but eccentric owner of a small banana grove in a remote desert oasis.
• Minnie’s harvest, which is worth its weight in gold, consists of 45 bananas.
• The marketplace where the harvest can be sold is fifteen miles away.
• However, Minnie must walk to market, and she can carry at most fifteen bananas at a time.
• Furthermore, being a camel, Minnie eats one banana continuously during each and every mile she walks. That means, for instance, if she walks a half mile, she eats a half banana.
• Because she is so famously ferocious, she knows she can drop bananas by the side of the road and not worry about anyone trying to steal them.
What is the most bananas Mini can get to market? Explain exactly how she can do it.

Big Problem 5: The Taxman.

The Taxman is a one player game. You, the player, will be given a number such as 17, and you should write all the numbers from one through your number on the paper (1 through 17 in this case). Then make a table with one column for the Taxman and one for the player.

First the player picks a number, writes it in her column, and crosses it off the list. Next, she takes all the divisors of that number that have not been crossed off, and writes them in the Taxman’s column. Then she crosses those numbers off the list.

Now, she picks another number that has not been crossed off, writes it in her column, crosses it off the list, gives the divisors that haven’t been crossed off yet to the Taxman, and crosses the divisors off the list.

The game continues in this way. There is just one rule to follow:

The Rule: Every number the player picks must have at least one divisor that has not been crossed off the list yet. That is, the Taxman must get something on every turn!

When the player can pick no more numbers while following the rule, the Taxman gets all the numbers that are left. The numbers in each column are then added to give the Player’s and Taxman’s total scores. The one with the highest score wins.

1. Play Taxman up to 10 (that is, use the numbers 1 through 10) and beat the Taxman.
2. Find out what is the maximum amount you can win in a game up to 10. Explain clearly how you know that the amount you write is really the maximum.
3. Play Taxman up to 25 and beat the Taxman. Show your winning game.
4. Find the maximum amount you can win given 25 and provide a convincing argument for why your answer is correct.
Big Problem 6: Repeating Decimal Periods. When a decimal representation repeats infinitely, we call the length of the repeating block "the period".
1. Examine the periods of fractions of the form 1/p, where p is a prime. Discover a cool rule describing the periods in relation to p, and share it with me. Explain why it is so.
2. Generalize your rule for reciprocals of prime numbers to the case of a general fraction, 1/n, where n is a natural number.
Big Problem 7: Proving Irrationality.
1. Use the continued fractions method to prove the square root of n^2+1 is irrational for any natural number n > 0.
2. Use an argument similar to Euclid's method to prove 2^(1/n) is irrational for any natural number n > 0.
3. Use an argument similar to Euclid's method to prove that the square root of p is irrational for p prime.
Big Problem 8: Random Hats.

N people arrive at Hilbert's Restaurant. Each one has a unique hat. They leave their N unique hats at the door of Hilbert's Restaurant. When they leave, they each are randomly returned a hat from the original set.
1. What is the probability that nobody got their proper hat back?
2. As N becomes very large, does this probability tend towards 0, 1 or a specific number?
Big Problem 9: Cube of Many Colors.

Twenty-seven small cubes (identical in size) can be used to form a large cube. Is it possible to paint each face of each small cube with one of the three colors (red, green, and yellow) in such a way that (for the same paint scheme):
• in one way of assembling the large cube, all six faces are red,
• in another way of assembling the large cube, all six faces are green,
• in still another way of assembling the large cube, all six faces are yellow?
You get part credit for proving it's possible. You get the rest of the credit for giving me an explicit paint scheme and rearrangement scheme.

Big Problem 10: Pascal's Triangle.

1. Find the triangular numbers in Pascal's Triangle. Prove that the pattern continues forever.
2. Identify the skew-diagonals of PT which sum to the Fibonacci numbers. Prove this pattern continues forever.
3. Prove the sum of every nth row is 2n (assuming the "1 1" row is the first row).

Big Problem 11: Closed Form Formula for the Fibonacci Sequence.

We call a sequence An Fibonacci-esque if it has the property An+2 = An+1 + An.
1. Find all geometric sequences that are Fibonacci-esque. That is, all numbers C such that the sequence An = kCn is Fibonacci-esque (for constant k).
2. Prove linear combinations of Fibonacci-esque sequences have to be Fibonacci-esque.
3. Find a closed-form formula for the famous Fibonacci sequence {1, 1, 2, 3, 5, 8, . . .} by finding a sum of Fibonacci-esque geometric sequences that has the famous values.