\documentclass[12pt]{article}
\usepackage[]{graphicx}
\usepackage[]{amsmath}
\usepackage[]{amsthm}
\usepackage[]{amssymb}
\usepackage[hmargin=.6in,vmargin=.6in]{geometry}
\pagestyle{empty}
\newtheorem{thm}{Theorem}
\newtheorem*{thma}{Theorem}
\theoremstyle{remark}
\newtheorem{rem}{Remark}
\begin{document}
\begin{center}
\textbf{Math 475 Big Problems, Batch 1}
\textsc{Three due by Spring Break, 2010}
\end{center}
\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 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.
\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: 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:
\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 Player's and Taxman's 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 3: 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?
\end{enumerate}
\noindent \textbf{Big Problem 4: 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. (Hint: Euler's totient function.)
\end{enumerate}
\noindent \textbf{Big Problem 5: Funny Bases}. We are all familiar with the base 10 numeral system, where the set of allowed digits is $ \{ 0, 1,2,3,4,5,6,7,8, 9 \} $ and we interpret $321_{\text{base }10} = 3(10^2) + 2(10^1) + 1(10^0)$. There are famous, useful alternative base systems, such as base 2 (binary), 8 (octal), and 16 (hexadecimal) that are used often in programming.
Consider a strange numeral system that we'll call ``base $-4$''. In this system, the allowed digits are $ \{ 0, 1,2,3 \} $ and place value works in analogy to base 10. For instance, $321.2_{\text{base }-4} = 3((-4)^2) + 2((-4)^1) + 1((-4)^0)+2((-4)^{-1}) = 3(16)+2(-4)+1+2(\frac{-1}{4}) = 40.5_{\text{base } 10}$.
\begin{enumerate}
\item Translate the following numbers, written base $-4$, into base 10: $10, 13, 1000, 0.1$
\item Translate the following numbers, written base $10$, into base $-4$: $3, 5, 20, -3, -0.25$
\item Explain how to write every natural number in base $-4$.
\item Which rational numbers can you write with terminating ``decimals'', base $-4$?
\end{enumerate}
Now consider a strange numeral system that we'll call ``base $2i$'', where $i^2=-1$. In this system, the allowed digits are $ \{ 0, 1,2,3 \} $ and place value works in analogy to base 10. For instance, $321.2_{\text{base }2i} = 3((2i)^2) + 2((2i)^1) + 1((2i)^0)+2((2i)^{-1}) = 3(-4)+2(2i)+1+2(\frac{1}{2i}) = -11+3i_{\text{base } 10}$.
\begin{enumerate} \setcounter{enumi}{4}
\item Explain how to quickly convert a number written in base $-4$ to its representation in base $2i$.
\item Explain how to write every complex integer, $a+bi$, where $a,b \in \mathbb{Z}$ in base $2i$. You are not allowed to use $i$, only plain base $2i$ numbers. (\emph{Hint}: Adapt the base $-4$ work.)
\item (\emph{Extra Credit}). Prove you can write every complex number in base $2i$.
\end{enumerate}
\end{document}