From cf201409a092b037371d09b4e09a16a0d7974898 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Wed, 20 Nov 2019 07:23:06 -0500 Subject: update --- tech-math/hw6.tex | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 tech-math/hw6.tex (limited to 'tech-math/hw6.tex') diff --git a/tech-math/hw6.tex b/tech-math/hw6.tex new file mode 100644 index 0000000..6d0ab8c --- /dev/null +++ b/tech-math/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