Any ideas (I have been struggling with this one for a while)?
Hi
The nine integer can be considered by their rest in the division by 5
There are 5 classes of rests : 0, 1, 2, 3 and 4
If 4 classes are empty, the nine integers are of the same class then any set of 5 integers works
If 3 classes are empty, then one of the 2 non-empty class has 5 integers. This set works
If 2 classes are empty :
- if 1 of the 3 non-empty class has only 1 integer then we have to consider the case where the 2 other classes have 4 integers (in the other cases one of the classes has 5 or more integers)
I do not see any other way than consider all the cases :
class 0 : 1 integer
class 1 : 4 integers
class 2 : 4 integers
==> 0-1-1-1-2 works
class 0 : 1 integer
class 1 : 4 integers
class 3 : 4 integers
==> 0-1-3-3-3 works
class 0 : 1 integer
class 1 : 4 integers
class 4 : 4 integers
==> 0-1-1-4-4 works
class 0 : 1 integer
class 2 : 4 integers
class 3 : 4 integers
==> 0-2-2-3-3 works
class 0 : 1 integer
class 2 : 4 integers
class 4 : 4 integers
==> 0-2-2-2-4 works
class 0 : 1 integer
class 3 : 4 integers
class 4 : 4 integers
==> 0-3-4-4-4 works
class 1 : 1 integer
class 0 : 4 integers
class 2 : 4 integers
==> 0-0-1-2-2 works
class 1 : 1 integer
class 0 : 4 integers
class 3 : 4 integers
==> 0-1-3-3-3 works
class 1 : 1 integer
class 0 : 4 integers
class 4 : 4 integers
==> 0-0-0-1-4 works
class 1 : 1 integer
class 2 : 4 integers
class 3 : 4 integers
==> 1-2-2-2-3 works
class 1 : 1 integer
class 2 : 4 integers
class 4 : 4 integers
==> 1-2-4-4-4 works
class 1 : 1 integer
class 3 : 4 integers
class 4 : 4 integers
==> 1-3-3-4-4 works
etc ...
- if 1 of the 3 non-empty class has only 2 integers then we have to consider the cases where the 2 other classes have 3 and 4 integers (in the other cases one of the classes have 5 or more integers)
class 0 : 2 integers
class 1 : 3 integers
class 2 : 4 integers
==> 0-0-1-2-2 works
class 0 : 2 integers
class 1 : 4 integers
class 2 : 3 integers
==> 0-1-1-1-2 works
etc ...
- the last case is : the 3 classes have 3 integers
class 0 : 3 integers
class 1 : 3 integers
class 2 : 3 integers
==> 0-1-1-1-2 works
class 0 : 3 integers
class 1 : 3 integers
class 3 : 3 integers
==> 0-1-3-3-3 works
class 0 : 3 integers
class 1 : 3 integers
class 4 : 3 integers
==> 0-1-1-4-4 works
etc ...
Consider the 2 other cases : 1 class empty and 0 class empty
It is a bit of work ...
There may be a simplest solution
First note that the sum of any five consecutive integers is divisible by 5, and that is because $\displaystyle x+(x+1)+(x+2)+(x+3)+(x+4)=5(x+2)$ .
Note that among the components of the sum there are $\displaystyle 0,1,2,3,4 \equiv \mod 5$. Of course $\displaystyle 0+1+2+3+4\equiv 0 \mod 5$.
Using the pigeonhole principle, among any nine integers there is at least one integer that is equal to $\displaystyle 0,1,2,3$ or $\displaystyle 4 \mod 5$. It's enough to pick those five and there we get a sum divisible by 5.
You may google 'congruence', 'modular arithmetic' for more on that topic.
As you don't know it yet, it might be simpler to put it that way: any integer you choose yields one of four different remainders in division by 5 (0,1,2,3 and 4). If you choose nine integers, then by pigeonhole principle at least one of them gives each of these five remainders in division by 5, so 0-1-2-3-4-2-3-4-4, 0-1-2-3-4-1-2-3-4 (or any combination in which 0-1-2-3-4 is contained). So you need to pick five numbers that each give a different remainder in division by zero, and sum them.