どの要素を取り除いても和がNとできる集合|思考力を鍛える数学

組合せの問題です.$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$$ となるので,条件 $(*)$ を満たします.

Copied title and URL