Finding the dichotomy that maximizes information gain for a classifier?
As in the discussion, there are too many "features" for this to be in interesting question. In particular, letting $A = C^{-1}(1)$, the set of positive examples, then $H(C|A) = H(C|C) = 0$ so information gain is $H(C)$, which is maximal. 

This is obvious in retrospect, in order to decrease the entropy maximally, make $C$ deterministic on $A$ and $A^c$. 

For decision trees, the point is that we have a limited collection of features, specifically excluding C, to split our data set around.