MathLabs

第4問

少なくとも2個の要素を持ち、各要素がほかの要素の少なくとも一つと共通の素因数を持つとき、その正の整数の集合を 芳香的 であるという。P(n)=n2+n+1P(n)=n^2+n+1 とする。集合 {P(a+1),P(a+2),…,P(a+b)}\{P(a+1),P(a+2),\dots,P(a+b)\} が芳香的となるような非負整数 aa が存在するような正の整数 bb の最小値を求めよ。
ステップ 3/5: すべての頂点を覆うには辺が少なすぎる
前のステップ次のステップ
ざっくり言うと

3本の辺は高々6個の頂点スロットにしか触れられず、辺が間隔 2,3,42,3,4 のみに制限されている場合、五角形状の間隔グラフの5個の頂点すべてを覆うことは不可能であることが分かる。

at most 3 edges among 5 vertices ⇒ some vertex has degree 0\text{at most }3\text{ edges among }5\text{ vertices}\ \Rightarrow\ \text{some vertex has degree }0
詳しい解説

55 個の頂点 a+1,…,a+5a+1,\dots,a+5 の間で合計高々 33 本の辺（間隔 22、33、44 それぞれ1本ずつ）しかなく、間隔 11 の辺は許されないので、これらの間隔がどの頂点対を結びうるかを直接確認すると、55 個の頂点すべてが同時に次数 ≥1\ge1 を持つことは不可能であり、常にどこかの頂点が孤立してしまうことが分かる。これは芳香的の条件（すべての要素に相手が必要）と矛盾するので、b≤5b\le5 は不可能である。