\documentclass[12pt,HW250,ifthen]{article}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}

\begin{document}

\centerline{Homework 6, Morally due Tue Apr 2, 12:30PM}

\centerline{\bf THE HW IS THREE PAGES LONG!!!!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(24 points)
At the Twitty Family Reunion there are $n$ people.

\begin{enumerate}
\item
Everyone hugs everyone. People even hug themselves!
And Alice-hugs-Bob is counted as different from
Bob-hugs-Alice. How many hugs are there?

\item
Everyone hugs everyone. Except that people do not hug themselves.
Alice-hugs-Bob is counted as different from
Bob-hugs-Alice. How many hugs are there?

\item
Everyone hugs everyone. Except that people do not hug themselves.
Alice-hugs-Bob is counted as the same as
Bob-hugs-Alice. How many hugs are there?

\item
Everyone hugs everyone. People even hug themselves!
Alice-hugs-Bob is counted as the same as
Bob-hugs-Alice. How many hugs are there?


\end{enumerate}

\item
(24 points)
\begin{enumerate}
\item
How many permutations are there of the letters in the sentence:

\centerline{\it pack my box with five dozen liquor jugs}

(ignore spaces, so the question is {\it packmyboxwithfivedozenliquorjugs}

\item
How many permutations are there of the letters in the sentence:

\centerline{\it Don't not ever stop not writing nothing}

(ignore spaces as above)

\end{enumerate}

\centerline{GO TO THE NEXT PAGE}

\newpage


\item
(28 points)
Alice makes lunch for his darling.
There is a sandwich- either PBJ, Turkey, Tomato, Egg salad, or Tuna fish,
a fruit- either apple or blueberries or blackberries or a banana,
and a snack- either pretzels, potato chips or applesauce.

\begin{enumerate}
\item
How many ways can Alice make his darling lunch?
\item
If his darling does not like having apples and applesauce in the same
lunch, then how many lunches can Alice make her?
\end{enumerate}



\centerline{GO TO THE NEXT PAGE}

\newpage

\item
(21 points)
(The first three parts are 0 points so they are really optional
and there is nothing to hand in; however, you should do them for
the enlightnement.)
Let $a_n$ be defined as follows


$a_1=10$

$(\forall n\ge 2)[ a_n = a_{\floor{n^{3/4}}} + 20]$

\begin{enumerate}
\item
(0 points but you will need this for the next part)
Write a computer program to compute, given $n$, $a_1,\ldots,a_n$.
\item
(0 points but you will need it for the next part)
Compute $a_i$ for $1\le i\le 100,000$
\item
(0 points)
Based on your data make a good guess for the form of a good bound on $a_n$.
(Do not look at the next question as it gives away the form.)
\item
(21 points)
Use constructive induction to find constants $A,B\in\N$ such that

$$(\forall n\ge 1)[  a_n \le A\lg\lg n + B ]$$

\end{enumerate}

\end{enumerate}

\end{document}