5
$\begingroup$

How do I prove that among any $5$ integers, you are able to find $3$ such that their sum is divisible by $3?$ I realize that this is a number theory question and we use modular arithmetic, but I'm unsure of where to begin with this specific situation.

$\endgroup$
9
$\begingroup$

Consider the residue class modulo $3$ of each of the five numbers. If three of them are equal, then the numbers corresponding to them will work. Otherwise, no three numbers have equal residue classes, but there are only $3$ potential residue classes, and that means that all three actually occur. The numbers corresponding to these classes work.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

All the integers can be represented as $3n+1, 3n+2$ or $3n; n \in \mathbb{Z}$. Among the five integers, if there is at least one integer of each form, then their sum would be divisible by $3$, as $3a+(3b+1)+(3c+2)=3(a+b+c)+3 \equiv 0 \, (\mathrm{mod} \; 3)$

If there isn't, all the numbers are of the remaining two forms. So, there are at least three integers of the same form, which is obvious using the pigeon hole principle. Their sum would be divisible by 3 as $(3a+i)+(3b+i)+(3c+i)=3(a+b+c+i)\equiv 0 \, (\mathrm{mod} \; 3);i =0,1,2$ Thus, completing the proof.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Hint: pigeonhole principle. $5$ pigeons (integers) and $3$ pigeonholes (numbers of the form $3n, 3n+1, 3n+2$). This works for $5$ or $4$ distinct integers among the $5$. If $3$ or more integers are the same, then it is trivial since you have 3 times the same number, say $k$, so $k+k+k=3k$ is obviously divisible by $3$ no matter what $k$ was.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Consider the remainders of the numbers when divided by 3. Clearly there are only three possible remainders: 0, 1 or 2.

  • If all these remainders occur among the given numbers, then adding together three numbers with different remainders will yield a sum that is divisible by 3 (since 0 + 1 + 2 = 3).

  • Otherwise, at least one of the three remainders does not occur among the five given numbers. By the pigeonhole principle, at least one of the other two remainders must thus occur more than twice (since 5 > 2 × 2). Adding together three numbers with the same remainder will then yield a sum divisible by 3.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And yes, I'm aware that this is essentially equivalent to several of the answers already given by others. I just wanted to try giving an elementary answer using as simple language as possible, without a profusion of notation or fancy terms like "residue class". That said, I did give the other answers a +1 too. $\endgroup$ – Ilmari Karonen Dec 1 '15 at 14:16
  • $\begingroup$ +1 from me, presented much better than the other answers. Although I would have just simply said "WLOG, this is the same problem if you restrict the numbers to $\{0, 1, 2\}$. $\endgroup$ – DanielV Dec 1 '15 at 20:57
2
$\begingroup$

Consider the following seven numbers:

$a_1\\a_2\\a_3\\a_4\\a_5\\a_1+a_2+a_3+a_4\\a_2+a_3+a_4+a_5$

Since there are seven numbers three of them must have same remainder modulo $3$. If all are from the first five then their sum is multiple of $3$ otherwise one of the four-element-sum and one of its summand must be included and their difference is divisible by $3$.

| cite | improve this answer | |
$\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.