Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
One might add that taking all of $[2]$ and one element of $[3]$ works equally well. –  Marc van Leeuwen Feb 12 at 12:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.