有面值为6,9,20的分币,问最大的不可能组成的数是多少?

Published in categories blog  Research  tagged with #博客  #math  #coding 

昨天LL同学(特别提醒不是ZL)发的问题,今天发现健健博客写到这道题

一看就是数论题,结果健健第一种方法是写程序。。OMG。。是的看来程序还木有渗入我的生活

看别的方法发现赫然写着数论爆初级结论。。毛线都记不得了。。

还好自己用一般弱的方法做出来了>< 不是很弱。。

—————————————————————–洒水的分割线——————————————————

方法一:我的普通方法:

最初觉得想用数学归纳法做,但是要考虑其完备性,

若 k=6l +9m +20n

则 k+1=6(l+2) +9(m+1) +20(n-1)

   k+2=6(l-3)   +9m         +20(n+1)   (l,m,n足够大)

随着k->k+2不断递推,l会越来越小,但是通过 203转化成610 可以转化l值,从而可以得到完备的归纳,可以知道归纳的k的初值是(l,m,n)=(0,0,3)

做到这里的时候,我在想是否要将剩下的数一个一个计算是否能被这样构成。在计算的时候,发现了新的方法。

如果一个数k符合要求,那它一定满足k=6l+9m+20n 现在我们假设n>=2(这是这种方法的关键,3和(6,9)=3密切相关)

现在要求l,m,n的解,记 x=k-20n

在这里,若x足够大

6l+9m=3(2l+3m)=x

6l+9m=3(2l+3m)=x+20

6l+9m=3(2l+3m)=x+40 三个方程必定有一个有自然数解。(因为x, x+20, x+40三个数必有一个能被3整除,而2l+3m=a对除1外的数都有解)

若三个方程都无自然数解,则说明x能被3整除,但第一个方程得到的简化方程是2l+3m=1,并且n=2

反推可得,x=3, n=2, k=43

一个初等数学的题目方法写这么复杂我觉得自己弱爆了><

方法二:代码法:

先排除100以上的数(具体可见健健的方法),在通过两个循环计算不能组成的数。计算机比人脑快多了,我们要好好利用呀~

方法三:大神的数论法:

感谢蒋炎岩 的方法:

假设整数x,y>=0,6和9可以表示所有3(x+2)的,20可以表示所有20y的。于是原来的问题就是3x+20y+6无法表示的最大数。ax+by不能表示的最大数是ab-a-b(数论爆初级结论,请自行证明),于是得到43

学过数论的少年表示记不得有这个结论了,桑心,遁地看书去。

健健说的不错,不论什么方法,积极思考就是好的~~

PS.感觉自己的思维还定在原来的小格子里,应该走出来学会用新的东西改造自己。

comments powered by Disqus