<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{amssymb}
%\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{fancybox}
\newcommand{\IR}{\mathbb{R}}

\newcommand{\age}{\mathord{\it age}}

\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsulenew}[1]{\vspace{0.5em}
  \shadowbox{%
    \begin{minipage}{.90\linewidth}%
      #1%
    \end{minipage}}
  \vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document} 

\begin{center} \Large\bf
COMP 2804 --- Assignment 1 
\end{center} 

\noindent {\bf Due:} Sunday September 27, 11:55 pm. 

\vspace{0.5em} 

\noindent {\bf Assignment Policy:} 
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through 
      cuLearn. 
\item {\bf Late assignments will not be accepted. I will not reply to 
      emails of the type ``my internet connection broke down at 
      11:53pm'' or ``my scanner stopped working at 11:54pm'', or 
      ``my dog ate my laptop charger''.} 
\item You are encouraged to collaborate on assignments, but at the level 
      of discussion only. When writing your solutions, you must do so 
      in your own words. 
\item Past experience has shown conclusively that those who do not put 
      adequate effort into the assignments do not learn the material and 
      have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
      \begin{itemize}
      \item You must justify your answers. 
      \item The answers should be concise, clear and neat.
      \item When presenting proofs, every step should be justified.
      \end{itemize}
\end{itemize}

\vspace{1em} 

\begin{question} 
\begin{itemize}
\item Write your name and student number. 
\end{itemize}
\end{question} 

\begin{question} 
Recall that $K_n$, where $n \geq 2$ is an integer, denotes the 
\emph{complete graph} with $n$ vertices. This graph has $n \choose 2$ 
edges, i.e., one edge for each pair of distinct vertices. 

Let $k \geq 1$ be an integer and let $L$ be a set of size $k$. If each 
edge of $K_n$ is labeled with one element of $L$, then we say that $K_n$ 
is $k$-\emph{labeled}. Three pairwise distinct vertices $u$, $v$, and 
$w$ of $K_n$ define a \emph{boring} triangle, if the three edges 
$uv$, $uw$, and $vw$ have the same label. 

In this question, you will prove the following statement $S(n,k)$ 
for all integers $n$ and $k$ with $n \geq 3 \cdot k!$: 
\begin{center}
 $S(n,k)$: Every $k$-labeled $K_n$ has a boring triangle. 
\end{center} 
(Note that in class, we have proved statement $S(n,2)$ for all 
$n \geq 6$.) The proof will be by induction on $k$. 
\begin{itemize}
\item Base case: Explain, in a few sentences, why statement $S(n,1)$ is 
true for all integers $n \geq 3$.
\item Induction step: Let $k \geq 2$ and assume that statement $S(m,k-1)$ 
is true for all integers $m \geq 3 \cdot (k-1)!$. Prove that statement 
$S(n,k)$ is true for all integers $n \geq 3 \cdot k!$.

\noindent 
\emph{Hint:} Let $u$ be an arbitrary vertex of $K_n$. Argue that among 
all edges that have $u$ as a vertex, at least $\lceil (n-1)/k \rceil$ 
have the same label. 
\end{itemize}
\end{question} 

\begin{question} 
Let $k \geq 2$ be an integer and consider the set $S = \{1,2,\ldots,k\}$. 
For any integer $n \geq 2$, determine the number of sequences 
$(a_1,a_2,\ldots,a_n)$ of length $n$, where each element belongs to $S$ 
and no two consecutive elements are the same.  
\end{question} 

\begin{question} 
Zoltan's House of Pizza is a popular restaurant in downtown Ottawa. 
The daily dinner special is Zoltan's Meal Deal:  
You choose between standard dough and gluten free dough; you choose 
one of chicken, beef, pork, and shrimp; you choose 
one out of five different sauces; you choose three out of seven different
cheeses; you choose any subset of twenty different toppings; and, finally, 
you choose four out of nine different beers. 

\begin{itemize} 
\item Determine the number of Zoltan's Meal Deals, if the cheeses chosen 
must be distinct and the beers chosen must be distinct. 
\item Determine the number of Zoltan's Meal Deals, if the cheeses chosen 
are not necessarily distinct and the beers chosen are not necessarily 
distinct. 
\end{itemize} 
\end{question} 

\begin{question}
This fall term, $230$ students have registered for COMP 2804B. 
While watching video lectures, $150$ students do not wear pants and 
$110$ students drink beer.  

Determine the best possible lower bound on the number of students who 
do not wear pants and drink beer while watching video lectures. 
\end{question} 

\begin{question} 
In class, we have seen how to determine the number of solutions of the 
equation 
\begin{equation}  \label{eq99} 
     x_1 + x_2 + x_3 = 99 ,
\end{equation} 
where $x_1 \geq 0$, $x_2 \geq 0$, and $x_3 \geq 0$ are integers. 

