2
$\begingroup$

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$?

  • 0
    @Aaron:I would also like to request you to post your initial comment as answer; so that I can accept :)2011-12-09

1 Answers 1

6

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.

  • 0
    One might add that taking all of $[2]$ and one element of $[3]$ works equally well.2014-02-12