\documentclass[12pt]{article}
\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{substr}
\IfSubStringInString{\detokenize{solution}}{\jobname}{%
% Solutions
\newcommand\qfill{}
\newcommand\qpage{}
\newcommand\qonly[1]{}
\newcommand\answer[1]{#1}
\newcommand\question[1]{{\em #1}}
\newcommand\rubric[1]{}
}
{%
\newcommand\qfill{\vfill}
\newcommand\qpage{\newpage}
\newcommand\qonly[1]{#1}
\newcommand\answer[1]{}
\newcommand\question[1]{#1}
\newcommand\rubric[1]{}
}
\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#6\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due November 23, 2015}}
\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{You open an account at a bank that
pays 5\% interest yearly, and deposit $a_0$ dollars in it. Every
year you withdraw \$10 times the number of years you have had the
account. For example, if you started with \$1000, then in the
first year you would earn \$50 in interest and withdraw \$10,
leaving \$1040, and in the second year would earn \$52 and
withdraw \$20, leaving \$1072, and so forth.
\begin{enumerate}
\item \question{Find a recurrence for $a_n$, the balance in the
account after $n$ years.}
\answer{Since the balance after $n$ years is 105\% of the
previous year's balance, minus $\$10n$, we have
$a_n=1.05a_{n-1}-10n$.}
\item \question{Solve the recurrence to find a closed form for
$a_n$.}
\answer{The associated homogeneous recurrence $b_n=1.05b_{n-1}$
clearly has general solution $b_n=A1.05^n$ for undetermined
coefficient $A$. Now we shall find a particular solution to
the inhomogeneous equation, using the template
$a^p_n=Bn+C$. Substituting this particular solution into the
recurrence, we find that
\begin{align*}
Bn+C&=1.05(B(n-1)+C)-10n\\
10n&=0.05Bn+(0.05C-1.05B)
\end{align*}
so that $B=200$ and $C=4200$, yielding a particular solution
$a^p_n=200n+4200$. The general solution is thus
$a_n=A1.05^n+200n+4200$. Plugging in a particular value of $a_0$, we see that $a_0=A+4200$, so $A=a_0-4200$, leading to the solution
\[a_n=(a_0-4200)1.05^n+200n+4200.\]}
\item \question{What is the smallest initial deposit which would
guarantee that the account never runs out of money?}
\answer{Over the long term, the balance will be positive or
negative based on the coefficient of $1.05^n$ in the closed
form, since this is the dominant term. Thus, in order for the
bank balance to remain non-negative (and actually positive, as
it turns out) indefinitely, it must be the case that
$a_0-4200\geq 0$, so $a_0\geq 4200$. Thus, an initial deposit
of \$4200 is necessary.}
\end{enumerate}
}
\item {\bf (10 points)} \question{Let $a_n=8a_{n-1}-16a_{n-2}+3\cdot
4^n$ with $a_0=3$ and $a_1=-1$. Find a closed form for $a_n$.}
\answer{The associated homogeneous recurrence,
$b_n=8b_{n-1}-16b_{n-2}$, has characteristic polynomial
$\lambda^2=8\lambda-16$, which has a double root at
$\lambda=4$. Thus, the general solution to the homogeneous
recurrence is $b_n=A4^n+Bn4^n$.
Now we shall find a particular solution to the inhomogeneous
equation. If we were to work in ignorance of our homogeneous
solution, we would use the template $a^p_n=B4^n$, but must ``bump
it upwards'' to not overlap our homogeneous solution, and will
instead consider $a^p_n=Bn^24^n$. Then, substituting this into our
recurrence:
\begin{align*}
Bn^24^n&=8B(n-1)^24^{n-1}-16B(n-2)^24^{n-2}+3\cdot 4^n\\
16Bn^24^{n-2}&=32B(n^2-2n+1)4^{n-2}-16B(n^2-4n+4)4^{n-2}+48\cdot 4^{n-2}\\
16Bn^2&=32Bn^2-64Bn+32B-16Bn^2+64Bn-64B+48\\
32B&=48\\
B&=\frac32
\end{align*}
so $a^p_n=\frac32n^24^n$, leading to the general form
$a_n=(A+Bn+\frac32n^2)4^n$. We substitute this into our initial
conditions to get:
\[\left\{
\begin{aligned}
3&=a_0=A\\
-1&=a_1=4A+4B+6
\end{aligned}
\right.\] so that $A=3$ and $B=\frac{-19}4$, leading to the solution
\[a_n=\left(3-\frac{19}4n+\frac32n^2\right)4^n.\]
}
\item {\bf (10 points)} \question{We are making bracelets with 6
stones in a ring, with three different colors of stone. A bracelet
must contain at least one stone of each color. Two bracelets are
considered to be identical if one is simply a rotation or a flip
of the other. How many different bracelets are possible?}
\answer{The symmetries we want to be considering are those of the
dihedral group on 6 elements, which contains 12 elements: the
identity, the clockwise and counterclockwise $60^\circ$ rotations
$r$ and $r^5$, the clockwise and counterclockwise $120^\circ$
rotations $r^2$ and $r^4$, and the $180^\circ$ rotation $r^3$, as
well as the rotations around antipodal stones $f$, $r^2f$, and
$r^4f$, as well as the rotations around antipodal edges between
stones $rf$, $r^3f$, and $r^5f$.
All possible oriented bracelets are invariant under the identity,
so the number of invariants under the identity is simply the
ordered selection of six elements form a pool of three
possibilities, with each needing to be selected at least once;
this is, as we have seen with the twelvefold way, simply
$3^6-3\cdot 2^6+3\cdot 1^6=540$.
Now, we might note that no bracelets are invariant under $r$ or
$r^5$; such bracelets would need to all be a single color,
violating the condition that bracelets have stones of all three
colors. Likewise, $r^2$ or $r^4$ would necessitate bracelets which
have at most two colors in an alternating ring, so there are also
no invariants for these.
Invariance under $r^3$ requires that the bracelet be made up of
two repetitions of a single pattern of three stones, which is
possible, and is equal to the number of ways to arrange all three
stones, which is $6$ (alternatively, we could look at number of
ways to select ordered stones using each, which would be
$3^3-3\cdot 2^3+3\cdot 1^3=6$.
Invariance under $rf$, $r^3f$, and $r^5f$ is quite similar, in
that the bracelet is defined by the colors on three specific
stones, and these too have 6 invariants. Finally, $f$, $rf^2$, and
$rf^4$ involve fixing two stones and mapping the other two pairs
onto each other, so the bracelet is defined by a selection of 4
stones, in $3^4-3\cdot 2^4+3\cdot 1^4=36$ ways.
Now we may use Burnside's Lemma to count the total number of
possible bracelets:
\[\frac{540+0+0+6+0+0+36+6+36+6+36+6}{12}=56\]}
\item {\bf (10 points)} \question{A $4\times 4$ grid of squares is
filled in, with each of the 16 squares colored black or white. Two
colorings are regarded as identical if one can be converted to
each other by performing any combination of flipping, rotating, or
swapping the two colors (flipping all the black squares to white
and vice versa). How many non-identical colorings are there?}
\answer{The algebra here is slightly more complicated than simply
the eight-element group $D_4$; each of those eight elements could
be composed with a ``color-swap'' to get 16 possible elements; if
we denote the color-swap as $s$, then these elements could be
called $e$, $r$, $r^2$, $r^3$, $f$, $rf$, $r^2f$, $r^3f$, $s$,
$rs$, $r^2s$, $r^3s$, $fs$, $rfs$, $r^2fs$, and $r^3fs$. Every
single coloring of the $4\times 4$ square is invariant under the
identity, for a total of $2^{16}=65536$ invariant colorings. To be
invariant under $r$ or $r^3$, a coloring would have to have the
same $2\times 2$ block repeated (with appropriate rotations) on
all four corners, so there are $2^4=16$ invariants. Invariance
under $r^2$ depends on one half of the grid being identical to the
appearance on the other half, so there are $2^8=256$
invariants. Likewise, letting $f$ be a horizontal flip, invariants
under both $f$ and $r^2f$ are determined by the coloration of half
(either a vertical or horizontal half) of the grid, so there are
$2^8=256$ invariants there. $rf$ and $r^3f$ are corner-to-corner
flips, so they have free choice of color for the four squares
along their diagonals and then for each of the 6 pairs of
mirror-image squares off the diagonal, for a total of $10$ choices
of colors and thus $2^{10}=1024$ invariant colorings.
Looking at the transformations involving $s$, the exact same
analysis, simply with a color-transformation added to it, works
for most of the transformations;
i.e. $r^2s$ has $2^8$ invariants, $fs$ has $2^8$, $rs$ has $2^4$, etc. However, all of the swapped versions of transformations which leave a square unmoved ($s$, $rfs$, and $r^3fs$) have \emph{no} invariants, since the unmoved square is necessarily a different color after transformation. Thus, applying
Burnside's lemma gives:
\[\frac{65536+16+256+16+256+1024+256+1024+0+16+256+16+256+0+256+0}{16}=4324.\]
}
\end{enumerate}
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
Guided only by their feeling for symmetry, simplicity, and
generality, and an indefinable sense of the fitness of things,
creative mathematicians now, as in the past, are inspired by the
art of mathematics rather than by any prospect of ultimate
usefulness.\\
\phantom0\hfill ---Eric Temple Bell
\end{minipage}
}
\end{center}
\end{document}