Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges?
I know that the answer is no for general graphs, since you can take a $K_6$ plus a disjoint edge. I also know that if we don't require the number of edges to be a power of 2, the answer is again no as shown by a $K_{5,9}$ plus a disjoint edge. I suspect that the answer to my question is also no.
Remark: A similar question where the smallest counterexample has $181^2$ “edges'': http://www.math.bas.bg/serdica/1995/1995-219-230.pdf
Update: I know this holds for $k\le 3$ even for general graphs.
Best Answer
Not an answer, but I like this question, so I decided to document a dark alley I went down which should be avoided (or more optimistically tweaked).
Begin Dark Alley.
Initially, I tried to get a counterexample out of purely number theoretic considerations. That is, let $2^{2k-1}-1$ be a Mersenne prime. Let $G$ be the graph consisting of the complete bipartite graph $K_{2^k+1, 2^k-1}$ together with an isolated edge $e$. Note that $G$ contains exactly $2^{2k}$ edges. Let $H$ be an induced subgraph of $G$ with exactly $2^{2k-1}$ edges. Note that if $e \in H$, then $K_{2^k+1, 2^k-1}$ contains an induced subgraph with exactly $2^{2k-1}-1$ edges. But this is impossible since $2^{2k-1}-1$ is prime. Unfortunately, $K_{2^k+1, 2^k-1}$ itself has an induced subgraph with $2^{2k-1}$ edges, by taking a subset of size $2^{k}$ from the left side and one of size $2^{k-1}$ from the right side. This is yet another instance of Douglas Zare's comment of don't try to make a counterexample which is a complete bipartite graph plus a few edges.
End Dark Alley.