= Solution
Use the following <decision-tree adversary for a threshold function>. Regardless of which variables the tree queries, answer $0$ on the first $n-r$ queries and $1$ on the next $r-1$ queries. After any proper prefix of this answer sequence, the unqueried variables can be completed both to an input of weight below $r$ and to one of weight at least $r$. Immediately before the last query the answers contain exactly $n-r$ zeros and $r-1$ ones, so the final bit alone determines the value of the <threshold Boolean function> $f_{n,r}$. Thus every decision tree has a root-to-leaf path of length $n$, while querying all variables gives depth $n$. Hence
$$
D(f_{n,r})=n.
$$
Back to article page
