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 {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: 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. ) |
欢迎光临 珍珠湾ART (https://zzwav.com/) | Powered by Discuz! X3 |