Ends in 00

What is the minimum number N N that satisfy the following properties?

Out of any set of N N integers, there are 2 of them whose sum or difference is a multiple of 100.


The answer is 52.

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.

1 solution

Shaun Leong
Oct 24, 2016

Let the property P P be the property that a set has a pair with sum or difference which is a multiple of 100 100 .

Consider any set of elements mod 100 100 ; note that whether any set has the desired property will remain unchanged when we take all elements mod 100 100 .

For a set without P P , then for any element r r there cannot be another element equal to r r or 100 r 100-r . Hence there are no repeats.

Firstly, for any n 51 n \leq 51 the set { 0 , 1 , 2 , 3 , 4 , , n 1 } \{0,1,2,3,4,\ldots, n-1\} does not satisfy P P .

For n = 52 n = 52 , if we assume there is a set without property P P , then we split { 0 , 1 , 2 , 3 , 4 , , 99 } \{0,1,2,3,4,\ldots,99\} into 51 51 sets of { 0 } , { 1 , 99 } , { r , 100 r } , , { 49 , 51 } , { 50 } \{0\}, \{1,99\}, \ldots \{r,100-r\}, \ldots, \{49,51\}, \{50\} .

By the pigeonhole principle, if we choose 52 52 elements, there must exist 2 2 elements which belong to the same pair even if there are no repeats. These 2 2 elements make the set have property P P , hence we have proven that all 52 52 element sets have property P P .

That's the Pigeonhole that I used too. I like that the holes are not "similar" to each other, which is often the case in such problems.

Chung Kevin - 4 years, 7 months ago

Log in to reply

I'm a fan of "different pigeonholes" too. It allows you to show off your creativity.

Calvin Lin Staff - 4 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...