Let $N$ be a net whose vertices are all subsets of set $\{1,..,k\}$ and an egde connect only these two subsets that differ in exactly one element. If this element is $x$ then this edge has capacity $2^x$ and is directed to the bigger subset. Find maximum flow from the source $z=\emptyset$ to the sink $s=\{1, . . , k\}$.
I know that the number of vertices is $2^k$ and every path from source to sink is$k$ long. On every of these paths there is an edge with capacity $2^1,..,2^k$.
The answer is that the maximum flow equals $2^k$ but I don't know how to come to this solution
The idea is to prove it by induction of $k$ but I don't know how. Help will be
appreciated.
$k=2,3$ with capacity of edges">
To prove that more than $2^k$ is impossible, it suffices to find a cut with that capactiy. Let $S$ be the set of vertices whose subset does not contain $1$, and let $T$ be the vertices who do contain $1$. There are $2^{k-1}$ edges from $S$ to $T$, each with capacity $2^1$, so the capacity is $2^k$.
To prove that $2^k$ is possible, it suffices to find a flow. Here is the basic idea. You have $2^k$ units of stuff at the source, $\varnothing$. Send half of that to $\{k\}$. Now there is $2^{k-1}$ at $\varnothing$ and $2^{k-1}$ at $\{k\}$. Next, recursively send the $2^{k-1}$ at $\varnothing$ to $\{1,2,\dots,k-1\}$, and recursively send the $2^{k-1}$ at $\{k\}$ to $\{1,2,\dots,k-1,k\}$. Finally, reunite the two halves by sending the $2^{k-1}$ at $\{1,2,\dots,k-1\}$ to $\{1,2,\dots,k\}$.