find the largest number that can't be written as $2008x+2009y+2010 z$

Question

Find the largest number that can't be written as $2008x+2009y+2010 z$, in the following cases:

1. $x,y,z$ are all positive integers.
2. $x,y,z$ are all nonnegative integers.

For integers $a_1,\cdots, a_n,$ let $N_{a_1,\cdots, a_n}$ denote the set of all nonnegative linear combinations of $a$ and $b$ (i.e. all integers $\sum_{i=1}^n k_i a_i, \,\forall 1\leq i\leq n, k_i\ge 0$). Define $P_{a_1,\cdots, a_n}$ to be the set of all positive linear combinations of the $a_i$'s. I know that if $a,b$ are positive integers, the largest positive multiple of $d := \gcd(a,b)$ that is not in $N_{a,b}$ is $\dfrac{ab}d-a-b.$ Then the largest positive multiple of $\gcd(a,b)$ that is not in $P_{a,b}$ is $\dfrac{ab}d.$ Indeed, from any number exceeding $\dfrac{ab}d$ we can subtract $a$ and $b$ to get a number exceeding $\dfrac{ab}d-a-b \ge \dfrac{ab}d-a-b$, and from above we know this number must be in $N_{a,b}$. Also, if $ab/d = ax+by$ for positive integers x and y, then $ab/d -ax = by \Rightarrow a/d (b/d-x) = b/d y,$ so $a/d | y\Rightarrow y\ge a/d$ and $b/d | (b/d - x)\Rightarrow b/d - x \ge b/d$. The latter inequality is a contradiction as $x > 0.$ For the particular problem, we know $1004\cdot 1005/2 - 1004 - 1005)$ is the largest even integer that is not in $N_{2008,2010}.$ But I'm not sure what the largest integer that is not in $N_{2008,2009,2010}$ (is it just $2009 + 1004\cdot 1005/2 - 1004 - 1005$?). I think the largest integer that is not in $P_{2008, 2009,2010}$ might be larger than the latter integer.

Edit: following a similar approach to @ThomasAndrews' answer, I think the answer to the first question is $C := 2008\cdot 1007+2.$ First I claim that $C$ cannot be achieved. Indeed, if this were the case then we could write $2008a+b+c =C$ for some $a > b > c > 0.$ Then note that $b+c\leq 2a-3.$ So $a\leq 1006$ implies $b+c\leq 2009$ and so $2008 a + b+c < 2008\cdot 1006 + 2010 = C.$ Hence we must have $a=1007$ and that is clearly impossible since $b+c > 3$ implies $2008a+b+c > C.$ Next I claim that any number that's at least $C + 1$ can be expressed in the desired form. To see why, take such a number $z.$ Then if $C+1 \leq z\leq 2008\cdot 1008 - 1,$ let $k= z-(C+1)$ so that $0\leq k \leq 2004.$ Note that we just need $b+c = k+3$ to have $2008\cdot 1007 + b+c = z.$ If $0\leq k\leq 1004,$ let $a=1007, b=k+2, c=1.$ If $1005\leq k\leq 2004,$ then let $a=1007, b=1006, c=k-1004.$ Now suppose $2008 x \leq z \leq 2008(x+1)-1$ for some $x\ge 1008.$ If $z = 2008 x + i$ for some $0\leq i\leq 2,$ let $a=x-1, b=1006, c=1002 + i$. If $z =2008x+i$ for some $3\leq i\leq 1008,$ let $a=x, b=i-1, c=1$. Finally if $z=2008x+i$ for some $1009\leq i\leq 2007,$ then let $a=x, b = 1007, c=i-1007.$

Answer 1

Write it as $2008a+b+c$ where $a=x+y+z, b=y+z, c=z.$ Then your condition is $a>b>c>0$ in the first case or $a\geq b\geq c\geq 0$ in the second case.

We'll take the second case, because it is easier.

If $a\leq1003,$ then $b+c\leq 2a\leq 2006 ,$ so we can never get $2008a+2007.$

On the other hand, if $a\geq 1004,$ for any $r=0,1,2,\dots,2007,$ we can find $c\leq b\leq a$ such that $r=b+c.$

So this means the largest number we can't reach is $2008\cdot 1003+2007=2008\cdot 1004-1.$

You can deduce the answer for the first case from the second case.

The same works for $mx +(m+1)y+(m+2)z$ for any $m.$ For $m$ even, you get $m^2/2-1$ is not a number of this form. For $m$ odd, a little care is required. $\frac{m(m-1)}{2}-1?$

Answer 2

This is the Frobenius Coin Problem.

The specific question of largest number not represented by $2008x + 2009y + 2010z$ is a special case of finding the Frobenius number for elements that form an arithmetic sequence.

A simple closed form formula exists for the Frobenius number of a set of integers in an arithmetic sequence. Given integers $a, d, w$ with $\gcd(a, d) = 1$, the Frobenius number for the set is:

$$ {\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)} $$

For the example problem, $a = 2008, d = 1, w = 2$.

$$ \begin{align} g(2008, 2009, 2010) & = \left(\left\lfloor {\frac {2008-2}{2}}\right\rfloor \right)2008+(1)(2008-1) \\ & = 1003 \times 2008 + 2007 \\ & = 2016031 \end{align} $$

Answer 3

I can't follow what you are saying even from the start, so this is an alternative approach that I hope will help.

For $b=2008$, it is $$bx + (b+1)y + (b+2)z = n$$ $$bx + (y+z)b + y + 2z = n$$

The $bx$ term makes it clear that all multiples of $b$ can be constructed by choosing $y=z=0$.

All $n \equiv 1 \pmod b$ can be constructed except $n=1$ by letting $y=1, z=0$.

All $n \equiv 2 \pmod b$ can be constructed except $n=2$ by letting $y=0, z=1$.

All $n \equiv 3 \pmod b$ can be constructed except $n=3, n=b+3$ by letting $y=1, z=1$.

All $n \equiv 4 \pmod b$ can be constructed except $n=4, n=b+4$ by letting $y=0, z=2$.

Etc.

All $n \equiv r \pmod b$ can be constructed except $n=kb+r, k < y+z$ by letting $y=(r \bmod 2), z=\lfloor r/2 \rfloor$.

So the largest will come from choosing $r=b-1, k=y+z-1$.