组合问题的实际应用

小学教育网

　　一名邮票设计家打算设计一种6张相连的邮票。他的设计理念是希望能以6张中的任一张或相连的几张组合出1元、2元、3元……N元的各种金额，N越大越好，每张邮票的面额并没有限制。图1所示为其设计出的一组邮票。
            该名设计者非常高兴，因为他以为这组邮票可以单一的一张或相连的数张邮票组合成1到32元的所有金额。可是经仔细核对后，发现其中有一种金额无法组合出来(注意：邮票的边缘必须相连)，真是遗憾。
       
        　　显示邮票组合出21元、23元及29元的例子。请自己找出1到32元的所有组合，并指出无法组合出哪一种金额。
       
        　　后来这位设计家又设计出另一组面额不同的邮票，可以在上述规则下组合出1到36元的各种金额。试着自己设计出一组邮票，看你能组合出的最大金额是多少？
       
        　　解答与分析
       
        　　不可能组合出的金额是18元，虽然7元、2元及9元邮票可合成18元，但是它们并没有相连在一起，故不符合题目的要求。我们先想出从6张邮票中取出一张或相连的几张邮票可有多少种方法，再来思考N的最大值。
       
        　　一共有40种取出邮票的方法，所以N的上限是40，但因题目的限制使得本题中N的最大值为36。共有下列两种方法可达成此目的，请你看看这两组邮票是否的确可组合出1元到36元的所有金额。