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
![\noindent \textbf{Big Problem 7: Which Is Bigger? }. Compare the cardinalities of the following sets:
\begin{enumerate}
\item $\mathbb{N}$
\item $\mathbb{R}$
\item $\mathbb{R}^2$
\item $\mathbb{R}^n$
\item set of functions from $\mathbb{N} \to \mathbb{N}$
\item set of functions from $\mathbb{R} \to \mathbb{R}$
\item algebraic numbers (i.e. the roots of finite degree polynomials with integer coefficients)
\item the Cantor Set
\item and the open interval $(0, 1)$
\item set of all things you can describe in finite English sentences \\[.1in]
\end{enumerate}
\noindent \textbf{Big Problem 8: Tulie Numbers}.
Recall the Tulie Numbers class activity.
\begin{enumerate}
\item Show that every rational number is dull, i.e. not endless.
\item Show that every dull number is rational.
\item Explain why the last two statements imply that a number has an infinite continued fraction representation if and only if it is irrational.
\item Convince me that $e$ is irrational by finding a pattern in its continued fraction expansion.\\[.1in]
\end{enumerate}
\noindent \textbf{Big Problem 9: Irrational Numbers}.
\begin{enumerate}
\item Use an argument similar to Euclids method to prove $\sqrt[n]{2}$ is irrational for any natural number $n > 1$.
\item Use an argument similar to Euclids method to prove that $\sqrt{p}$ is irrational for $p$ prime.
\item 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.)\\[.1in]
\end{enumerate}
\noindent \textbf{Big Problem 10: Closed Form Formula for the Fibonacci Sequence}.
\begin{enumerate}
\item We call a sequence $A_n$ \emph{Fibonacci-esque} if it has the property $A_{n+2} = A_{n+1} + A_n$.
\item 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$).
\item Prove linear combinations of Fibonacci-esque sequences have to be Fibonacci-esque.
\item 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.
\end{enumerate}](/latex/cache-w5VDjhb8CNUID7s4scaxBA/srender-crop-0.png)  | • pdf • pdf tight • latex |
The First Batch of Big Problems
![\newcommand{\cent}{\hbox{\rm\rlap/c}\;}
\noindent \textbf{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 cant make 1\cent or 2\cent in postage. Lets call postage like 9\cent or 11\cent possible postage for 3\cent and 5\cent stamps, and lets call 1\cent and 2\cent impossible postage.
\begin{enumerate}
\item Find the highest impossible postage for 3\cent and 5\cent stamps.
\item Write a convincing argument that it is the highest impossible postage.
\item 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.
\item Prove your formula is valid for any pair of positive postages.
\end{enumerate}
\noindent \textbf{Big Problem 2}. \begin{enumerate}
\item Give me an algorithm for adding two numbers in base $2i$. What is the analogue to our carrying in base 10?
\item Give me an algorithm for multiplying two numbers in base $2i$.
\item Explain why your algorithms work.
\end{enumerate}
\noindent \textbf{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 Taxmans 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 havent 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:
\textbf{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 Players and Taxmans total scores. The one with the highest score wins.
\begin{enumerate}
\item Play Taxman up to 10 (that is, use the numbers 1 through 10) and beat the Taxman.
\item 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.
\item Play Taxman up to 25 and beat the Taxman. Show your winning game.
\item Find the maximum amount you can win given 25 and provide a convincing argument for why your answer is correct.\\[.1in]
\end{enumerate}
\noindent \textbf{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 \emph{unit fractions with no repeated denominators}. So, we can write it like $1/2 + 1/10$.
\begin{enumerate}
\item Show every \textbf{proper} fraction has an Egyptian fraction representation. Be sure to show an explicit algorithm and prove that it terminates with no repeated denominators.
\item Which unit fractions can be written as a sum of TWO unit fractions? \\[.1in]
\end{enumerate}
\noindent \textbf{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}
\item in one way of assembling the large cube, all six faces are red,
\item in another way of assembling the large cube, all six faces are green,
\item in still another way of assembling the large cube, all six faces are yellow?
\end{itemize}
You get part credit for proving its possible. You get the rest of the credit for giving me an explicit paint scheme and rearrangement scheme.\\[.1in]
\noindent \textbf{Big Problem 6: Repeating Decimal Periods}. When a decimal representation repeats infinitely, we call the length of the repeating block ``the period.
\begin{enumerate}
\item 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.
\item Generalize your rule for reciprocals of prime numbers to the case of a general fraction, $1/n$, where $n$ is a natural number.
\end{enumerate}](../latex/cache-CgzlIq5wyPYbHETY9OA5uA/srender-crop-0.png)   | • pdf • pdf tight • latex |