MathLabs

第3問

S={1,2,3,…,280}S=\{1,2,3,\ldots,280\} とする。Sの各n要素部分集合が、任意の2つが互いに素な5個の数を含むような最小の整数nを求めよ。
ステップ 5/5: 1つのブロックに5個を強制する
∣T∣=217 ⟹ ∣T∩(P∪A1∪A2∪A3∪B1∪B2)∣≥25>6⋅4|T|=217\ \Longrightarrow\ |T\cap(P\cup A_1\cup A_2\cup A_3\cup B_1\cup B_2)|\ge25>6\cdot4
詳しい解説

選んだ88個の補集合は192個である。従って217要素集合Tはその合併と少なくとも25個で交わる。6ブロックの各々がTを高々4個含むなら交わりは24個以下。よってあるブロックが互いに素な5個を含む。障害集合と合わせ、最小値はn=217。