PDF《科别：数学科》

科别:数学科 组别:高中组 作品名称:支付『国民便当』方法数的探讨 关键词:高斯函数、递回关系、非负整数解 编号:040402 学校名称: 台北县私立光仁高级中学 作者姓名: 刘韦廷、张哲豪、张菀心、蔡瑶 指导老师: 翁立卫、林丽卿 摘要 本文主要探讨的问题是「以多种不同钱币来支付 n 元的方法数」 .

研究方式多半先以观察 与考察特例为主,再思考、证明并推广至一般的情况.主要所涉及的数学概念与技巧是数列 递回的概念与消去法,在化简的过程中亦常会遭预到高斯函数与相关性质. 壹、研究动机 在某天中午我们一群朋友去 7-11 买便当,那时大家口袋里刚好都有很多硬币,於是决定 凑钱买几个『国民便当』 ,以解决午餐问题.为了支付每个

39 元的便当,大家凑的钱数和方 法都有所不同,这令我们觉得很好奇,到底有多少种方法可以凑成

39 元呢? 这是一个蛮生活化的问题,如果使用钱币的种类更多,那支付的方法铁定更多.因此我 们大胆的推论: 『使用 m 种不同的钱币支付 n 元时,会不会有通式,能轻易算出付款的方法 数?』感觉上这似乎是一个庞大的工程.於是我们找了些志同道合的朋友,一段神秘的发现 之旅就此展开. 贰、研究目的 为了求出以 m 种不同钱币支付 n 元的方法数,我们先分几种可能性做探讨.

一、当m=2 时,表用

2 种不同货币,支付 n 元的方法数,如:

(一) 以1元及 p 元付款,p∈N 且p,k>1

(二) 以p元及 q 元付款,p,q∈N 且(p , q)=1

(三) 以p元及 q 元付款,p,q∈N 且(p , q)=d , d≠

1

二、m=3 时,以3种不同货币,支付 n 元的方法数,如:

(一) 以1元、p 元及 kp 元付款,p,k∈N 且p,k>1

(二) 以1元、p 元及 q 元付款,p,q∈N , p,k>1 且(p , q)=1 参、研究方法

一、预备知识

(一) 排列组合的基本概念

(二) 数列的递回定义与对消法

(三) 高斯符号及相关性质

(四) a,b,c∈Z , ax+by=c 有整数解的充要条件为(a,b)?c.

二、前提:

(一) 本文中提及之付款方式,与付款之先后顺序无关.例如:"先付一个

3 元再付两个

5 元"与"先付两个

5 元再付一个

3 元",视为同一种付款方式.

1

(二) 为了配合理论的完整性及作为递回定义的起始条件,约定

0 元的付款方式为

1 种, 即支付

0 元的方法数 .

0 1 a =

(三) 所供应之钱币个数是没有限制的.

三、方法:本文的研究方式多半先以观察与考察特例为主,再思考、证明并推广至一般的 情况. 肆、研究过程

一、m=2 (有2种不同货币时)

(一) 以1元及 p 元(p∈N 且p>1)两种货币支付 n 元的方法数之探讨: 我们先以特例来思考,试试看以

1 元及

3 元来支付 n 元的方法数有何规律性,进而推广 至更具一般性的付款方式(1 元及 p 元).我们将部份结果摘录於下表: n 元012345678910

11 12

13 14

15 方法数

1 2

3 4

5 6 发现与启示:观察上表,得知支付 n 元的方法数 an 为每隔

3 元跳一次,所以我们可以以高斯 符号,将其规律性的变化表示出来, n a [ ]

3 n

1 = + . 因此推论:利用

1 元及 p 元来支付 n 元的方法数 n a [ ] n p

1 = + . 【证明】设使用

1 元x个、p 元y个来支付 n 元(x,y 为非负整数),则x,y 要满足:x+py=n 显然 x=n-kp (y=k)满足上式方程式,因此 n-kp≥0 ? n≥kp ? p n ≥k ? p n ≥[ p n ]≥k≥0 ?k 有[ p n ]+1 个可能,因此有[ p n ]+1 组解,即na[]np=+1.