# How many integers less than $300$ is such that the sum of any two of them is not divisible by $3$?

Pam chose some numbers from $1$ to $300$ and wrote them down. As she observed her list, she noticed a peculiar fact that no two numbers on this list added up to a multiple of $3$. What can be the maximum possible number of numbers on this list?

There are exactly $200$ numbers $($ignoring the set $\{ 3,6,9 ,\cdots, 300 \} )$ between $1$ and $300$ which are not divisible by $3$; now among these we have to choose all such that $\forall a,b$ in the list such that if $a \equiv x_1 \pmod 3$, $\space b \equiv x_2 \pmod 3$ then, $x_1+x_2 \not\equiv 0 \pmod 3$. Which is the fastest method for counting all such unique $a$ and $b$?

-
Note that the list can contain at most one multiple of 3, and if it contains an element congruent to $1 \mod 3$, then it contains no elements congruent to $-1 \mod 3$. These are the only restrictions. Therefore, since there are $100$ elements between $1$ and $300$ in each congruence class, you can have a maximum of $100+1=101$ elements in a list. – Aaron Dec 8 '11 at 2:07
@Aaron:Abstract algebra is still terra incognita for me, could you explain congruence classes or replace it with something that easily understandable? – Quixotic Dec 8 '11 at 2:19
@MaX: "congruent to $1\bmod 3$" numbers of the form $3k+1$ for some integer $k$; that is, one more than a multiple of $3$. "congruent to $-1\bmod 3$" means that it is of the form $3k-1$ (or $3k+2$); that is, one less than a multiple of $3$. The "congruence class" is just all numbers that satisfy the condition (there are 100 multiples of $3$; 100 numbers that are one more than a multiple of $3$; 100 numbers that are one less than a multiple of $3$). – Arturo Magidin Dec 8 '11 at 2:25
@Arturo Magidin:I knew about the "congruent to $1 \mod 3$" and the later but thanks for explaining 'congruence classes'; so just to complete the definition it also means that there are $100$ numbers that are $2$ less than a multiple of $3$ and same goes for $-2$ isn't? Also, is 'congruence classes' same as 'equivalence class'? – Quixotic Dec 8 '11 at 2:53
@MaX: Numbers that are 2 less than a multiple of 3 are exactly the same as numbers that are 1 more than a multiple of 3, since $3k-2 = 3(k-1)+1$. Numbers that are -2 less (that is, 2 more) than a multiple of 3 are the same as numbers that are 1 less than a multiple of 3, since $3k+2 = 3(k+1)-1$. – Arturo Magidin Dec 8 '11 at 3:13

Note that the list can contain at most one multiple of $3$, and if it contains an element congruent to $1 \mod 3$, then it contains no elements congruent to $−1 \mod 3$. These are the only restrictions. Therefore, since there are $100$ elements between $1$ and $300$ in each congruence class, you can have a maximum of $100+1=101$ elements in a list.
In slightly more elementary terms, define $3$ sets, $[1],[2]$, and $[3]$, where $[i]=\{3k+i \mid 0\leq k < 100 \}$. Each of these three sets contains $100$ elements. Our desired set cannot contain more than one element from $[3]$, and it cannot contain any elements from both $[1]$ and $[2]$. This gives a maximum possible size for our set of $1+100$, obtained by taking e.g., all the elements in $[1]$ and one element in $[3]$. Moreover, if two elements sum to a multiple of $3$, either they are both in $[3]$ or one is in $[1]$ and the other is in $[2]$, which shows that our hypothetical example works.
One might add that taking all of $[2]$ and one element of $[3]$ works equally well. – Marc van Leeuwen Feb 12 '14 at 12:22