What is the minimum number that satisfy the following properties?
Out of any set of integers, there are 2 of them whose sum or difference is a multiple of 100.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let the property P be the property that a set has a pair with sum or difference which is a multiple of 1 0 0 .
Consider any set of elements mod 1 0 0 ; note that whether any set has the desired property will remain unchanged when we take all elements mod 1 0 0 .
For a set without P , then for any element r there cannot be another element equal to r or 1 0 0 − r . Hence there are no repeats.
Firstly, for any n ≤ 5 1 the set { 0 , 1 , 2 , 3 , 4 , … , n − 1 } does not satisfy P .
For n = 5 2 , if we assume there is a set without property P , then we split { 0 , 1 , 2 , 3 , 4 , … , 9 9 } into 5 1 sets of { 0 } , { 1 , 9 9 } , … { r , 1 0 0 − r } , … , { 4 9 , 5 1 } , { 5 0 } .
By the pigeonhole principle, if we choose 5 2 elements, there must exist 2 elements which belong to the same pair even if there are no repeats. These 2 elements make the set have property P , hence we have proven that all 5 2 element sets have property P .