ホーム >> 組合せ >> どの要素を取り除いても和がNとできる集合
hide or visible

問題の説明

組合せの問題です.$200$ 以上の自然数 $N$ と $1$ から連続する $N$ 個の自然数の集合 $X$ を考えます.以下の条件 $(*)$ を満たす最小の自然数 $N$ を求める問題です.
条件 $(*)$ : $X$ からどのように $100$ 個の要素を取り除いたとしても,残りの集合から上手に $100$ 個の要素を選んで和が $N$ となるようにできる.

この条件が少しわかりにくいです.より噛み砕いて言うと,『$X$ という集合からどんな $100$ 個の要素を取り除いたとしても,残りの $N-100$ 個の要素から上手に $100$ 個選んで,その和が $N$ になるようにできる.』ということです.

示すべきことは $2$ つあります.ひとつは,求めるべき $N$ よりも小さい値では,条件 $(*)$ に違反してしまうこと.もうひとつは,求めるべき $N$ が実際に条件 $(*)$ を満たしていることです.前半は簡単ですが,後半は少し発想が必要です.

解答例

$N=15050$ であることを示します.

まず,$N$ < $15050$ のとき,条件 $(*)$ が必ず満たされないことを示します.
$N$ < $15050$ のとき,$X$ から $1,2,...,100$ の $100$ 個の要素を取り除いたとすると,残りの集合から $100$ 個選んで和が最小になるようなものは,当然 $101,102,...,200$ です.このとき, $$101+102+\cdots +200=\frac{1}{2}\times 301 \times 100=15050 > N$$ です.したがって,$X\backslash \{1,2,...,100\}$ からどのように $100$ 個の要素を選んでもその和は $N$ より大きくなってしまうので,条件 $(*)$ は満たされません.

つぎに,$N=15050$ のとき,確かに条件 $(*)$ が満たされることを示します.
以下のような $150$ 組の $2$ つの数のペアを考えます. $$\binom{1}{300},\binom{2}{299},\binom{3}{298},...,\binom{150}{151}$$ どの組も,$2$ つの数の和は $301$ であり,さらにどの組に現れている数も相異なることに注意してください.
上の組は $150$ 組あるので,$X$ から,どのように $100$ 個の数を取り除いたとしても,少なくとも $50$ 組は取り除かれていません.その $50$ 組を選べば,その和は $$50\times 301=15050=N$$ となるので,条件 $(*)$ を満たします.