\documentclass[12pt]{exam}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\newcommand{\ppp}{\par \noindent}
\newcommand{\R}{\mathbb{R}}
\newcommand{\ds}{\displaystyle}
\newcommand{\PS}{\mathcal{P}}
\pagestyle{empty}
\begin{document}
\centerline{\textbf{Deceptively Uninspiring Homework 5}}
\centerline{Due Wednesday May 21th at the beginning of class}
\bigskip
You may handwrite or type your answers/solutions/proofs. I highly encourage the use of a mathematical typesetting language (like \LaTeX). If you handwrite, please make sure that your work is legible, and please staple your homework when you turn them in.
\begin{questions}
\question Given a positive integer $n$, a finite sequence of positive integers $(a_1,\ldots, a_k)$ is said to be \emph{coherent} if $\sum_{i=1}^ka_i=n$. Show that the number of coherent sequences of $n$ is $2^{n-1}$. For instance, here are the $4=2^{3-1}$ coherent sequences of $3$: $(3)$, $(2,1)$, $(1,2)$ and $(1,1,1)$.
\question Prove using induction that $n!>n^2$ for $n\geq 4$.
\question In a \emph{labeled} tournament, the vertices are numbered from $1$ to $n$. The labeling matters, but which vertex is drawn where doesn't matter. Find (and prove) a formula for the number of labeled tournaments with $n$ vertices.
\question For $k\geq 3$, a $k$-cycle in a tournament is a sequence of vertices $v_1$, $v_2$, $\ldots$, $v_k$ with arcs $v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k \rightarrow v_1$. Prove that if a tournament contains a $k$-cycle for some $k>3$, then it also contains a $3$-cycle.
\end{questions}
\end{document}