% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vy{\mathbf{y}}
\def\vz{\mathbf{z}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 10 --- Solutions}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Pigeonhole
% \clearpage
\problem\ [10pts] Let $n_1,\dots,n_t$ be positive integers. Prove that if $1 + \sum_{i=1}^t n_i$ objects are placed into $t$ boxes, then for some $i$, the $i$th box contains at least $n_i + 1$ objects.

\begin{proof}
We prove by the contrapositive.
Suppose some number of objects are placed into $t$ boxes such that the $i$th box contains at most $n_i$ objects.
Then the number of objects is at most $\sum_{i=1}^t n_i$.
Thus, we did not place $1 + \sum_{i=1}^t n_i$ objects.
\end{proof}

% Pigeonhole
 \clearpage
\problem\ [15pts] Recall the definition of the Ramsey number $r(k,\ell)$.

\textbf{a.} [5pts] Prove that $r(k,2) = k$.

\begin{proof}
Let $c : E_k \to \{ R, B\}$ be a 2-coloring.
If any pair $\{i,j\} \in E_k$ receives color $B$ then there exists a $B$-colored clique of size 2.
Otherwise, all pairs $\{i,j\} \in E_k$ receive color $R$ and there exists an $R$-colored clique of size $k$.
Thus, $r(k,2) \leq k$.

To show $r(k,2) > k-1$, use the 2-coloring $c : E_{k-1} \to \{R,B\}$ where every pair $\{i,j\} \in E_{k-1}$ receives the color $R$.
Thus there is no $B$-colored clique of size 2 and there is no clique of size $k$ at all.
\end{proof}

\textbf{b.} [10pts] Use problem 1, part (a), and the fact that $r(3,3) = 6$ to prove that $r(3,4) \leq 10$. 

\begin{proof}
Let $c : E_{10} \to \{R, B\}$ be a 2-coloring.
We will show that $c$ contains either an $R$-colored clique of size 3 or a $B$-colored clique of size $4$.

Consider the pairs $\{i,10\}$ for $1 \leq i \leq 9$.
There are 9 pairs that receive two colors.
Let $n_1 = 3$ and $n_2 = 5$.
Since $9 = 1 + (3 + 5)$, then by Problem 1 either there are $n_1+1=4$ pairs $\{i,10\}$ that are colored $B$ or there are $n_2+1=6$ pairs $\{i,10\}$ that are colored $R$.

If there are 4 pairs $\{i,10\}$ colored $B$, without loss of generality we can let the pairs $\{i,10\}$ with $1 \leq i \leq 4$ be the pairs colored $B$.
Since $r(2,4) = r(4,2) = 4$ by part (a), the 2-coloring $c$ on pairs $\{i,j\}$ with $1 \leq i < j \leq 4$ either has a $B$-colored edge (completing a $B$-colored clique of size 3 with the vertex 10) or has an $R$-colored clique of size 4.
Thus, $c$ contains a $B$-colored clique of size 3 or an $R$-colored clique of size 4.

If there are 6 pairs $\{i,10\}$ colored $R$, without loss of generality we can let the pairs $\{i,10\}$ with $1 \leq i \leq 6$ be the pairs colored $R$.
Since $r(3,3) = 6$, the 2-coloring $c$ on pairs $\{i,j\}$ with $1 \leq i < j \leq 6$ either has a $B$-colored clique of size 3 or has an $R$-colored clique of size 3 (completing an $R$-colored clique of size 4 with the vertex 10).
Thus, $c$ contains a $B$-colored clique of size 3 or an $R$-colored clique of size 4.
\end{proof}

% Double counting or identities
 \clearpage
\problem\ [10pts] Let $k$ and $n$ be integers with $0 \leq k \leq n$. Give a formula for the coefficient of $x^{2k}$ in the polynomial $(x + \frac{1}{x})^{2n}$. Simplify the formula as much as possible.

\begin{proof}
By the binomial theorem with $x = x$ and $y = \frac{1}{x}$, we have
\[
	\left(x+\frac{1}{x}\right)^{2n} = (x+y)^{2n} = \sum_{i=0}^{2n} \binom{2n}{i}x^i y^{2n-i} = \sum_{i=0}^2n \binom{2n}{i}x^ix^{-(2n-i)} = \sum_{i=0}^{2n} \binom{2n}{i} x^{2i-2n}.
\]
The monomial $x^{2k}$ appears when $2k = 2i-2n$, hence when $k = i - n$ and $i = n+k$.
Thus, the coefficient of $x^{2k}$ is given by the binomial coefficient $\binom{2n}{n+k}$.
\end{proof}

% Double counting or identities
 \clearpage
\problem\ [10pts] Give a combinatorial proof that $\sum_{k=0}^n k\binom{n}{k}^2 = n\binom{2n-1}{n-1}$. [Hint: Select a committee of size $n$ from a group of $n$ mathematicians and $n$ computer scientists and select a chair for the committee that is a mathematician.]


\begin{proof}
We will use double-counting to select a committee of size $n$ from a group of $n$ mathematicians and $n$ computer scientists and select a chair for the committee that is a mathematician.

We could select a mathematician as the chair in $n$ ways.
There are $2n-1$ people remaining to fill the remaining $n-1$ positions in the committee, so there are $\binom{2n-1}{n-1}$ ways to complete the committee. 
Thus, there are $n\binom{2n-1}{n-1}$ ways to select this committee.

We could also first select the number of mathematicians in the committee.
Let $k$ be the number of mathematicians to be on the committee.
Then there are $\binom{n}{k}$ ways to select the mathematicians.
There are $\binom{n}{n-k}$ ways to select the computer scientists on the committee.
Recall that $\binom{n}{n-k} = \binom{n}{k}$.
Finally, there are $k$ mathematicians in the committee for us to select the chair.
Hence, there are $\sum{k=1}^n k\binom{n}{k}^2$ possible selections.
Since $0 \binom{n}{0}^2 = 0$, we can add the $k =0$ term to our sum, resulting in $\sum_{k=0}^n k\binom{n}{k}^2$ possible committees.

Since these two expressions are counting the same thing, they must be equal.
\end{proof}







\end{document} 