Prove Sum Divisible by 5 with 5 Arbitrary Natural Numbers

[Zurtex]

The question asks me to prove that if I have 5 arbitrary natural numbers to show that one of the sums (in order) is divisible by 5. So say the numbers are a_1,a_2,a_3,a_4,a_5 some examples would be:

a_1 + a_2 + a_3

a_4

a_3 + a_4

etc..

My first thought was to consider the remainder upon division 5 and then start identifying all the possible combinations where the sum is divisible by 5 and show there are no more left. However when starting this I realized this was actually a lot of work and there must be some simpler way. Can anyone else point me in a different direction?

 

[lurflurf]

I don't know what in order means so I hope it does not matter.
consider the sums
a1
a1+a2
a1+a2+a3
a1+a2+a3+a4
a1+a2+a3+a4+a5
consider their remainders upon division by 5
There are 5 possible remainders {0,1,2,3,4} and 5 sums so either a sum is divisible by 5 (remainder=0) or of two of the sums remainders are equal.
if 2 sums remainders are equal the difference of the sums is itself a sum and is divisible by 5
so for example if (a1,a2,a3,a4,a5,n,m,r are natural numbers)
a1+a2=5m+r
a1+a2+a3+a4=5n+r
5|a3+a4

 

[wais]

One way to approach this problem is by using the pigeonhole principle. The pigeonhole principle states that if n+1 objects are placed into n boxes, then at least one box must contain two or more objects.

In this case, we have 5 natural numbers, so we can think of them as 5 objects. If we divide them into 4 boxes, at least one box must contain two or more numbers. This means that there must be a sum of two or more numbers in that box, and since we are dealing with natural numbers, the sum must also be a natural number.

Now, since we have a sum of two or more numbers in one of the boxes, we can add that sum to the remaining number (that is not in the box) to get a new sum. This new sum will also be a natural number.

We can continue this process until we have only one number left. This last number will be the sum of all the original numbers, and since it is a natural number, it must be divisible by 5.

Therefore, we have shown that one of the sums of 5 arbitrary natural numbers is divisible by 5, using the pigeonhole principle.