\begin{itemize}
\item Determine the number of solutions of (\ref{eq99}), where 
$x_1 \geq 40$, $x_2 \geq 0$, and $x_3 \geq 0$ are integers. 
\item Determine the number of solutions of (\ref{eq99}), where 
$x_1 \geq 0$, $x_2 \geq 50$, and $x_3 \geq 0$ are integers. 
\item Determine the number of solutions of (\ref{eq99}), where 
$x_1 \geq 0$, $x_2 \geq 0$, and $x_3 \geq 55$ are integers. 
\item Determine the number of solutions of (\ref{eq99}), where 
$x_1 \geq 40$, $x_2 \geq 50$, and $x_3 \geq 0$ are integers. 
\item Use the Principle of Inclusion and Exclusion to determine the 
number of solutions of (\ref{eq99}), where 
$0 \leq x_1 \leq 39$, $0 \leq x_2 \leq 49$, and $0 \leq x_3 \leq 54$ are 
integers. 
\end{itemize} 
\end{question} 

\begin{question} 
Let $n \geq 2$ be an integer and consider the set $S = \{1,2,\ldots,n\}$. 
A permutation of $S$ can be regarded as a bijection 
$f : S \rightarrow S$. For any integer $i \geq 1$, define 
\[ f^i(x) = \underbrace{f(f(f(\cdots f}_{\mbox{$i$ times}} 
               (x) \cdots))) . 
\] 
In words, to obtain $f^i(x)$, we start with $x$ and apply the function 
$i$ times. 

If $x$ is an element of $S$, then the \emph{cycle} of $x$ is the 
sequence 
\[ ( x, f^1(x),f^2(x) , \ldots , f^{m-1}(x) ) , 
\]
where $m$ is the smallest positive integer such that $f^m(x) = x$. 

The \emph{cycle decomposition} of $f$ is obtained as follows: 

\vspace{0.5em} 

\noindent 
{\bf Step 1:} Initially, all elements of $S$ are unmarked and the 
cycle decomposition is empty. 

\vspace{0.5em} 

\noindent 
{\bf Step 2:} Repeat the following, until all elements of $S$ have been 
marked: Take the smallest unmarked element, say $x$, in $S$. Mark all 
elements in the cycle of $x$, and add this cycle to the cycle 
decomposition. 

\vspace{0.5em} 

For example, the cycle decomposition of the permutation 
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|}
\hline
$f(x)$ &amp; 7 &amp; 4 &amp; 6 &amp; 8 &amp; 1 &amp; 3 &amp; 5 &amp; 2 \\ 
\hline
$x$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 \\
\hline
\end{tabular}
\end{center}
is given by 
\[ (1,7,5) , (2,4,8) , (3,6) .
\] 
This cycle decompositions consists of three cycles, having lengths 
$3$, $3$, and $2$, respectively. 

\begin{itemize}
\item Let $x$ be an element of $S$. Explain why there exists a 
positive integer $m$ such that $f^m(x) = x$. 
\item Prove or disprove the following statement: Let $k$ be an 
integer with $k &gt; n/2$. The cycle decomposition can have more 
than one cycle of length $k$. 
\item Let $k$ be an integer with $k &gt; n/2$. Prove that the number of 
permutations of $S$ whose cycle decompositions contain a cycle of length 
$k$ is equal to 
\begin{equation} \label{eq} 
   {n \choose k} \cdot (k-1)! \cdot (n-k)! . 
\end{equation} 
\item Use algebra to simplify the expression in (\ref{eq}) 
to $n! / k$. 
\end{itemize} 




\end{question} 

\begin{question}  
Let $n \geq 2$ be an integer and consider the set 
$S = \{1,2,\ldots,n\}$. Recall that a permutation of $S$ is an 
ordered sequence $a_1, a_2, \ldots, a_n$, in which every element 
of $S$ occurs exactly once. 

Let $i$ be an integer with $1 \leq i \leq n$. We say that $i$ is 
a \emph{cool index}, if $a_i \neq i$. We say that $i$ is a 
\emph{super cool index}, if $i$ is cool and none of the indices 
$i+1,i+2,\ldots,n$ is cool; in other words, $i$ is the rightmost 
cool index in the permutation. 

For example, in the permutation below, the indices $1$ and $4$ are cool,
whereas the index $4$ is super cool. 
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|}
\hline
$a_i$ &amp; 4 &amp; 2 &amp; 3 &amp; 1 &amp; 5 &amp; 6 &amp; 7 &amp; 8 \\ 
\hline
$i$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 \\
\hline
\end{tabular}
\end{center}

\begin{itemize} 
\item Determine the number of permutations of the set $S$ that have 
at least one cool index. 
\item Prove or disprove the following statement: There exists a 
permutation of $S$ in which the index $1$ is super cool. 
\item Let $k$ be an integer with $1 \leq k \leq n-1$. 
Determine the number of permutations of $S$ in which the index 
$k+1$ is super cool. 
\item Use the above results to prove that 
\[ \sum_{k=1}^{n-1} k \cdot k! = n! - 1 . 
\] 
\end{itemize} 
\end{question} 

\begin{question} 
Let $n \geq 1$ be an integer and consider the set 
$S = \{0,1,\ldots,3n\}$. For any integer $k$, let $N_k$ be the number of 
subsets $X$ of $S$ for which $|X|=2n+1$ and $\min(X)=k$. 
\begin{itemize} 
\item Determine the values of $k$ for which $N_k \neq 0$. 
\item Let $k$ be an integer with $0 \leq k \leq n$. Determine the 
value of $N_k$. 
\item Use the above results to prove that 
\[ \sum_{k=0}^n {{3n-k} \choose {2n}} = {{3n+1} \choose n} . 
\] 
\end{itemize} 
\end{question} 

\end{document} 
</pre></body></html>