公式解説 [3] の部分についての Tester 解です

公式解説での良い整数の定義は、以下の通りでした。

• \(n\) を \(3\) 進数で表記したとき、全ての桁が \(0\) または \(1\) である。

良い非負整数のうち、 \(9999\) 番目のものは \(1679655\) です。ここで、以下が成立します。

良い非負整数のうち \(9999\) 番目までのものを \(N-1\) 個含んだ良い集合 \(S\) に、 \(4000000=4 \times 10^6\) 以上の任意の整数 \(\alpha\) をひとつ追加した集合 \(S'\) も良い集合である。

証明: \(S' \ni x, y, z\) (\(x<y<z\)) がこの順に等差数列をなすとき、 \(z=\alpha\) となります。このとき \(y \in S\) なので \(y < 2 \times 10^6\) であるため \(x<0\) であるべきということになり、 \(S'\) の構成法上負の整数は含まれないため矛盾します。

この \(\alpha\) を \([4 \times 10^6,4 \times 10^6+N)\) の中から適切に選ぶことにより、「 \(M \mod N\) 」と「 ( \(S'\) の総和 ) \(\mod N\) 」とを一致させることができます。

最後に \(S'\) 内の全ての要素に特定の値を足すことにより、 \(S'\) の総和を \(N\) 単位で調整することができ、目的の集合を得られます。