% !TEX program = pdflatex
% ---------------------------------------------------------------------------
\documentclass[10pt,a4paper,english]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{bbm}
\usepackage{mathtools}
\usepackage{physics}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{fancyvrb}
\usepackage{nth}
\usepackage{multicol}
\usepackage{soul}
\usepackage{siunitx}
\makeatletter
\newcommand*{\rom}[1]{\expandafter\@slowromancap\romannumeral #1@}
\makeatother
\renewcommand{\imath}[0]{ i }
\newcommand{\Natural}[0]{\mathbbm{N}}
\newcommand{\Integer}[0]{\mathbbm{Z}}
\newcommand{\Real}[0]{\mathbbm{R}}
\newcommand{\Rational}[0]{\mathbbm{Q}}
\newcommand{\Complex}[0]{\mathbbm{C}}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\newcommand{\subsets}[2]{\qty[\genfrac{}{}{-2pt}{0}{#1}{#2}]}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\id}{id}
\title{CS40 Winter 2021 Homework \#9}
\begin{document}
\maketitle
\paragraph{Notes}
\begin{itemize}
\item
You may work with a partner in order to understand the problems and discuss how to approach them.
If you do so, write clearly on your assignment the name of the student you collaborated with.
\item
\emph{Justify your answers! A numeric answer is not sufficient.
You may leave your answers in analytic form as fractions, factorials and binomials/multinomials.}
\item
Please re-read the ``Conduct'' section in the class syllabus.
\item
No late submissions! Turn-in what you have by the deadline.
\end{itemize}
\dotfill
\begin{enumerate}
\item
\begin{enumerate}
\item
How many three-digit natural numbers can be assembled from the digits $2, 3, 5, 6, 7$, if the digits are not repeated?
How many of these numbers are divisible by five?
\item
If the number of elements $n$ is increased by two, then the number of $3$-combinations from those $n$ elements increases by $324$.
Find the number of elements $n$ (after increase).
\item
How many positive integers divisible by five smaller than \num{8000} exist, if they are only made out of the digits $0, 1, 2, 5, 7, 9$?
\item
How many permutations of the 26 letters of the English alphabet do not contain any of the strings ``fish'', ``bird'' or ``sock''?
\item
We have \SI{6}{\litre} of milk and 4 empty bottles of milk. Using a \SI{0.5}{\litre} measuring cup, in how many ways can we distribute our milk
into the bottles? (you may assume distinguishable bottles).
\item
Assume that the relation ``friend'' is symmetric.
Show that if $n\geq 2$, then in any group of $n$ people there are two with the same number of friends in that group.
\end{enumerate}
\item
Suppose there are 15 blue balls and 15 black balls, each marked with an integer between 1 and 100 (inclusive),
and no integer appears on more than one ball (of any colour).
\begin{enumerate}
\item
How many possible ways are there to draw 10 balls and place them in a line.
\item
How many possible ways are there to draw 10 balls and put them in a box (i.e. ignoring order).
\item
The value of a pair of balls is the sum of the numbers on the balls.
Show there are at least two pairs, consisting of one blue and one black ball, with the same value.
Show that this is not necessarily true if there are 13 balls of each colour.
(Be careful! Showing that a particular argument fails is not enough to show that something can not be done in general.)
\end{enumerate}
\item
\begin{enumerate}
\item
\begin{enumerate}
\item How many 9-bit binary strings are there which begin with 101?
\item How many of the strings you counted in part (a) also end with 111?
\item How many 9-bit binary strings are there which begin with 101 or end with 111?
\end{enumerate}
\item How many strings of four decimal digits
\begin{enumerate}
\item do not contain the same digit twice?
\item end with an even digit?
\item have exactly three digits that are 9s?
\end{enumerate}
\item A test with 20 questions is a multiple choice test with 5 answers for each
question but only 1 correct answer to each question. How many ways are there to have
\begin{enumerate}
\item no correct answers?
\item exactly 6 correct answers?
\item at least 6 correct answers?
\end{enumerate}
\end{enumerate}
\item
Consider the equation $x_1+x_2+x_3+x_4=22$. Calculate the number of solution if:
\begin{enumerate}
\item
$x_j$-s are non-negative integers.
\item
$x_j$-s are non-negative integers and $10$.
\end{enumerate}
\end{document}