The question is as follows:
We define on the complete graph $K_n$ with the vertices {$v_1, v_2, ... , v_n$} the following directions: for every j>i, the edge $v_i v_j$ is directed from $v_i$ to $v_j$ if |i-j| is odd, and from $v_j$ to $v_i$ if |i-j| is even. We define the capacity function c($v_i v_j$)=|i-j|, and set $v_1$ as the source and $v_n$ as the sink. Find a maximum flow and a minimum cut.
Obviously the idea is to use the Max-flow Min-cut Theorem. However, I encounter few difficulties when trying to imply it, and I fear it is mostly because of lack of understanding. My idea of solution started with computing $val(f)$ (the value of the flow). Each edge connected to the sink n will thus be negetive if it comes out of it, and positive if it comes into it. So I get:
$val(f)=\sum_{x=1}^{n-1}(-1)^{n-x+1}*(n-x)=\frac{1}{4}(2*(-1)^n*n-(-1)^n+1)$
But then, if n is odd I get that the value is negetive. Am I doing the summation wrong? How can I even find a fitting source-sink cut for a negetive value of the flow? Is it even possible? And when n is even, I get $n/2$. It's still hard to find a fitting source-sink cut with the same capacity, at least I can't think of a method to do so.
Any hints/corrections/ideas will be extremely appreciated.
Update: I managed to find the solution for odd $n$. I defined the following flow: for every $1<x<n$, where x is even, I allow the flow from x to n to be on full capacity (and none out of n). Furthermore, I add a flow from 1 to each such x on full capacity. Lastly, I add a flow between every x and (n-x+1) (which will go in the direction of the lesser one), at full capacity too. I then show that the flow I described is feasible as it holds the conservation constraints for each x (the odd vertices besides 1 and n have no flow coming from them or into them, all set to 0). Once that's done, it's obvious that the capacity of cutting all the vertices besides n is the same as the val(f) of this flow, and therefore it's a maximal flow and minimal cut. The value according to the summation is $\frac{1}{4}(n-1)^2$.
I still struggle with even n. I can see that for every n I checked (up to 10), there was a feasible flow where all the odd vertices gave their full capacity into n (and none out of it of course). However, each required many additional paths to make it feasible. There is a certain pattern to these paths, yet I can't find it. I will extremely appreciate if anyone can guide me to the pattern these paths follow that allow such a flow to be feasible.