問題

整数 $N$ が与えられます。 $\{1,2,...N\}$ の部分集合の組 $(S_1,S_2,...,S_k)$ であって、以下の条件を満たすものが存在するか判定し、存在する場合はひとつ構成してください。

考え方

求めることは、部分集合の組である。部分集合の組の数を $k$ とする。例として $k=4$ となる場合を考えよう。

$2$ つ目の条件を求めるべき $k$ つの部分集合に適応すると、 $2$ つの部分集合の組と共通の要素の関係は以下のようになる。

このとき、集合 $S_1$ は $S_1 = \{ A, B, C \}$ の要素を持つことになる。同様にして部分集合 $S_2, S_3, S_4$ に持つべき要素も一意に定まる。

上記の議論により、解をもつ場合の必要条件は $2 \times N = k \times (k-1)$ が成り立つことである。 $N$ について、必要条件が成り立つことを確認し、満たす場合は Yes で上記で示した方法で部分集合を構成する。満たさない場合は No となる。