小明买菜

STEM版,合并数学,物理,化学,科学,工程,机械。不包括生物、医学相关,和计算机相关内容。

版主: verdeliteTlexander

回复
头像
(ヅ)楼主
著名点评
著名点评
帖子: 4585
注册时间: 8月 21, 2022, 2:20 pm

小明买菜

帖子 (ヅ)楼主 »

小明家里有三个存钱罐

第一个里面全是$1面值硬币
第二个里面全是$2面值硬币
第三个里面全是$5面值硬币

鉴于小明是土豪,每个存钱罐里面的硬币数量为无穷多

妈妈今天想吃龙虾,小明在中国店称了一颗龙虾要$37,请问

1. 有多少种硬币组合办法可以刚好凑出$37
2. 任意价格$x的商品,怎么找出有多少种硬币组合办法(a,b,c) such that a*$1 + b*$2 + c*$5 = $x
图片
头像
(ヅ)楼主
著名点评
著名点评
帖子: 4585
注册时间: 8月 21, 2022, 2:20 pm

Re: 小明买菜

帖子 (ヅ)楼主 »

用a_n表示可以用某种硬币凑出$n总数的组合的数量。如果只用$1硬币,其对应的母函数为

1/(1-x) = 1 + x + x^2 + ... = a_0 * 1 + a_1 * x + a_2 * x^2 + ...

如果只用$2硬币,其对应的母函数为

1/(1-x^2) = 1 + x^2 + x^4 + ... = a_0 * 1 + a_1 * x^2 + a_2 * x^4 + ...


只用$5硬币同理

那么对于任意价格$x的商品,只需要检查\frac{1}{(1-x)(1-x^2)(1-x^5)}泰勒展开后对应x^n项的系数,其up to x^40的展开式为
92*x^39 + 88*x^38 + 84*x^37 + 80*x^36 + 76*x^35 + 72*x^34 + 68*x^33 + 65*x^32 + 61*x^31 + 58*x^30 + 54*x^29 + 51*x^28 + 48*x^27 + 45*x^26 + 42*x^25 + 39*x^24 + 36*x^23 + 34*x^22 + 31*x^21 + 29*x^20 + 26*x^19 + 24*x^18 + 22*x^17 + 20*x^16 + 18*x^15 + 16*x^14 + 14*x^13 + 13*x^12 + 11*x^11 + 10*x^10 + 8*x^9 + 7*x^8 + 6*x^7 + 5*x^6 + 4*x^5 + 3*x^4 + 2*x^3 + 2*x^2 + x + 1

所以付$37有84种办法
图片
回复

回到 “STEM”