Suppose that you have a multiset of rational numbers. All of these rational numbers have as their denominators. Brilli the Ant claims that it is always possible to find a non-empty sub-multiset of such that the sum of the elements of that multiset is an integer. Is she right?
Details and assumptions:
I tried to frame this problem so that it would have a numerical answer but I failed. That's why this is a multiple choice question
A multiset is like a set but it can have elements that can appear more than once. is an example of a multiset. is a sub-multiset of .
The sum of one number is the number itself.
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.
Consider only the numerators, since the denominators are all equal to 1000. For the sum of the elements of a sub-multiset to be an integer, the sum of the numerators must be ≡ 0 ( m o d 1 0 0 0 ) .
Now, consider S 1 , S 2 , S 3 … S 1 0 0 0 where S i denotes the sum of the numerators of the first i elements of A. If one of them is divisible by 1000, we are done, or else, their remainders modulo 1000 must be from the set [ 1 , 2 , 3 , … 9 9 7 , 9 9 8 , 9 9 9 ] .
Since there are 999 possible remainders and 1000 S i 's, by PHP, the remainders of two S i 's must be the same. Let them be S j and S k .
Therefore S j − S k ≡ 0 ( m o d 1 0 0 0 ) . Or, alternatively, we can say that the set [ j + 1 , j + 2 … k − 1 , k ] satisfies the condition