10個の数の空でない部分集合は2^10-1=1023個。これらの和はすべて1以上、最大でも選んだ数の合計以下で、その合計はどんなに大きくても91+92+…+100=955以下。部分集合の個数1023が可能な和の種類数955を超えるので、鳩の巣原理より同じ和を持つ2つの部分集合が必ず存在する。 【ヒント】部分集合の個数と、和が取りうる値の範囲の広さを比較する。 【Aha】個々の数ではなく「部分集合の総数 vs 可能な和の数」という規模の比較に鳩の巣原理を使う。