求一个最大的数

怀疑

  有数论定理

怀疑

  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