Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 51 / 1 / e / Solution

A classical query with known answer bit $z$ reveals exactly the one bit $f(x,y)$, since it returns $z\oplus f(x,y)$. For the four promised Boolean functions, the value table isEvery possible first query splits the four alternatives into one class of size one and another of size three. On the branch with three remaining alternatives, a second binary answer can separate at most two classes. At least two alternatives therefore still agree on that branch, regardless of how the second query was chosen adaptively. This decision tree argument proves that a procedure guaranteed to identify every alternative needs at least three queries in the worst case.

For sufficiency, query $00,01,10$. The three-bit answer strings for $1,y,x,x\oplus y$ are respectively $111,010,001,011$, which are all distinct. Hence the exact classical worst-case query requirement is three. Some individual branches can terminate sooner; the lower bound does not assert that every oracle requires three queries.