嘘がない場合と同様に、二分探索で範囲を狭めていけそう。まず、上図の[A]のように全体の1/2の位置にある数を尋ねてGと返ってきた状況を考える。（赤線とその隣にあるアルファベットが、質問した位置と答えを表す。LIEは「真の数を含んでいるとすると答えが嘘である」区間を表す。）その次に全体の1/4の位置にある数を尋ねると、二回連続で嘘をつけないという条件により、3段目で×をつけた区間は除外できる。同様に、1回目でLが返ってきた場合は3/4の位置にある数を尋ねると同等の結果が得られる。2回の質問で可能な空間のサイズが3/4になっているので、これを繰り返せば部分点が取れる。
満点の条件では120回の質問で突き止める必要があるが、上の方針では最終的な候補数が$10^9 \times (3/4)^{60} \simeq 32$程度にしかならない。そこで、上図の[B]のようにG→Lという答えが返ってきた場合に、追加で3/4の位置にある数を尋ねるとサイズが1/2になることに注目する。この比率が毎回達成できれば間に合う計算だが、G→Gの場合にうまい追加質問がない。つまり、この区間割ではできればG→L, L→Gと答えてほしくてG→G、L→Lは望ましくないということになるが、それは割り方が最適でないということを意味する。
そこで、区間の割り方を調整して、G→LでもG→Gでも同じレートで空間が縮むようにしたい。2回目の質問で1/4の代わりに位置$x \in [0 ,1]$で区切るとする。このとき、G→Lでは3回の質問で空間が$x+1/4$倍になり、G→Gでは2回の質問で$1-x$倍になる。1回あたりの改善率が同じになる条件は$(x+1/4)^2 = (1-x)^3$なので、$x \simeq 0.31586$と求まる。計算してみると、120回の質問で足りることがわかる。
想定解の改善率は2回あたり33%だった。2回の質問を1セットとして、G→Lの場合には次のセットで前の結果を利用できるらしい。
