反射律は自明なので、対称律と推移律を証明します。

以下の事実を確認しておきます。

• 直線の列 \((L_1, L_2, \ldots, L_n)\) を考える。 Alice が \(X\) にいるときに、 \(L_1, \ldots, L_n\) を順に使ったときの移動先を \(X'\) とする。同様に、 Alice が \(Y\) にいるときに、 \(L_1, \ldots, L_n\) を順に使ったときの移動先を \(Y'\) とする。このとき、\(XY=X'Y'\) が成り立つ。

これは操作回数に関する数学的帰納法などで証明できます。この事実を用いて証明していきます。

まずは対称律を示します。 \(P\) から \(Q\) へ到達可能であるとします。任意の実数 \(\varepsilon > 0\) をとります。このとき、 \(P\) から \(Q\) への到達可能性から、ある直線の列 \((L_1, \ldots, L_n)\) が存在して、 Alice が \(P\) にいるときに \(L_1, \ldots, L_n\) を順に使った際の移動先を \(P'\)としたとき、 \(P'Q<\varepsilon\) となります。ここで、 Alice が \(P'\) にいるときに \(L_n, L_{n-1}, \ldots, L_1\) を順に使ったときの移動先が \(P\) であることと、 \(P'Q<\varepsilon\) であることから、 Alice が \(Q\) にいるときに \(L_n, L_{n-1}, \ldots, L_1\) を順に使ったときの移動先を \(Q'\) とすると、 \(P'Q=PQ'<\varepsilon\) となります。これにて、 \(Q\) から \(P\) へ到達可能であることが示されました。

続いて、推移律を示します。 \(P\) から \(Q\) 、 \(Q\) から \(R\) へそれぞれ到達可能であるとします。任意の実数 \(\varepsilon > 0\) をとります。 \(P\) から \(Q\) への到達可能性から、ある直線の列 \((L_1, \ldots, L_n)\) が存在して、 Alice が \(P\) にいるときに \(L_1, \ldots, L_n\) を順に使った際の移動先を \(P'\)としたとき、 \(P'Q<\frac{\varepsilon}{2}\) となります。 \(Q\) から \(R\) への到達可能性から、ある直線の列 \((K_1, \ldots, K_m)\) が存在して、 Alice が \(Q\) にいるときに \(K_1, \ldots, K_m\) を順に使った際の移動先を \(Q'\)としたとき、 \(Q'R<\frac{\varepsilon}{2}\) となります。ここで、 \(P'Q<\frac{\varepsilon}{2}\) であったので、 Alice が \(P'\) にいるときに \(K_1, \ldots, K_m\) を順に使った際の移動先を \(P''\)としたとき、 \(P''R \le P''Q'+Q'R = P'Q + Q'R<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon\) となります。 \(P''\) というのは、 Alice が \(P\) にいるときに \(L_1, \ldots, L_n, K_1, \ldots, K_m\) を順に使った際の移動先に等しいです。したがって、 \(P\) から \(R\) へ到達可能であることが示されました。

\(O\) を原点として考えてよいです。

\(1\) 本目の直線の偏角を \(\alpha\) 、 \(2\) 本目の直線の偏角を \(\beta\) とします。また、現在の Alice の位置を \(X\) で表すこととします。

まず、 \(2\) 本の直線をどのように使っても、 \(OX\) の値は変わりません。したがって、\(OS \ne OT\) の場合、すなわち \(S,T\) が \(O\) を中心とする同一円周上にない場合、 \(S\) から \(T\) へは到達不可能です。

以降、 \(O\) を中心とし、 \(S\) を通る円周上の移動について考えます。 \(X\) の偏角を \(x\) とし、移動による \(x\) の変化について考えます。 \(1\) 本目の直線での移動により \(x \mapsto 2\alpha -x\) 、 \(2\) 本目の直線での移動により \(x \mapsto 2\beta -x\) と変化します。したがって、 \(1\) 本目、 \(2\) 本目と順に使うことで、 \(x \mapsto x+2(\beta-\alpha)\) という変化が可能になります。同様に、\(2\) 本目、 \(1\) 本目と順に使うことで、 \(x \mapsto x-2(\beta-\alpha)\) という変化も可能になります。これを繰り返すことで、任意の整数 \(n\) について、偏角が \(x+2n (\beta-\alpha) (\bmod 2\pi)\) となる点に有限回で移動することができます。 \(\frac{\beta-\alpha}{\pi} \) が有理数でないとき、これらの有限回で移動可能な点たちは円周上を稠密に「埋め尽くす」ことができます。 (これはディオファントス近似などを使うことで証明できます。参考：Wikipedia )

\(\frac{\beta-\alpha}{\pi} \) が有理数にならないことを背理法で示します。 \(\frac{\beta-\alpha}{\pi} \) が有理数であると仮定します。この問題では、直線は \(2\) つの格子点を通る直線として与えられます。また、 \(O\) はよい交点であるので、\(\beta-\alpha=\pm\frac{\pi}{2}\) となることはありません。したがって \(\tan (\beta-\alpha)\) は有理数になります。 \(\tan (\beta-\alpha)\) が有理数であるときに、 \(\frac{\beta-\alpha}{\pi} \) が有理数となるのは、 \(\beta-\alpha=0, \pm\frac{\pi}{4}, \pm\frac{3\pi}{4}\) となるときに限られます(Niven の定理の系。参考：Wikipedia )。 しかし、これらはいずれも \(\frac{\pi}{4}\) の倍数であり、 \(O\) がよい交点であることに反します。したがって、 いい交点においては、 \(\frac{\beta-\alpha}{\pi} \) は有理数とはなりません。

以上より、 \(2\) 点\(S,T\) が \(O\) を中心とする同一円周上に存在するとき、 \(S\) から \(T\) は到達可能となります。

まず、任意の点 \(T\) が \(O_1\) から到達可能であることを示します。 \(d=O_1O_2\) とします。また、現在の Alice の位置を \(X\) と表すことにします。

はじめ、 \(O_1X=0\) です。ここから、 \(O_2\) を中心として円周上の移動を行うことで、 \(O_1X=2d\) とできます。ここから、 \(O_1\) を中心として円周上の移動を行い、 \(X\) を \(O_1\) に関して \(O_2\) と反対側の位置に移動させます。ここからさらに \(O_2\) を中心として移動を行うことで、\(O_1X=4d\) とできます。 これを繰り返すことで、 \(O_1X\) をいくらでも大きくすることができます。ここまでの距離の変化は連続的に行うことができるため、 \(O_1X\) の値は任意に設定できます。このことを用いて、 \(O_1X=O_1T\) とした後、 \(O_1\) を中心として円周上の移動を行うことで、 \(T\) に移動することができます。よって、 \(O_1\) から \(T\) は到達可能です。

任意の \(2\) 点 \(S,T\) に関して、 \(O_1\) から \(S\) 、 \(O_1\) から \(T\) に到達可能であるので、 \(S\) から \(T\) も到達可能です。

上記の方法で移動可能と判定された場合、明らかに移動可能です。逆を示します。

\(S\) から \(T\) へ移動するための操作の列があるとします。この中で、向き \(0\) の直線による操作、向き \(1\) の直線による操作を順に行う箇所があるとします (このようなものを \(0,1\) の操作と呼ぶことにします)。この操作において、 \(2\) 本の直線の交点を \(O\) とすると、 \(O\) を通る向き \(2\) の直線が存在します。この直線を用いると、 \(0,1\) の操作を \(1,2\) の操作に変換することができます。同様に、 \(2,1\) は \(1,0\)、 \(0,3\) は \(3,2\)、 \(2,3\) は \(3,0\) というような変換を行うことができます。この操作を繰り返すことで、 向きが \(1,3\) の直線による操作をすべて操作列の最初に持ってくることができます。向き \(1\) の直線の操作と、向き \(3\) の直線の操作は独立であり、それぞれの向きに直線は高々 \(1\) 本しか存在しないため、 \(2\) 回以上の操作をする必要はありません。したがって、向き \(1,3\) の直線で高々 \(1\) 回操作をし、残りは向き \(0,2\) の直線で操作をするという操作列が存在することが示せました。これにより、 \(S\) から \(T\) へ移動可能な場合、上記の方法で移動可能と判定されます。