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

$\endgroup$
13
  • 6
    $\begingroup$ 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. $\endgroup$
    – Aaron
    Commented Dec 8, 2011 at 2:07
  • $\begingroup$ @Aaron:Abstract algebra is still terra incognita for me, could you explain congruence classes or replace it with something that easily understandable? $\endgroup$
    – Quixotic
    Commented Dec 8, 2011 at 2:19
  • $\begingroup$ @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$). $\endgroup$ Commented Dec 8, 2011 at 2:25
  • $\begingroup$ @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'? $\endgroup$
    – Quixotic
    Commented Dec 8, 2011 at 2:53
  • $\begingroup$ @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$. $\endgroup$ Commented Dec 8, 2011 at 3:13

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ One might add that taking all of $[2]$ and one element of $[3]$ works equally well. $\endgroup$ Commented Feb 12, 2014 at 12:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .