若有8分和15分的邮票可以无限制的取用,但某些邮资如7分,29分等不能刚好凑成,哪么8分和15分的邮票不能凑成的最大邮资是多少?

Question

若有8分和15分的邮票可以无限制的取用,但某些邮资如7分,29分等不能刚好凑成,哪么8分和15分的邮票不能凑成的最大邮资是多少?

Answer 1

首先,此题是有解的,证明如下：
1、设要凑成某值的邮票A,凑成方法为：A=15x+8y,则x、y应该都为非负整数.
2、可以得到：y=（A-15x）/8=(A+x)/8-2x.
3、由于2x为整数,所以只要(A+x)为8的整数倍,而且大于2x,就可以凑得出了.
4、如果A>8,那么都可以找到一个数x,0《x《7,使（A+x）/8为整数,如果要找到一个最大的数A,使y不能成为非负整数,则有:
（A+x）/8-2x