475 Spring 09 Big Problems

What Are These?

You will write up six Big Problems over the course of the semester. Three are due by the midterm date. Another three are due by Wednesday May 20th, 11:59pm.

If you want to see the weekly homework, go to 475 Spring 09 Homework.

Updates

• (Apr 7) Added second batch of Big Problems
• (Mar 5 ) Clarified the Egyptian fractions problem to be about proper fractions.

The Second Batch of Big Problems

Big Problem 7: Which Is Bigger? . Compare the cardinalities of the following sets:

1. $\mathbb{N}$
2. $\mathbb{R}$
3. $\mathbb{R}^2$
4. $\mathbb{R}^n$
5. set of functions from $\mathbb{N} \to \mathbb{N}$
6. set of functions from $\mathbb{R} \to \mathbb{R}$
7. algebraic numbers (i.e. the roots of finite degree polynomials with integer coefficients)
8. the Cantor Set
9. and the open interval $(0, 1)$
10. set of all things you can describe in finite English sentences
    

Big Problem 8: Tulie Numbers. 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.
4. Convince me that $e$ is irrational by finding a pattern in its continued fraction expansion.
   

Big Problem 9: Irrational Numbers.

1. Use an argument similar to Euclid's method to prove $\sqrt[n]{2}$ is irrational for any natural number $n > 1$.
2. Use an argument similar to Euclid's method to prove that $\sqrt{p}$ is irrational for $p$ prime.
3. Use the continued fractions method to prove the square root of $n^2+1$ is irrational for any natural number $n > 0$. (You can assume the results of Big Problem 8.)
   

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

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

The First Batch of Big Problems

\newcommand{\cent}{\hbox{\rm\rlap/c}   }Big Problem 1. If you have as many 3\cent stamps and 5\cent stamps as you want, you could make 9\cent postage, and 11\cent postage. (How?) But you can't make 1\cent or 2\cent in postage. Let's call postage like 9\cent or 11\cent possible postage for 3\cent and 5\cent stamps, and let's call 1\cent and 2\cent impossible postage.

1. Find the highest impossible postage for 3\cent and 5\cent stamps.
2. Write a convincing argument that it is the highest impossible postage.
3. Now experiment with different pairs of N\cent and M\cent stamps. Find a method, for any specific pair of N\cent and M\cent stamps, for determining whether there is a highest impossible postage, and if there is a highest one, a formula for what it is.
4. Prove your formula is valid for any pair of positive postages.

Big Problem 2.

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 3: The Taxman The Taxman is a one player game invented by Diane Resek. 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 4: Egyptian Fractions. Egyptians really liked fractions of the form $1/n$ (unit fractions). What did they do when writing $3/5$? $1/5 + 1/5 + 1/5$ seems ugly and repetitive. We want to use unit fractions with no repeated denominators. So, we can write it like $1/2 + 1/10$.

1. Show every proper fraction has an Egyptian fraction representation. Be sure to show an explicit algorithm and prove that it terminates with no repeated denominators.
2. Which unit fractions can be written as a sum of TWO unit fractions?
   

Big Problem 5: 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): \begin{itemize}

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? \end{itemize} 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 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.