\(N < 6\) の時は探索すればよいです。以下 \(6 \le N\) とします。

まず \(2\) 項の場合を考えましょう。 \(\dfrac{a}{b}<\dfrac{c}{d}\) を満たす \((a,b,c,d)\ (1 \le a,b,c,d \le N)\) について、 \(\dfrac{c}{d}-\dfrac{a}{b} = \dfrac{bc-ad}{bd}\) ですから、 \(\dfrac{1}{N(N-1)} \le \dfrac{c}{d}-\dfrac{a}{b}\) です。逆に、 \((a,b,c,d)=(1,N,1,N-1)\) とすれば \(\dfrac{c}{d}-\dfrac{a}{b} = \dfrac{1}{N(N-1)}\) が達成できます。

同じように考えると、 \((a,b,c,d,e,f)=(1,N,1,N-1,1,N-2)\) が思い浮かびます。実は、このときの \(\dfrac{e}{f}-\dfrac{a}{b}=\dfrac{2}{N(N-2)}\) が条件を満たす中で最小であることが示せます。

実際に示しましょう。まず、最小値は \(\dfrac{be-af}{bf}\) と表せます。ここで、 \(be-af\) の値を決め打つことを考えましょう。

\(be-af=1\) のとき

分母を適当に通分すると、 \(\dfrac{a}{b}<\dfrac{c}{d} < \dfrac{e}{f}\) は \(\dfrac{adf}{bdf}<\dfrac{bcf}{bdf} < \dfrac{bde}{bdf}\) と言い換えられます。つまり、 \(adf<bcf<bde\) です。 また、 \(1 \le bcf-adf<bde-adf\) より \(1 \le (bc-ad)f<d\) です。 \(bc-ad\) の値で場合分けします。

\(bc-ad=1\) のとき

\(be-af=1\) と \(bc-ad=1\) という式が似通っていることに着目すると、適当な正整数 \(k\) をとって \(\dfrac{c}{d}=\dfrac{ka+e}{kb+f}\) と表せることがわかります。 \(p,q \le n\) を満たす正の実数の組 \(p,q\) についての \(pq\) の最大値が \(\dfrac{n^2}{4}\) であることから \(\dfrac{be-af}{bf}=\dfrac{1}{bf}\) について \(\dfrac{4}{N^2}\) 以上であることが言え、この値は \(6 \le N\) において \(\dfrac{2}{N(N-2)}\) 以上であることが帰納法などを用いると示せます。

\(2 \le bc-ad\) のとき

先ほどの式より、 \(f < \dfrac{d}{2}\) です。よって、解は \(\dfrac{1}{N^2}+\dfrac{2}{N^2}\) 以上、つまり \(\dfrac{3}{N^2}\) 以上であることが言えます。先ほどと同様に、この値は \(6 \le N\) において \(\dfrac{2}{N(N-2)}\) 以上です。

\(be-af=2\) のとき

\(\dfrac{e}{f}-\dfrac{c}{d}=\dfrac{c}{d}-\dfrac{a}{b}=\dfrac{1}{N(N-1)}\) とすることができないことを示します。 \(\dfrac{p}{q}-\dfrac{r}{s}=\dfrac{1}{N(N-1)}\) のとき、 \(q,s\) は片方が \(N\) 、片方が \(N-1\) です。よって、 \(b=f=N\) または \(b=f=N-1\) となりますが、 \(6 \le N\) において \(\dfrac{2}{N(N-1)}=\dfrac{1}{N}\) または \(\dfrac{2}{N(N-1)}=\dfrac{1}{N-1}\) とすることは不可能です。

\(3 \le be-af\) のとき

\(6 \le N\) において \(\dfrac{2}{N(N-2)} \le \dfrac{3}{N(N-1)}\) ですから、最小値にはなりえません。

以上より、この問題を時間計算量 \(O(1)\) で解くことができました。 \(N<6\) の場合に気を付けてください。(実際には、 \(N=4,5\) においては先ほどの構築方法が最小値の一つとなります)

実装例 (C++)