\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{13: The Probabilistic Method}{Due Friday, Week 8}



Do \textbf{one} of the three problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!  

\begin{enumerate}
\item Prove that for any two positive integers $k, l$, we have
\begin{align*}
R(k,l) \leq \binom{k+l-2}{k-1}.
\end{align*}
\item Take any subset $B$ of $n$ positive integers $\{b_1, \ldots b_n\}$.  Using the probabilistic method, show that $B$ contains a sum-free\footnote{A subset $S$ of $\mathbb{R}$ is called \textbf{sum-free} if for any $a, b \in S$, $a+b$ is not in $S$.  For example, $\{1,3,5\}$ is sum-free.} subset of size $\geq n/3$.  

Hint: pick some prime $p$ that's larger than twice the maximum absolute value of elements in $B$, and look at $B$ modulo $p$ (in other words, look at $B$ as a subset of $\mathbb{Z} / p\mathbb{Z}.$  Because of our clever choice of $p$, all of the elements in $B$ are distinct mod $p$ (why?) Now, look at the sets $xB := \{x \cdot b: b \in B\}$ in $\mathbb{Z} / p\mathbb{Z}.$  Using the probabilistic method, show that there is some value of $x$ such that more than a third of the elements of $xB$ lie between $p/3$ and $2p/3$.  Use this to attack your problem.
\item A \textbf{$n$-vertex tournament} is any way to take $K_n$ and assign an orientation to each of its edges.  For example, here is a tournament on $4$ vertices:
\begin{center}
\includegraphics[height=.7in]{ham_path1.pdf}
\end{center}
A \textbf{Hamiltonian path} on an oriented graph is any path that only travels on edges along their orientations, that visits each vertex exactly once.  We draw an example of a Hamiltonian path on the graph above here:
\begin{center}
\begin{center}
\includegraphics[height=.7in]{ham_path2.pdf}
\end{center}
\end{center}
Prove that for any $n$, there is a $n$-vertex tournament with at least $\frac{n!}{2^{n-1}}$ different Hamiltonian paths.
\end{enumerate}



\end{document}