(より詳しい解説は後日ブログで公開します)

\(b_1 < \ldots < b_N\) で \(N\) 角形ができる条件は \(b_1 + \cdots + b_{N-1} > b_N\) です．

すべてのケースについて YES か NO の証拠を見つければ解けたことになるので，それを目指します．

YES

適当に探索すると見つかります．

とはいえ純粋な全探索や範囲内一様ランダムだと難しいかもしれません．例えば，定数の \([0, 1]\) 一様ランダム乗などで値を作ってソートした後に，\(N\) 角形になってほしいところをぎりぎりに調整する (例えば \(b_N = b_1 + \cdots + b_{N-1} - 1\) に設定する) とよいです．

NO

実は \(k \le 2\) で見つかります．

\(k = 2\) を例として説明すると，\(Q_1, Q_2\) を全探索して，判定するには \(b_1 + \cdots + b_{N-1} > b_N\) の形の条件 \(A, B, C, D, E, F\) について \(A \land B \implies (C \land D) \lor(E \land F)\) に対する反例の有無がわかればよいですが，これは \(A \land B \land \overline{C} \land \overline{E}\) のような式に対する反例を探すことを \(2^2\) 回行えばよく，LP になります (\(f < g\) を \(f + 1 \le g\) にして有理数解を探しても同値なので)．