これは、ＳＵＢＳＥＴ−ＳＵＭという 問題に対する動的計画法という アルゴリズムの基本的な考え方を応用したもので、 これを知っていればすぐに答がわかります。
ＳＵＢＳＥＴ−ＳＵＭとは、 いくつかの数字から成る集合があるときに、それらの数字の和 (重複の使用は許さない)で、ある１つの数字を作ることができるか、 できないか判定する問題です。 例えば、｛３、５、６、９｝ という集合があるとき、１７という数はそれらの和で作れるか というと、答えはＹＥＳです。
さて、この問題に対する動的計画法は、
まず、３で作ることのできる数の集合をＡ１
とすれば、
Ａ１＝｛３}
つぎに、３と５で作ることができる数の集合をＡ２
とすれば、Ａ２は、３で作ることのできるＡ１と、５自身と、５にＡ１の
各数を足し合わせた数になるので、
Ａ２＝｛３、５、８｝
同様に、３と５と６でできる数の集合をＡ３とすれば、
３と５の組合せで作れる数字の集合であるＡ２と、６自身と、６にＡ２の各数を
足してできる数字からできています。したがって、
Ａ３＝｛３、５、６、８、９、１１、１４｝
そして最後に｛３、５、６、９｝の集合から作れる
数字の組Ａは、
Ａ＝｛３、５、６、８、９、１１、１２、１４、１５、１７、１８、２０、２３｝
となっている。１７も確かにこの中に含まれています。
この考え方を利用すれば、クイズの答えは、 ｛１、２、４｝で作れる数字の組は、｛１、２、３、４、５、６、７｝なので、 ８があれば１〜１５までの数字がすべて作ることができます。 さらに、１６はできなくても構わないので、１７があれば１６を除いた １〜３２までの数字が全て作ることができるのがわかるでしょう。