\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{wasysym}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{5: More Generating Functions}{Due Friday, Week 3}

Do \textbf{three} of the \textbf{six} problems below!   Prove all of your claims. Generating functions and the results we proved using them can be used to solve all of these problems, though you are not required to do so if you see another solution.

\begin{enumerate}
\item Let $T_n$ denote the number of ways to tile a $2 \times n$ strip with $2 \times 1$ dominoes.  Find a closed form for $T_n$.


\item Prove the following identity: for any $r, s, n \in \mathbb{N}$, we have
\begin{align*}
\sum_{k=0}^n \binom{r}{k}\binom{s}{n-k} = \binom{r+s}{n}.
\end{align*}

\item Suppose you live in a country with 1, 2 and 3$\cent$ coins $\circled{1}, \circled{2}, \circled{3}$.  In how many different ways can you make $\$10.00$ using these coins?  (Assume you have as many of the $\circled{1}, \circled{2}, \circled{3}$ coins as you need.)

\item A finite sequence $a_1, \ldots a_n$ is called \textbf{p-balanced} if any sum of the form $a_k + a_{k+p} + a_{k+2p} + \ldots$ is the same, for any $k \in \{1,2,3,\ldots p\}$.  For example, the sequence $(1,2,3,4,3,2)$ is $3$-balanced, because $a_1 + a_4 = a_2 + a_5 = a_3 + a_6 = 5$.

Suppose that $(a_1, a_2, \ldots a_{50})$ is a sequence of length 50 of real numbers.  Suppose that this sequence is $p$-balanced for $p = 3,5,7,11,13,$ and $17$.  Show that this sequence must be the all-zero sequence.

(Hint: when you want to study a sequence this week, what do you do?)
\end{enumerate}

To work with our dice problems, we needed to factor certain polynomials into irreducible factors.  Here are some helpful deus-ex-machina claims that you can use without proof on the next few problems:
\begin{obs}
\begin{align*}
\frac{x^k - 1}{x-1} = \prod_{d|k, d > 1} \Phi_d(x),
\end{align*}
where the polynomials $\Phi_d(x)$ are the cyclotomic polynomials
\begin{align*}
 \Phi_d(x) = \prod_{\omega} (x-\omega),
\end{align*}
where the product above is taken over all primitive $d$-th roots of unity\footnote{A primitive $d$-th root of unity is a complex number $\omega$ such that $\omega^d = 1$ and $\omega^i \neq 1$, for any $1 \leq i < d$.}
\end{obs}
\begin{obs}
The cyclotomic polynomials are all irreducible.
\end{obs}
\begin{obs}
The following is a list of some of the cyclotomic polynomials:
\begin{align*}
\Phi_1(x) &= x-1\\
\Phi_2(x) &= x+1\\
\Phi_3(x) &= x^2 + x + 1\\
\Phi_4(x) &= x^2 + 1\\
\Phi_5(x) &= x^4 + x^3 + x^2  x + x+ 1\\
\Phi_6(x) &= x^2 - x + 1\\
\Phi_7(X) &= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\
\Phi_8(x) &= x^4 + 1\\
\Phi_9(x) &= x^6 + x^3 + 1\\
\Phi_{10}(x) &= x^4-x^3+x^2-x+1\\
\Phi_{12}(x) &= x^4 - x^2 + 1\\
\Phi_{20}(x) &= x^8 - x^6 + x^4 - x^2 + 1\\
\end{align*}
\end{obs}



\begin{enumerate}
\setcounter{enumi}{4}
\item Using the list of cyclotomic polynomials above, can you classify all of the pairs of nonstandard $k$-dice that behave the same as a pair of standard $k$-dice when rolled and summed?

To make our lives easier, assume that we’re working with typical physical dice here, so that our values of $k$ are limited to the platonic solids (in other words, $k = 4,6,8,12,$ or $20$.)
\item Is there any value of $k = 4,6,8,12, 20$ such that we can find \textbf{three} $j$-dice $D_1, D_2, D_3$ for some $l$, such that rolling those three $j$-dice and summing them gives us the same results as rolling two standard $k$-dice and summing them?  
\end{enumerate}








\end{document}