It can be shown that after each question the sum of the weights of the two possible arising states is equal to the weight of the state preceding the question. Therefore the Responder can always achieve that after each query the weight decreases by no more than its half. Clearly, when the Questioner finds the unknown element, the weight is 1, since he needs zero query then. From these follows the lower bound of [weightbound]Lemma REF . The upper bound is due to Rivest et al. [1]}, for proofs see [2]}, [1]}.
