0

Let S be a set of three distinct integers. A be a nonempty subset of S and $\sigma _A$ be the sum of A. Now prove that there exist two distinct non empty subsets $B,C\subset S$ with $\sigma _B\equiv \sigma_C \bmod 6$

Now I am able to figure out that we $\sigma _A$ could be the sum of any of these seven possibilities:

$$\{\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$$

Now the book states that for each subset A of S, $\sigma _A$ is congruent to $0,1,2,3,4,$ or $ 5$ $\bmod 6$. How could I be sure of this?

lulu
  • 70,402
ALEXANDER
  • 2,099
  • Does $Q_c=\sigma_C$? – lulu Apr 11 '16 at 23:05
  • To your second question, every integer is congruent to one of those numbers $\pmod 6$. Those are the possible remainders on division by $6$. – lulu Apr 11 '16 at 23:06
  • Yes, lulu, I apologize for the notation something went wrong. – ALEXANDER Apr 11 '16 at 23:08
  • No problem. In that case, your claim follows from the Pigeonhole Principle: as you noted, you have $7$ subsets, hence $7$ sums, and there are only $6$ possible residue classes. – lulu Apr 11 '16 at 23:09
  • but why is every integer congruent to one of those numbers (mod6). Could you explain a bit further? – ALEXANDER Apr 11 '16 at 23:11
  • 1
    If $n$ is any integer we try to divide $n$ by $6$. We may fail, but we can always do it if you allow a remainder. Specifically, we can always write $n=6q+r$ where $0≤r<6$. Of course it follows that $r\in{0,1,2,3,4,5}$. Also, it is clear that $n\equiv r \pmod 6$. – lulu Apr 11 '16 at 23:14

1 Answers1

1

For all $A\subseteq S$, you can be certain that $\sigma_A$ is congruent to 0, 1, 2, 3, 4, or 5 mod 6 because there are no other options for $\sigma_A$. You could just as easily say $\sigma_A$ is congruent to

  • 0, 1, or 2 mod 3
  • 0, 1, 2, 3, ..., 198, 199 mod 200
  • 0, 1, 2, ..., $n-1$ mod $n$ (in general)

It wouldn't make any sense to say $\sigma_A$ is congruent to 7 mod 6 because we just call that 1 again. $\sigma_A$ is the sum of integers, so it itself is an integer. Since congruence modulo $n$ is an equivalence relation on the integers, its equivalence classes partition the integers. Every integer must therefore belong to exactly one equivalence class, in this case 0, 1, 2, 3, 4, or 5. When talking about congruence, these are sets, not the actual integers. My professor wrote them as $[0]$, $[1]$, $[2]$, etc. where $[0]=\{...,-12,-6,0,6,12,24,...\}$, $[1]=\{...,-11,-5,1,7,13,...\}$, and so on, just to keep it straight in our heads.

Lulu also posted a comment which explains it another way using the division algorithm.

To continue the problem, the set of all subsets (i.e., the power set) of a set with size 3 is 7, which you showed by listing them all. The handy formula is $2^n-1$ where $n$ is the size of the set in question. So you have 7 sets that can be sorted into 6 equivalence classes. Intuitively, they must double up somewhere. Slightly more formally, this follows from the pigeonhole principle.

The pigeon hole principle states that if I have more pigeons than I have holes, there must be a hole with more than one pigeon stuffed in it. Or, if I have $p$ pigeons and $h$ holes with $p>h$, there exists at least one hole with greater than one pigeons in it. The contrapositive is even more intuitive. If all holes have 1 or fewer pigeons, then $p \leq h$. You could think of it as there are no onto functions from the set of pigeons to the set of holes.

For the case of your problem, replace "pigeons" with "sums of subsets of $S$" and "holes" with "equivalence classes modulo 6". Then using the pigeonhole principle, observe that at least one hole must have more than one pigeon in it. So if it has more than one, it must have at least two, and those are your two $\sigma$s.

The pigeonhole "proof" using the contrapositive isn't really a proof, just an appeal to intuition. If you're doing this for a class, you might be able to get away with just applying the pigeonhole principle if you've done something similar, or you could explain/prove it using the terms and assumptions you normally make in that class.

Cordello
  • 750