問 $N$ を $200$ 以上の自然数,$X=\{1,2,...,N\}$ とする.次の条件 $(*)$ を満たす最小の $N$ を求めよ.
条件 $(*)$ : $X$ からどの $100$ 個の要素を取り除いても,残りの集合から $100$ 個の要素を選んで和が $N$ となるようにできる.
2019/6/10
組合せ
★★★☆☆
組合せの問題です.$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$$
となるので,条件 $(*)$ を満たします.