求一个最大的数

新用户

给你任意个6（0个6， 1个6， 2个6， 3 个6 。。。。。。）
给你任意个9（0个9， 1个9， 2个9， 3 个9 。。。。。。）

给你任意个20（0个20， 1个20， 2个20， 3 个20 。。。。。。）www.ddhw.com

 

求：不能用任意个6，任意个9， 任意个20之和来表示的最大的数。www.ddhw.com

 

比如说，3就不能用6，9， 20之和表示，7也不行，11也不行，15可以（=6+9）

www.ddhw.com

 

怀疑

  有数论定理

怀疑

  37

新用户

  请给出解题过程

怀疑

Sorry, I just  gave this problem 10 seconds before I wrote the wrong answer 37 down.   The correct answer is  43.    There are some simple method (e.g., show 44, 45, 46, 47, 48, 49 can be expressed. But this is good only if you can guess 43 quickly).   It is easy to see that {3a+20b: a, b>=0} = {6a+9b+20c: a, b, c>=0}+{3+20b}. The largest number that is not in {3a+20b} is 20*3-20-3=37.  And the largest number in www.ddhw.com {3+20b}\{6a+9b+20c} is 43: this is because 3+20b=63+20(b-3)=7*9+20(b-3) for b>=3.       （Probably there is some theorem that can directly solve the problem. But I only  remember the following:    If x>0, y>0, (x, y)=1, then the largest number that is not in {ax+by:a, b>=0} is xy-x-y.   The proof is easy:www.ddhw.com    Suppose xy-x-y=ax+by, a>=0, b>=0, then x(y-1-a)=(b+1)y, since (x, y)=1, then x | b+1, b>=x-1, similarly a>=y-1, then ax+by>=x(y-1)+y(x-1)>xy-x-y.  Contradiction. Thus, xy-xx-y is not in {ax+by: a, b>=0}   For  a number n>xy-x-y,  n=cx+dy for some integers c and d. Suppose c>=0. If c>=y, replace (c, d) with  (c-y, d+x). Keep doing this, we get n=cx+dy, 0<=cxy-x-y-x(y-1)=-y, d>-1, i.e., d>=0. )   www.ddhw.com

新用户

  perfect!!