\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amssymb}
\pagestyle{fancy}
\lhead{Homework 11M}
\chead{Geoffrey Bostany}
\rhead{Recitation 202}
\begin{document}
\begin{enumerate}
\item if the munky only types 4 letters, the expected number of times that it types math is $\frac{1}{26^4}$. But if he types a million letters, then there are 999,996 different 4 letter strings each with a $\frac{1}{26^4}$ of being MATH. so by the linearity of expectations the expected number of times math appears is $\frac{999,996}{26^4}$
\item so from last week we are given that E[R]=$\sum\limits_{i=0}^{\infty}$Pr[R$\geq$ i ]. So due to the linearity of expectation, we can partition this into \\
E[R]= Pr[R $ \geq $ 1]+Pr[R $ \geq $ 2]+Pr[R $ \geq $ 3]+Pr[R $ \geq $ 4]+Pr[R $ \geq $ 5]+Pr[R $ \geq $ 6]. \\
Also, for each of these, we know that Pr[R $ \geq $ i] = 1 - Pr$[Y < (i-1)]$. \\ Pr[R $ \geq $ 1] = 1 - 0 \\ Pr[R $ \geq $ 2] = 1 - $\frac{1}{6^6}$ = $\frac{46655}{46656}$ \\ Pr[R $ \geq $ 3] = 1 - Pr$[R < 2]$ = 1 - $\frac{2^6}{6^6}$ = $\frac{46592}{46656}$ \\ Pr[R $ \geq $ 4] = 1 - Pr$[R < 3]$ = 1 - $\frac{3^6}{6^6}$ = $\frac{45927}{46656}$ \\ Pr[R $ \geq $ 5] = 1 - Pr$[R < 4]$ = 1 - $\frac{4^6}{6^6}$ = $\frac{46400}{46656}$ \\ Pr[R $ \geq $ 6] = 1 - Pr$[R < 5]$ = 1 - $\frac{5^6}{6^6}$ = $\frac{31031}{46656}$ \\
E[R]= 1+$\frac{46655}{46656}$+$\frac{46592}{46656}$+$\frac{45927}{46656}$+$\frac{46400}{46656}$+$\frac{31031}{46656}$ = 5.64
\item Consider the two components of T which $e$ connects. This edge is needed otherwise T would not be connected. So if e is not present, such as the case with T', there must exist some other edge, $e'$, that connects the two connected componenets. Now again consider T without e and T' without $e'$. both these graphs are now disconnected and no longer spanning trees. But say for example T now contains $e$ and $e'$. the graph is now connected but also cyclical which cannot be either. That means that for a spanning tree, there can only be one edge that connects any two components. Thus if we remove e from T and replace it with $e'$, the graph still remains a spanning tree. likewise for T' without $e'$ but with $e$.
\item consider a vertex x in the graph. We know that it has d degrees and therefore is adjacent to d vertices. This means that we have atleast (d+1) total vertices. Now again consider the vertex y which is adjacent to x. In order for it to have d degrees without any 3-cycles, it must be adjacent to d vertices without being adjacent to a vertex that is already adjacent to x. Therefore we now know that there must be an additional (d-1) vertices present. (d+1)+(d-1)=2d so we know there must be atleast 2d vertices.
\item proof by induction on n \\
IH: assume the claim is true when n=k \\
BC: n=2. clearly there is a path that visits each city once.
IS: n=k+1 \\
we remove one city, called x, and are left with k cities. By the induction statement, we know that there exists a path that visits each city once. We can call this path P. Now when we add x back, we will show that there still exists a path which visits every city once. \\ Assume that there is a road going from the start of the path, s, to x and then a road from x to the end of the path e. Otherwise, the claim would clearly be true. so we assume that there are roads $s \to x$ and $x \to e$. Now, there are also roads between x and every other city on the path which are between s and e. No matter which direction these roads go, there will always be 2 roads adjacent each other that go directly from the path P down to x and then back to the very next city on the path. We know this to be true because if it were false, that means that either every path would have to be going away from x or every path would go toward x which contradicts are earlier assumption that $s \to x$ and $x \to e$. Thus there will always be some city which has a path that goes from P to X and then back to the very next city on P. therefore there exists a path which visits every city only once.
\end{enumerate}
\end{document}
