\documentclass[letterpaper,11pt]{article}

\newcommand{\removefromfile}[1]{}

\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage[most]{tcolorbox}
\renewcommand{\theenumi}{\alph{enumi}}
\begin{document}
\title{{\bf Problem Set 1 Solutions} }
\author{Name: TODO}

\date{}
\maketitle

\section*{Collaborators}
\begin{tcolorbox}
    List collaborators, if any. 
\end{tcolorbox}

\section*{Use of 312 Learning Assistant}
\begin{tcolorbox}
    List which problems you used the 312 Learning Assistant on.
\end{tcolorbox}


\section{Syllabus and Course Integrity Commitment (5 points)}

\begin{tcolorbox}
    Filled in on gradescope.
\end{tcolorbox}

\section{Mathematical Background [10 points]}

\begin{tcolorbox}
    Filled in on gradescope.
\end{tcolorbox}

\newpage
\section{Film Festival Volunteers (10 points)}
Fourteen people volunteer at a film festival: 5 critics and 9 general volunteers.
\begin{enumerate}
  \item (3 points) How many ways are there to choose 4 volunteers to staff a screening room?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

  \item (3 points) How many ways are there to assign 4 distinct roles (usher, ticket scanner, projection assistant, and crowd manager) from the 14 volunteers?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

  \item (4 points) How many such role assignments are there if at least one critic must be among the four selected volunteers?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

\end{enumerate}

\newpage

\section{DNA codes (16 points)}
A DNA code is a string of length 4 formed from the alphabet \(\{A,C,G,T\}\).
\begin{enumerate}
  \item (3 points) How many DNA codes are there in total?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

  \item (3 points) How many DNA codes contain only \(A\) and \(T\)?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}

  \item (4 points) How many DNA codes contain exactly two \(G\)'s?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}
  \item (6 points) How many DNA codes contain at least one \(A\) and at least one \(T\)?
\begin{tcolorbox}
    TODO: Your solution here.
\end{tcolorbox}
\end{enumerate}

\newpage
\section{The Problem of Grandma Gertrude (10 points)}
Grandma Gertrude has hoarded $s$ neon scratchy sweaters, $d$ terrifying porcelain dolls, and $f$ petrified fruitcakes. Conveniently, she has exactly $s + d + f$ deeply unenthusiastic grandchildren. (The grandchildren are distinguishable, but the horrifying gifts of the same variety are not distinguishable.) Gertrude wants to force exactly one "gift" upon each grandchild. Let $W$ be the set of all ways in which she can ruin their holidays.

\begin{enumerate}
  \item (6 points) The story outlines two different ways Gertrude could assign the gifts, which results in a combinatorial identity. 

\begin{itemize}
    \item \textbf{Method 1:} She could first determine which poor souls get the petrified fruitcakes. Then, she could decide who among her remaining grandchildren has earned a terrifying porcelain doll. The rest get sweaters.
    \item \textbf{Method 2:} She could first decide which grandchildren will suffer her "homemade horrors" (the sweaters and the fruitcakes) and then, from among those unlucky few, determine who truly merits a scratchy neon sweater. The rest of the homemade horror recipients get fruitcakes, and the remaining grandchildren get dolls.
\end{itemize}
Translate both methods into mathematical expressions using binomial coefficients to show the two formulas for $|W|$. In other words, write down the equation that is being proved using a combinatorial argument.

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

  \item (4 points) Suppose Gertrude decides to make things even more personal. She embroiders a unique passive-aggressive message on each sweater, names each porcelain doll, and adds different questionable ingredients to each fruitcake. Now, all $s$ sweaters, $d$ dolls, and $f$ fruitcakes are completely distinguishable from one another. How many distinct ways can she distribute the gifts now?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}
\end{enumerate}

\newpage
\section{Card Selection (15 points)}
\begin{enumerate}
  \item (3 points) How many ways are there to choose 7 cards from a standard 52-card deck?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}


  \item (4 points) How many 7-card hands contain at least one heart?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

  \item (8 points) How many 7-card hands contain at least one card from each suit?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

\end{enumerate}

\newpage
\section{Walking on a Grid (12 points)}
Consider paths on an integer grid that start at \((0,0)\) in which every step increments one coordinate by 1 and leaves the other coordinate unchanged.

\begin{enumerate}
  \item (3 points) How many such paths are there to \((20,30)\)?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}


  \item (3 points) How many such paths to \((20,30)\) pass through the point \((5,10)\)?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}


  \item (6 points) How many such paths to \((20,30)\) pass through \((5,10)\) but do \textbf{not} pass through \((10,15)\)?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

\end{enumerate}

\newpage
\section{Using the Binomial Theorem (12 points)}
\begin{enumerate}
  \item (3 points) What is the coefficient of \(x^4\) in \((1+x)^6\)?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

  \item (4 points) What is the coefficient of \(x^3y^2\) in \((x+2y)^5\)?

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

  \item (5 points) Use the binomial theorem to prove that \[\sum_{k=0}^{n} \binom{n}{k} 2^k = 3^n.\]

  \begin{tcolorbox}
    TODO: Your solution here.
  \end{tcolorbox}

\end{enumerate}

\newpage

\section{A gentle introduction to Python (15 points)}
\begin{enumerate}
\item (10 points) Read the \href{https://edstem.org/us/courses/96846/lessons/162340/slides/954025}{Pset 1 Python Tutorial and Coding Exercises} lesson on Edstem and follow the directions to complete the 5 coding exercises.
\textbf{Then submit all required files to Pset 1 [Coding] on Gradescope}.
You may resubmit to Gradescope as many times as you like.
We do not have any hidden tests for this assignment;
whatever score you see on Gradescope on your last submission will be your final score.
\item (5 points) Read the \href{https://edstem.org/us/courses/96846/lessons/162339/slides/954014}{Edstem lesson} on Python's numpy library and write the reflection described below (be sure to finish part (a) before moving to this part).
You do \textbf{not} need to complete the \emph{coding} exercises for this part (but you might find them to be nice extra practice);
you do have to do the reflection below. 
The goal of this part is to see some more advanced python features that will definitely be useful in the future, but you won't need to use frequently for this course.\\    
    After reading the lesson, write a reflection on what you felt was the most confusing numpy function and/or class to you and why.
If nothing is confusing, explain which function and/or class is the most interesting to you.
We will grade based on completion and effort (since this response can't be ``correct'' or ``incorrect'').
We expect most responses will be 2-4 sentences. %You must read the lesson and write the reflection (regardless of whether you do the coding part).
\textbf{Include your reflections in the pdf you upload to Gradescope with the other problems on this assignment.}




  \begin{tcolorbox}
    (Your solution to part 1 will be on edstem.
    
    TODO: Your reflection for part 2 here.
  \end{tcolorbox}


\end{enumerate}


\end{document}


