From 56b740565fd6467564be28b5465ad24cccf71109 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 16 Jan 2020 21:24:46 -0500 Subject: moved comb hw --- tech-math/comb/hw6.tex | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 tech-math/comb/hw6.tex (limited to 'tech-math/comb/hw6.tex') diff --git a/tech-math/comb/hw6.tex b/tech-math/comb/hw6.tex new file mode 100644 index 0000000..6d0ab8c --- /dev/null +++ b/tech-math/comb/hw6.tex @@ -0,0 +1,33 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} + +\noindent {\bf Q1)} %#13:2 + +Bob is right because if the flow of the network were greater than eighteen, the flow into the sink (T) would have to be greater than 18, which is greater than the sum of the capacities of incoming edges from G, A, and H. + +\noindent {\bf Q2)} %#13:3 + +$(S,H,B,I,A,D,T)$ has a flow $\delta = 1$ because of the limiting factor BI. The update would change SH to a flow of 2, HB to 2, IB to 0, IA to 10, and AT to 4---setting $\hat\phi = \phi + 1 = 16.$ + +\noindent {\bf Q3)} %#13:6 + +54. + +\noindent {\bf Q4)} %#13:10 + +$\phi = 73.$ + +Cut: $$\left\{ {L = \{S,C,F,G,E\} \atop U = \{T,A,B,D\}}\right\}$$ + +\noindent {\bf Q5)} %#10:4 + +According to Theorem 7.12, $$lim_{n\to\infty} {d_n\over n!} = {1\over e}.$$ This means that the odds one of the permutations Zori chooses is a derangement is approximately ${1\over e}$, meaning that if Bob paid one dollar to pay, he should win with a slightly higher payout around $2.72$ (to make the game fair). + +\noindent {\bf Q6)} %#10:5 + +\pre{a.} Because the connections are independent, the graph generation can be simulated as only running on that 3-element subgraph. Because it is connected if all three possible edges exist, the odds that all three were selected to exist is ${1\over2}^3 = {1\over8} = P(E_S).$ + +\pre{b.} $P(E_S) = P(E_S|E_T)$ because $P(E_S) = {1\over 8}$ and $E_T$ being true guarantees nothing about any of the independent selections on $S$ (i.e. if their intersection is one vertex, $E_T$ doesn't show that any vertex pair on $S$ shares an edge). + +\pre{c.} Regardless of if connections form between 3 and 5 or 4 and 5, both conditions state that $\{2,3,4\}$ is fully connected. Thus, $23$ is an edge, and the odds that $S$ is connected are equal to the independent coin tosses respective to $12$ and $13$ (a $1\over4$ chance in either case). + +\bye -- cgit