= Solution
Orient every edge of the feasible <convex polytope> in the direction of increasing objective. Write
$$
O=000,\qquad A=(1/2,1,1),\qquad
B=(1,1/2,1),\qquad C=(1,1,1/2).
$$
The possible improving <simplex method> paths from $O$ to $A$ are
$$
\begin{aligned}
&O\to010\to011\to A,
&&O\to001\to011\to A,\\
&O\to100\to110\to C\to A,
&&O\to010\to110\to C\to A,\\
&O\to100\to110\to C\to B\to A,
&&O\to010\to110\to C\to B\to A,\\
&O\to100\to101\to B\to A,
&&O\to001\to101\to B\to A.
\end{aligned}
$$
These exhaust the directed edge graph: the ordinary cube edges remain except those incident to the removed vertex $111$; each such edge ends at one of $A,B,C$; and the cutting face contributes the triangle with edges $AB,AC,BC$.
The first two paths use three pivots, while the two paths through both $C$ and $B$ use five. Therefore the smallest and largest possible numbers of simplex steps are
$$
\boxed{3\text{ and }5},
$$
and the total number of distinct outcomes is
$$
\boxed{8}.
$$
This is the <simplex paths on a cube with one truncated corner> calculation.
Back to article page
