任意の相異なる数 \(X, Y, Z\) を考え、質問 \((X, Y), (X, Z), (Y, Z)\) の場所に注目します（\(Y<X\) なら、\((X, Y)\) は \((Y, X)\) のことです）。一般性を失うことなく、この中で \((X, Z)\) が最も後ろにあるとします。そのとき、もし \(P_X<P_Y\) かつ \(P_Y<P_Z\) であれば、すでに \(P_X<P_Z\) と推定できます。同様に、もし \(P_X>P_Y\) かつ \(P_Y>P_Z\) であれば、すでに \(P_X>P_Z\) と推定できます。よって、ペア \((X, Z)\) が最後に現れるような任意の三つ組 \(X, Y, Z\) について、\(P_Y\) は \(P_X\) と \(P_Z\) の間にはありません。

観察 1: もし上記の要求がすべて満たされれば、\(\frac{N(N-1)}{2}\) 個の質問がすべてされる。

証明: ある \((U, V)\) について、質問 \((U, V)\) をする前に \(P_U<P_V\) とわかったと仮定します。そのためには、列 \((X_1, X_2, \ldots, X_t)\) であって、\(X_1 = U, X_t = V\) であり、ここで隣接する要素のペアすべてについてすでに質問済みであり、すべての \(1 \le i \le t-1\) について \(P_{X_i}<P_{X_{i+1}}\) と知ったという列が存在する必要があります。そのような列のうち、最短のものを考えます。明らかに、\(t \ge 3\) です。ここで、ペア \((X_1, X_3)\) についての質問を考えます。もしこの質問がすでにされていれば、より短い列が存在したはずです。従ってこの質問はされておらず、\(X_1, X_2, X_3\) について、ペア \((X_1, X_3)\) が \((X_1, X_2)\) や \((X_2, X_3)\) より後にあることになり、よって \(P_{X_2}\) が \(P_{X_1}\) と \(P_{X_3}\) の間にあるということはありえません。

ここで、\(N\) 頂点の完全グラフを考えます。\(X < Y\) であるような各辺 \((X, Y)\) を、\(P_X<P_Y\) なら白で、\(P_X>P_Y\) なら黒で塗ります。このとき、各順列に対応する色分けが存在し（逆もまた然りとはいいませんが）、異なる順列に対しては異なる色分けが対応することに注意します。

すると、すべての三つ組 \(X, Y, Z\) について、\(X, Y\) の間の辺と \(Y, Z\) の間の辺の色が同じか否かがわかります。これらの条件をすべて、DSU などで記録しましょう。

観察 2: 矛盾が生じた場合（すなわち、ある二本の辺について、それらが同じ色であると同時に異なる色でなければならないという場合）、答えは \(0\) である。

観察 3: 矛盾がない場合、辺に関するグラフ（二つの辺は、それらの色について条件があるときに結ばれる）の連結成分の個数を \(k\) とすると、答えは \(2^k\) である。

証明: 上記の要求がすべて満たされるなら、質問がすべてされることはすでに示しました。あとは、あらゆる色分けが何らかの順列に対応することを示すのみです。そのためには、色分けに対応する有向グラフにサイクルがないことを示せば十分です。完全有向グラフにおいて、「サイクルが存在する」\(\iff\)「長さ \(3\) の有向サイクルが存在する」であることを思い出しましょう。有向サイクル \((P_X \to P_Y, P_Y \to P_Z, P_Z \to P_X)\) が生じたと仮定して、一般性を失うことなく、ペア \((X, Z)\) が \((X, Y), (Y, Z), (X, Z)\) の中で最後に現れるとします。すると、色分けによれば、\(P_X \to P_Y, P_Y \to P_Z\) という（\(P_Y\) が \(P_X\) と \(P_Z\) の間にある）遷移は不可能であることになります。