That is the solution! See? It's so simple it seems like a formulation of the problem itself!
The solution is to think of the input ('001') in terms of an n-dimensional cube, where n is the length of the input.
So for example, a binary logic with 5 bits ('01010') would require a 5-dimensional cube. From there, you check whether moving from one input ('00001') to an adjacent input ('00011') causes a flip in the output. If it does, you label it as "red", and if it doesn't, you label it as "blue". Then you merely find the vertex with the highest number of opposite colors, and the number of opposite colors is the sensitivity.
The article is quite clear that this formulation of the problem has been around for a while and did not lead to a proof until Huang had his special insight.
> Huang knew, as did the broader research community, that the sensitivity conjecture could be settled if mathematicians could prove an easily stated conjecture about collections of points on cubes of different dimensions.
> In 1992, Craig Gotsman, now of the New Jersey Institute of Technology, and Nati Linial of Hebrew University figured out that proving the sensitivity conjecture can be reduced to answering a simple question about cubes of different dimensions: If you choose any collection of more than half the corners of a cube and color them red, is there always some red point that is connected to many other red points?
An easier way to think of it is just as a matrix where each vertex is connected to n other vertices. The reason an n-cube is used specifically is because the bits correspond to spatial coordinates, which obviously require a uniform structure (like a cube if we're talking 3D) in order to make sense.
