\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{hhline}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\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}
\usepackage{makecell}
\newcolumntype{x}[1]{>{\centering\arraybackslash}p{#1}}
\usepackage{tikz}

\input{preamble.tex}


\newcommand\diag[4]{%
  \multicolumn{1}{p{#2}|}{\hskip-\tabcolsep
  $\vcenter{\begin{tikzpicture}[baseline=0,anchor=south west,inner sep=#1]
  \path[use as bounding box] (0,0) rectangle (#2+2\tabcolsep,\baselineskip);
  \node[minimum width={#2+2\tabcolsep-\pgflinewidth},
        minimum  height=\baselineskip+\extrarowheight-\pgflinewidth] (box) {};
  \draw[line cap=round] (box.north west) -- (box.south east);
  \node[anchor=south west] at (box.south west) {#3};
  \node[anchor=north east] at (box.north east) {#4};
 \end{tikzpicture}}$\hskip-\tabcolsep}}

\begin{document}

\homework{16: More Probability}{Due Thursday, Week 9, at the start of class.}


Solve \textbf{one} of the following \textbf{three} problems.    As always, prove your claims/have fun!  

\begin{enumerate}
\item[0.] Solve any un-signed-up-for problems from HW\#15!
\item Take the collection $S_n$ of all permutations of the numbers $\{1, 2, \ldots n\}$: that is, let
\begin{align*}
S_n = \{ f: \{ 1, 2, \ldots n\} \to \{1, 2, \ldots n\}, f \textrm{ is a bijection.}\}
\end{align*}
For example, $S_2$ contains two elements: the map that sends $1 \to 1, 2 \to 2$ and the other map that sends $1 \to 2, 2 \to 1$.

Choose a permutation $f$ at random from $S_n$.  What are the odds that your permutation has no ``fixed'' points: that is, that $f(k) \neq k$ for every $k$?  (You will get a formula that depends on $n$ here.)
\item Given any two points on the boundary of a unit circle, you can draw a line segment between them: call this a \textbf{chord}.  Randomly pick a chord on a circle of radius 1.  What is the probability that it is longer than $\sqrt{3}$?
\item A dizzy lemming is standing on the edge of a cliff; from where it is currently placed, any step towards the cliff will cause it to fall off of the cliff.  At each time step, it takes a random step either towards or away from the cliff (with towards and away both occurring with probability 1/2.)  Suppose that its warren is $n$ steps away from the cliff, and that if it makes it to either its warren or falls off the cliff it stops wandering (because it either goes to bed or is very sad.)

What are the odds that it falls off the cliff?
\end{enumerate}





\end{document}








