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

  • 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.2011-12-08
  • 0
    @Aaron:Abstract algebra is still *terra incognita* for me, could you explain congruence classes or replace it with something that easily understandable?2011-12-08
  • 0
    @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$).2011-12-08
  • 0
    @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'?2011-12-08
  • 0
    @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$.2011-12-08
  • 0
    @MaX: The relation $a$ is congruent to $b$ modulo $m$ (aka $m$ divides $a-b$, aka $a$ and $b$ have the same remainder on division by $m$, aka $a\equiv b \pmod{m}$, is an equivalence relation, and congruence classes are equivalence classes.2011-12-08
  • 0
    @MaX Just to elaborate on what Andre said, "equivalence class" is a rather general term for the classes under any sort of equivalence relation you might have (e.g., congruence, equality of some aspect, isomorphism, similarity, etc.) Often times, when your equivalence has a name or a particular useage, the equivalence classes will be given special names (e.g. congruence class, isomorphism class, orbit, conjugacy class, coset, etc.). The names add context, just like using particular variables in particular ways does. However, they are all just instances of equivalence classes.2011-12-08
  • 0
    @André:Thanks for your explanation; I proved that $ a\equiv b \pmod{m}$ is an equivalence relation proving reflexive, symmetric and transitive simultaneously.:)2011-12-08
  • 0
    @ Aaron:So my understanding of your comment: Every $a \in$ $1$ to $300$ can be either $a\equiv 0 \pmod{3}$ or $a\equiv 1 \pmod{3}$ or $a\equiv 2 \pmod{3}$ so if we choose the congruence class $a\equiv 1 \pmod{3}$ we cannot choose any from the congruence class $a\equiv 2 \pmod{3}$ as summing them up would be a multiple of $3$. And after that we could only choose 1 element of the form $a\equiv 0 \pmod{3}$. Thus making the maximum possible numbers in the list to $101$. Right?2011-12-08
  • 0
    @MaX: Good! I find a simultaneous proof hard to imagine, though each part follows fairly directly from the definition. You will find this type of construction useful later in constructing new abstract structures. And your comment about the $101$ is correct. Alternately we can take the $100$ numbers in the list that are $\equiv 2 \pmod{3}$, plus $1$ number congruent to $0$.2011-12-08
  • 0
    @MaX Yes, exactly. It might be a fun exercise to try to generalize the problem. Try it with 7 instead of 3 (i.e., numbers from 1 to 700, no two add up to a multiple of 7). If you can explain why the answer is 301, you should be set.2011-12-09
  • 0
    @Aaron:For the multiple of $7$ the congruence classes will be $0,1,2,3,4,5,6$; and as it is between $1$ to $700$ there will be exactly 100 of them in each class; which choosing, if we choose 1 we can't choose 6 and if we choose 2 we can't choose 5 and in the same way 3 will not go with 4; so we can choose only in the manner {1,2,3},{1,2,4},{1,3,5},{1,4,6},... and we can choose the maximum of one element from the congruence class 1 hence $300+1=301$.2011-12-09
  • 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