Thread: Integer proof

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

WOW! That looks complicated - is there any simpler, neater solution, by any chance?

You should be able to reduce your problem to the following: Given 9 elements of it is always possible to select 5 which sum to 0.

Could you please explain that in simpler terms?

First note that the sum of any five consecutive integers is divisible by 5, and that is because .
Note that among the components of the sum there are . Of course .
Using the pigeonhole principle, among any nine integers there is at least one integer that is equal to or . It's enough to pick those five and there we get a sum divisible by 5.

Could you please explain to me what this triple equals sign means, and also what this 'mod' means?

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.

Would there, by any chance, be any other simpler way of doing this?

Really, once you put your fingers on the topic of congruence, this is the simplest way.