\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Zplus}{\Z^+}

\begin{document}
\title{Math 228: Homework 1}
\author{Mary Radcliffe}
\date{due 9 Sept 2016}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).

\begin{enumerate}

\item (*) Let $n\in \Zplus$. We call a subset of $[n]$ odd if it has odd size, and even if it has even size.

Prove that the number of odd subsets of $[n$] is equal to the number of even subsets of $[n]$.

\item\label{presents} (*) You have 20 different presents to distribute among 10 children. You may distribute presents in any way; it is even permissible that all the presents go to the same child. How many ways can the presents be distributed?

\item Repeat problem \ref{presents}, but add the restriction that each child must get at least one present.

\item $n$ boys and $n$ girls all go to a dance. In how many ways can they partner up to dance together, assuming that each partnership is of one boy and one girl?

\item (*) Prove each of the following binomial identities in two ways; one using algebra, and one using combinatorics.
\begin{enumerate}
\item ${n\choose 2}+{n+1\choose 2} = n^2$
\item ${n\choose k}{k\choose j} = {n\choose n-j}{n-j\choose k-j}$
\end{enumerate}

\item (*) You have 10 different colored balls in a single pile. You perform the following procedure:
\begin{enumerate}
\item[i.] Split the balls into two piles (in any way)
\item[ii.] Select a pile containing at least 2 balls (if it exists)
\item[iii.] Split that pile into two piles (in any way)
\item[iv.] Repeat steps ii \& iii until you cannot
\end{enumerate}
How many steps will you take until the procedure is completed? In how many different ways can this be done?

\item A 4-digit number is called a palindrome if it is the same when the digits are read in reverse. For example, 7337 and 3333 are 4-digit palindromes, but 1337 and 0990 are not. Note that 0990 doesn’t count because it’s actually a 3-digit number.

A 4-digit number is called an almost-palindrome if there is a way to change exactly one digit so that the result is a 4-digit palindrome. For example, 1337, 1501, and 1990 are 4-digit almost-palindromes (they could become 1331 or 7337, 1001 or 1551, and 1991), but 1234, 0991, and 1331 are not. The issue with 0991 is again that it is actually a 3-digit number, and the issue with 1331 is that if you change any digit, then it becomes a non-palindrome.

How many 4-digit almost-palindromes are there?

\end{enumerate}

\end{document}