6
$\begingroup$

How can I show that for any set of 5 integers, there is at least one subset of 3 integers whose sum is divisible by 3?

I tried to think about it using the pigeonhole principle but I don't quite get it.

$\endgroup$
  • 1
    $\begingroup$ Just a single application of the pidgeonhole principle won't quite get you there, although it is close. Hint: each of the five integers has a remainder when divided by 3; what are the possibilities for these five remainders? $\endgroup$ – Mees de Vries Nov 4 '16 at 10:58
  • 5
    $\begingroup$ By the pigeonhole principle, if you have 5 colored balls, then you either have 3 balls of the same color, or else you have 3 balls which are all of different colors. $\endgroup$ – bof Nov 4 '16 at 11:02
  • $\begingroup$ They can be 0, 1 or 2 :D @MeesdeVries $\endgroup$ – Firdaws Nov 4 '16 at 11:02
  • $\begingroup$ How do I conclude that from the pigeonhole principle? Doesn't it only state that if n items are put into m containers, with n > m, then at least one container must contain more than one item? @bof $\endgroup$ – Firdaws Nov 4 '16 at 11:06
  • $\begingroup$ I'm thinking of a different "pigeonhole principle" which says that, if $mn+1$ objects are put into any number of containers, then either there are $m+1$ objects in one container, or else there are $n+1$ objects all in different containers. $\endgroup$ – bof Nov 4 '16 at 11:22
7
$\begingroup$

One way to approach this is as follows: Let $q \in \Bbb N$ be given. Note that for every $q$, there exists some $x \in \Bbb N$ and some $v \in \{0,1,2\}$ such that $q = 3x + v$.

Now let $x_i \in \Bbb N, v_i \in \{0,1,2\}$ be given such that $q_i = 3x_i + v_i$ for all $(1 \leq i \leq 5)$ What we're trying to prove is that for every possible realization of this set of five variables we can find at least one combination of $v_a + v_b + v_c = v_6$ such that $a,b,c$ are all distinct and in $\{1,2,3,4,5\}$ and that $v_6$ is divisible by three.

Assume that there exist a combination of three $v_i (1 \leq i \leq 5)$ such that all three $v_i$ are equal. Without loss of generality we can assume these are $v_1,v_2,v_3$. Then we have that $q_1 + q_2 + q_3 = 3(x_1 + x_2 + x_3) + 3v_1 = 3(x_1+x_2+x_3 + v_1)$ Where me make use of the assumption that $v_1=v_2=v_3$. Clearly the sum $q_q + q_2 + q_3$ is devisible by three.

Now assume there exists no combination of three $v_i(1 \leq i \leq 5)$ such that all three are equal. It is trivial to show that now we have at least one $v_i$ for every possible realisation of $v_i$. Thus, without loss of generallity we can assume $v_1 =0, v_2=1, v_3=2$. We now obtain: $q_1 + q_2 + q_3 = 3(x_1 + x_2 + x_3) + v_1 + v_2 + v_3 = 3(x_1 + x_2 + x_3) + 3 = 3(x_1 + x_2 + x_3 + 1)$.

Which is clearly devisible by three. This completes the proof.

Note that this proof is only applicable for natural numbers. But the extention to integers shouldn't cause too much trouble.

$\endgroup$
  • $\begingroup$ Look at it this way: you have three types of coins: coin A, B and C. Lets try to draw 5 coins such that not every type is drawn and we do not have three or more of one coin. We could for example draw AABB as coins, now we still don't have 3 of the same, and we don't have A, B ánd C. But at the fifth draw, no matter if you draw A, B or C, you are guarenteed to either end up with three equal coins or with at least one of every type. $\endgroup$ – Casper Thalen Nov 4 '16 at 14:07
2
$\begingroup$

Suppose the numbers are $x_1, x_2, x_3, x_4$, and $x_5$. For each $i$, let $r_i$ be the unique number $r_i \in \{0,1,2\}$ such that $r_i \equiv x_i \pmod 3$. Then we need to show that every possible instance of the list $r_1, r_2, r_3, r_4,r_5$ contains three numbers whose sum is congruent to $0$ modulo $3$.

The first thing to notice is that all three numbers $0,1$, and $2$ cannot occur in the list at the same time, since $0+1+2 \equiv 0 \pmod 3$

So you must have a list of 5 numbers chosen from one of the sets $\{0,1\}, \{0,2\}$, or $\{1,2\}$. By the pigeon-hole principle one of those numbers must occur at least three times. Since $0+0+0 \equiv 1+1+1 \equiv 2+2+2 \equiv 0 \pmod 3$, then there will always exist a subset of three numbers whose sum is a multiple of three.

$\endgroup$
  • $\begingroup$ I think you misuse the pigeon hole principle. The set $\{1,1,2,2,3\} $ does not contain three numbers of the same congruence mod 3. $\endgroup$ – Will Fisher Nov 4 '16 at 12:46
  • $\begingroup$ @WillFisher - I said that I said the numbers 0,1,2 cannot occur in the list. Somehow it got deleted. I'll put it back. $\endgroup$ – steven gregory Nov 4 '16 at 19:06
1
$\begingroup$

Working from the comments, we're trying to fit $5$ integers into $3$ different remainder classes. So think of the integers as elements and each possible remainder as a box. Now the pigeonhole principle gives that either there will be $3$ or more integers in one remainder class, or that there is at least one integer in all of the classes.

If it's the first possibility then just picking the set of $3$ integers in the one remainder class will give a sum divisible by $3$. If it's the second possibility then we choose for our set one element from each remainder class, and the sum will once again give us 3.

To see this remember that for any $z\in \mathbb{Z}$ we have that $$z=3q+x$$ where $q$ is an integer and $x\in \{0,1,2\}$.

$\endgroup$
  • $\begingroup$ This is not correct. Since for every $z \in \Bbb Z$ we have that $z=3q+\frac{x}{3}$, is undefined for every $x \in \{1,2\}$. This concerns integers and fractions are not a part of the set of integers. $\endgroup$ – Casper Thalen Nov 4 '16 at 16:42
  • $\begingroup$ @CasperThalen Yes silly mistake on my part thank you. I juxtaposed the representation of any integer divided by 3 with the representation of any integer modulo 3 to acquire nonsense. Thanks for pointing it out. $\endgroup$ – K.Power Nov 4 '16 at 20:52
0
$\begingroup$

The set of three numbers to give non multiple of $3$ sum can have $6$ possibilities. $(0,0,1),(0,0,2),(0,1,1),(0,2,2),(2,1,1),(2,2,1), $ Where the elements of set represent modulo $3 $ of actual numbers. For any possibility, a set of $3 $ numbers can be made to get sum multiple of $3$. For example $ (0,1,1)$ if two others numbers have $1$ or $2$,change the set accordingly as $ (1,1,1) $ or $(0,1,2) $ respectively. Or if both numbers are $ (0,0 )$ then the set of $3$ zeros. Same logic can be applied for other possibilities.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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