1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
|
