若有8分和15分的邮票可以无限次取用,那么只用8分和15分邮票不能凑成的最大邮资是多少?必须要推理过程.

Question

若有8分和15分的邮票可以无限次取用,那么只用8分和15分邮票不能凑成的最大邮资是多少?
必须要推理过程.

Answer 1

1.设最大不能凑成的游资为x,
则x+1,x+2,x+3,...,x+8应都能凑出,（x+9以后不必考虑,因为若x+1,x+2,x+3,...,x+8都能凑出,只需增加一枚8分邮票就可以凑出x+9,...x+16,之后也是如此）,
实际上寻找不能凑成的游资x的过程,应为寻找最小x+1的过程,这是因为x+1以后的游资都能凑出,若x+1不是满足上述条件的最小数字,x必然能够凑出,与x不能凑成矛盾
设凑出x+1需要m枚8分邮票和k枚15分邮票,有
8m+15k = x+1
若需凑出x+2,可以增加2枚8分邮票,减少1枚15分邮票,即
8(m+2)+15(k-1)=x+2
凑出x+3,可以在增加2枚8分邮票,减少1枚15分邮票
8(m+4)+15(k-2)=x+3
同理
8(m+6)+15(k-3)=x+4
8(m+8)+15(k-4)=x+5
8(m+10)+15(k-5)=x+6或8(m-5)+15(k+3)=x+7
8(m+12)+15(k-6)=x+7或8(m-3)+15(k+2)=x+7
8(m+14)+15(k-7)=x+8或8(m-1)+15(k+1)=x+8
上面各式中,8,15乘数应大于0,因此可知k>=7,m>=0或k>=6,m>=1或k>=5,m>=3或k>=4,m>=5
由x+1=8m+15k知,最小的x+1应在k=6,m=1时取得,此时x+1=98
故最大不能凑成的游资为97