4
$\begingroup$

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5.

I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any thoughts on what should the holes be ?

$\endgroup$

3 Answers 3

4
$\begingroup$

Since you don't seem to be familiar with modular arithmetic I won't use the language of congruences.

Every integer is of one of the following forms, $$ 5k, \ 5k + 1, 5k + 2, 5k + 3, 5k + 4; \; \text{for some integer $k$} $$

Now, if you pick $17$ integers by the pigeonhole principle either you must pick at least $1$ from each class or else you will have $5$ from the same class.

Say you picked at least $1$ from each class then they are of the form, $$5k_1, \ 5k_2 + 1, \ 5k_3 + 2, \ 5k_4 + 3, \ 5k_5 + 4$$ Now their sum is equal to $$5(k_1 + k_2 + k_3 + k_4 + k_5) + 10 \;\; \text{which is clearly divisible by $5$}$$

OR

You've picked $5$ integers from the same class and they are of the form $$5k_1 + i, \ 5k_2 + i, \ 5k_3 + i, \ 5k_4 + i, \ 5k_5 + i$$ where $i \in \{0,1,2,3,4\}$. It is easily seen that their sum too is divisible by $5$

$\endgroup$
3
  • 1
    $\begingroup$ I think that should be "... if you pick $17$ integers by the pigeonhole principle you must pick $5$ from the same class or at least 1 from each class..." $\endgroup$ Feb 20, 2014 at 16:18
  • $\begingroup$ @user73985: You're right.. Corrected.. $\endgroup$
    – Ishfaaq
    Feb 20, 2014 at 16:25
  • $\begingroup$ @Ishfaaq understand if the 5 selected integers are in either the same class or if they are selected so that at least one is in each class we can find their sum to be divisible by zero.But i don't understand how we get to think as` if you pick 17 integers by the pigeonhole principle either you must pick at least 1 from each class or else you will have 5 from the same class.` $\endgroup$
    – clarkson
    Nov 16, 2014 at 8:24
3
$\begingroup$

"Divisible by 5" suggests considering modulo 5. Can you have 5 of them in the same residue class mod 5? If not, will you have at least 1 in each residue class? If so, notice that $0+1+2+3+4 = 10$.

As chubakueno pointed out, this isn't a tight bound. We can easily cut it down by the following.

We can add 1 to each number and it doesn't affect whether there are 5 of them with the property, so we can add until residue class 0 is the biggest.

If there are at least 3 "0"s, there cannot be both "1" and "4" or both "2" and "3", giving at most $4+4+4 = 12$. In the other case there are at most 2 "0"s, and hence at most 2 in each residue class, giving at most 10 numbers in total. This gives an upper bound of 12, which still isn't tight, and if we want we can push even further.

If there are at least 3 "0"s,

  There cannot be:

    "1,2,2" or "1,1,1,2"

    "1,1,3" or "1,3,3,3"

    "2,4,4" or "2,2,2,4"

    "3,3,4" or "3,4,4,4"

  Therefore in any pair of non-empty non-zero residue classes has at most 3 numbers in total

  But as before for every non-zero residue class its complementary class must be empty

  So there will be at most 2 non-empty non-zero residue classes

  If there are 2 non-empty non-zero residue classes,

    They have at most 3 numbers in total

  If there is at most 1 non-empty residue class,

    There are at most 4 numbers in it

  Therefore there are at most $4+4 = 8$ numbers

If there are at most 2 "0"s,

  If there is a non-zero residue class with 2 numbers in it,

    We could make it such that it is either residue 1 or residue 2

    If we have 2 "0"s and 2 "1"s,

      There cannot be any "3" and there can be at most 1 "2" and 1 "4"

      Therefore there are at most $2+2+1+1 = 6$ numbers

    If we have 2 "0"s and 2 "2"s,

      There cannot be any "1" and there can be at most 1 "3" and 1 "4"

      Therefore there are at most $2+2+1+1 = 6$ numbers

  If every non-zero residue class has at most 1 number in it,

    There are at most $2+1+1+1+1 = 6$ numbers

  Therefore in any case there are at most 6 numbers

Therefore there are at most 8 numbers and it is tight because of $(0,0,0,0,1,1,1,1)$

$\endgroup$
7
  • $\begingroup$ I was mistaken. Had to edit. Thank you ! $\endgroup$
    – lvi
    Feb 20, 2014 at 16:52
  • $\begingroup$ @lvi his hint uses that $16<17$. But actually, 17 is not a tight bound. $\endgroup$
    – chubakueno
    Feb 20, 2014 at 16:54
  • $\begingroup$ @chubakueno: Please help me check my proof for the tight bound, in case I made some mistake! $\endgroup$
    – user21820
    Feb 21, 2014 at 6:00
  • $\begingroup$ I didn't understand Therefore in any pair of non-empty non-zero residue classes has at most 3 numbers in total .Is there a typo, maybe? $\endgroup$
    – chubakueno
    Feb 21, 2014 at 23:04
  • $\begingroup$ It's because those blocking combinations between pairs of classes are such that if you have 1 in one class, you can have at most 2 in the other class. For example if you have 1 "1", you can have at most 1 "2", and if you have 1 "2", you can have at most 2 "1"s. $\endgroup$
    – user21820
    Feb 22, 2014 at 2:35
1
$\begingroup$

My idea; we have 0+1+2+3+4=10 which is a multiple of 5 or generally we have 0mod5+ 1mod5+ 2mod5+ 3mod5+ 4mod5=0mod5. Let's try to argue the 17 number, the least random number to chose, so we can find 5 among them that sum up to a number multiple of 5. There are some ways to sum up to 0mod5, (partition of 5); 5=1+1+1+1+1+1=2+1+1+1+0=2+2+1+0+0=2+3+0+0+0+0=1+4+0+0+0+0, (0 is very important here) If we chose 5 random numbers and they are all 0mod5, or all 1mod5, ..., or all 4mod5, then we have finished. But, we are not sure that will happen. We will try to collect all the numbers avoiding 5x 1,2,3,4(mod5), 1 2 3 4, 1 2 3 4, 1 2 3 4, 1 2 3 4, We have 16 numbers here, and there is not a case that we can find 5 numbers here that sum up to a multiple of 5. We need only one number which can be anything, 0mod5, 1mod5, 2mod5,3mod5, 4mod5, and the problem is solved. So, if we have 17 natural random numbers, we can find 5 numbers among them, that sum up to a number multiple of 5. This is my solution. Best Regards,

$\endgroup$

You must log in to answer this question.

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