= Solution
A <decision tree> queries individual input bits, chooses subsequent queries from previous answers and labels each leaf with an output. Its <decision-tree depth> is the largest number of queries on any root-to-leaf path; $D(f)$ is the least such depth over trees computing $f$. An <evasive Boolean function> on $n$ bits has $D(f)=n$.
Remove repeated queries along any path, since their answers are already known. A leaf at depth $r\leq d<n$ fixes $r$ bits and leaves at least one bit free. The inputs reaching it form a subcube on which $f$ is constant, say $b$. Its contribution to the alternating sum is
$$
b(-1)^{\sum\text{fixed bits}}\prod_{\text{free bits}}(1-1)=0.
$$
Here $\operatorname{wt}(x)$ is the <Hamming weight>. The leaf subcubes partition the input cube, so adding their contributions proves
$$
\boxed{D(f)<n\Longrightarrow\sum_{x\in\{0,1\}^n}(-1)^{\operatorname{wt}(x)}f(x)=0}.
$$
The contrapositive is the <alternating-sum criterion for decision-tree evasiveness>: a nonzero alternating sum forces all $n$ bits to be necessary in the worst case.
Back to article page
