どの2数も「よい組」を作らないように最大何個選べるか，最大クリーク問題 / 2020 トルコジュニア第2問

問題概略
最大クリーク問題に帰着させる
証明する

問題概略

$\dfrac{17m+43n}{m-n}$ が整数になるような正の整数の組 $(m,\, n)$ を「よい組」とよぶことにする。

1, 2, $\cdots$ , 2021 からどの 2 数もよい組を作らないように数を選んでいくとき，最大で何個の数を選べるだろうか？
https://artofproblemsolving.com/community/c6h2476057p20756209

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

最大クリーク問題に帰着させる

この分数が整数になるのは分子が分母で割り切れるとき，つまり「分母と分子の最大公約数が分母のとき」です。
$a$ , $b$ の最大公約数を $(a,\, b)$ であらわして計算します。

\begin{align*}
(17m+43n,\, m-n) &=\left(17m+43n-17(m-n),\, m-n\right)\\
&=(60n,\, m-n)\mbox{　……(1)}\\
&=\left(60n+60(m-n),\, m-n\right)\\
&=(60m,\, m-n)\mbox{　……(2)}
\end{align*}

(1)より $(m,\, n)$ がよい組になる条件は $60n$ が $n-m$ で割りきれることです。

(1)(2)より $(m,\, n)$ がよい組なら $(n,\, m)$ もよい組なので，以下 $m< n$ とします。

「よい組」をグラフの言葉で言い換えましょう。 $(m,\, n)$ がよい組でないとき点 $m$ と点 $n$ の間に辺をはります。

どの 2 数もよい組を作らないように選んだ数の集合はクリーク（フルメッシュな部分グラフ）を構成します。最も大きいクリークの頂点数が答えです。mathematica で計算しました。

    In[]:= AbsoluteTiming[
        d = 2021;
        f[{m_, n_}] := If[! Divisible[60 n, n - m], m <-> n, Nothing];
        eLst = f /@ Flatten[Table[{i, j}, {i, 1, d - 7}, {j, i + 7, d}], 1];
        ans = Length /@ FindClique@Graph@eLst]
       
    Out[]= {48.8364, {289}}

4 行目の eLst は辺の集合です。
$n-m$ が 1, 2, 3, 4, 5, 6 のとき $n-m\, |\, 60\,|\, 60n$ から $(m,\, n)$ はよい組になるので，
差が 7 以上ある $(m,\, n)$ の集合から $n-m$ が $60n$ を割りきらないものを抽出して辺をはっています。

5 行目は辺の集合をグラフにして最大クリークの 1 つを求め，その頂点数を表示させています。
答えは 289 個でした。ちなみにここで求めた最大クリークの中身は初項 1，公差 7 の等差数列でした。

証明する

「プログラムを組んで実際に求めました」では解答にならないので，ちゃんと証明します。

どの 2 数もよい組を作らないように選んだ数を小さい順に $a_1$ , $a_2$ , $\cdots$ , $a_{N}$ とおいて，
その階差の最小値を $d=\min\left\{a_2-a_1,\, a_3-a_2,\, \cdots,\, a_{N}-a_{N-1}\right\}$ とおきます。
これは上の説明で言えば $n-m$ の最小値のことなので $d\geqq 7$ です。