Prove that for any set of one hundred whole numbers, either one of those numbers is divisible by 100 or the sum of a subset of those numbers is divisible by 100.


Solution

Let the one hundred whole numbers be x1, x2, … , x100, and consider the subsets{x1}, {x1, x2}, … , {x1, x2, … , x100}.

Let’s take the sums of each subset, divide them by 100, and consider the remainders. If one of these remainders is zero, then the sum of that subset is divisible by 100 and the original condition is satisfied.

So if none of the remainders are zero, that means there are one hundred subsets and only ninety-nine possible remainders (1–99). By the Pigeonhole Principle, two of these sums must have the same remainder. Let’s say these subsets are {x1, x2, … , xa} and {x1, x2, … , xa, … , xb}.

The difference between these two subsets can be written as {xa+1, xa+2, … , xb}, which is yet another subset of the original one hundred numbers. Since these subsets have the same remainder when divided by 100, then the difference between these subsets would have a remainder of 0 when divided by 100. This means this difference is a subset with a sum that is divisible by 100, which fulfills the original condition.

Leave a Reply

Your email address will not be published. Required fields are marked *