第4問

少なくとも2個の要素を持ち、各要素がほかの要素の少なくとも一つと共通の素因数を持つとき、その正の整数の集合を 芳香的 であるという。

P(n)=n^2+n+1

とする。集合

\{P(a+1),P(a+2),\dots,P(a+b)\}

が芳香的となるような非負整数

a

が存在するような正の整数

b

の最小値を求めよ。

ステップ 2/5: 可能な辺が少なすぎるグラフ

前のステップ次のステップ

ざっくり言うと

$b$ 個の連続した値の間で共有されうる因子をグラフとしてモデル化する。前のステップにより、可能な「間隔」の辺は特定の3種類のみで、それぞれ高々1本しかありえない。

b\le5\ \Rightarrow\ \text{at most one edge of gap }2,\,3,\,4,\text{ and none of gap }1

詳しい解説

間隔 $2$ では $7$ による整除のため、2つの添字は $2,4\pmod7$ という2つの根でなければならず、5個の連続添字には高々1組しかない。間隔 $3$ では $3$ による整除のため両添字が $1\pmod3$ であり、やはり高々1組。間隔 $4$ では $19$ の根が $7,11\pmod{19}$ であり、これも高々1組である。間隔 $1$ は最大公約数が1なので不可能。したがって5個の連続添字の間には高々3本の共通因子辺しかなく、5頂点すべてを覆うことはできない。 $1$