PDF《科别：数学科》

(二) p,q 为互质正整数,以p元及 q 元两种货币支付 n 元的方法数之探讨: 问题 1. p,q 为两互质正整数(且q>p) ,以p元、q 元等面额的钱币来支付 n 元物品,有几 种支付方法? (1) 从p=3,q=5 时的特例开始: 发现将正整数适度的分类(以除以

3 之后的余数来分类),发现

3 之倍数这一类的数一定 可以用

3 的倍数的面额来支付,而被

3 除余

1 这类的数,在(含)10 元之后,是没有问题的, 可以用两张

5 元的钱币来支付,而10 元以前的三个数字 1,4,7 就有困难了,因为它既无法用

3 元的面额来支付,也无法用

5 元的面额来支付;

同理,被3除余

2 这类的数,在(含)5 元之 后,是没有问题的,可以用一张

5 元的钱币来支付,而5元以前的数字

2 就有困难了.因此

2 发现,

1、

2、

4、7 这四种钱数,不能以

3 元及

5 元的钱币来支付,因此方法数皆为

0 种. n=3k+1

1 4

7 10

13 n=3k+2

2 5

8 11

14 n=3k

3 6

9 12

15 我们从观察中发现:15 是3和5的最小公倍数,在本题中扮演关键角色.每隔

15 个数, 方法数便会出现较大的周期变化,而前

14 个数字(如果包括 0,就是

15 个数字),大约可以分 成两个类(集合),一个称之为是可行的集合 P,表示可以用

3 元及

5 元来凑成的集合;

P={aO? m', n'∈N∪{0},使得 3m'+5n'=a,a