Number Theory #7

[I will use the term 'numbers' for non-negative integers]

The Frobenius number of 'n' numbers $a_1,a_2,a_3,.....a_n$ is the largest number which cannot bee expressed as $a_1.n_1+a_2.n_2+a_3.n_3+........a_n.n_n$ . For any two numbers 'm' and 'n', their Frobenius number is given by $mn-m-n$ .

It is easy to see then, that the largest number not in the set $S$ is $97$ (which is the Frobenius number of 50 and 3). Also the numbers which are multiples of 50 or 3 or both are in the set. Thus, we get ""only"" 49 such numbers, which can be easily added to yield 2009 as the answer.

It is given that the set of integers $s(m,n) = 50m+3n$ . And find the sum of all integers not in set s. This means there is a finite number of integers not in set $s$ . Let us first consider $s(m,n)$ for $m=0,1,2$ for $n=0,1,2,....$

$s(0,n)=0,3,6,...48,51,54,...96,99,102,....$

$s(1,n)=50,53,56,...98,101,104,....$

$s(2,n)=100,103,106,....$

Adding the three series together, we have

$s(m,n)=0,3,6,...48,50,51,53,54,...96,98,99,100,101,102,103,104,105,106,....$ , where $m=0,1,2$ .

Since for $m=0,1,2$ , from the term $= 98$ onward, it continues to infinity, this means that the series is true for $m=0,1,2,...$ as well. Therefore

$s(m,n)=0,3,6,...48,50,51,53,54,...96,98,99,100,101,....$ , where $m=0,1,2,...$ and $n=0,1,2,....$

And the series of integers not in $s$ is $1,2,4,5,...49,52,55,...91,94,97$ and its sum $N$ is given by:

$N=1+2+4+5+...+49+52+55+...+91+94+97$

$=(1+4+7+...+49+52+55+...+91+94+97)+(2+5+8+...41+44+47)$

$=\sum _{ i=0 }^{ 32 }{ (3i+1)+\sum _{ j=1 }^{ 16 }{ (3j-1) } }$

$=\frac { 33 }{ 2 } (1+97)+\frac { 16 }{ 2 } (2+47)=\boxed{2009}$

All multiples of three are in $s$ .

For $n \equiv 2 \pmod 3$ , we require to add one $50$ . Thus, the $n \equiv 2 \pmod 3$ which are in $s$ are $50, 53, 56, \dots$ . This means that $2, 5, 8, \dots, 47$ are not in $s$ .

For $n \equiv 1 \pmod 3$ , we require to add two $50$ s. So, $100, 103, 106, \dots$ are in $s$ while $1, 4, 7, \dots, 97$ are not.

Adding those up, we get $2009$ .