This is a Multiple Choice Question :(

Suppose that you have a multiset A A of 1000 1000 rational numbers. All of these rational numbers have 1000 1000 as their denominators. Brilli the Ant claims that it is always possible to find a non-empty sub-multiset of A A 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. { 1 , 3 , 3 } \{1,3, 3\} is an example of a multiset. { 3 , 3 } \{3, 3\} is a sub-multiset of { 1 , 3 , 3 } \{1,3,3\} .

The sum of one number is the number itself.

Yes, she is! She's wrong! It's impossible to find such a subset. This is a dummy answer. Don't click on this! She can't claim that! There's not enough information.

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.

2 solutions

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 1000 ) \equiv 0 \pmod{1000} .

Now, consider S 1 , S 2 , S 3 S 1000 S_1, S_2, S_3 \ldots S_{1000} where S i 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 , 997 , 998 , 999 ] [1,2,3, \ldots 997,998,999] .

Since there are 999 possible remainders and 1000 S i S_i 's, by PHP, the remainders of two S i S_i 's must be the same. Let them be S j S_j and S k S_k .

Therefore S j S k 0 ( m o d 1000 ) S_j -S_k \equiv 0 \pmod{1000} . Or, alternatively, we can say that the set [ j + 1 , j + 2 k 1 , k ] [j+1,j+2 \dots k-1,k] satisfies the condition

Brilli the Ant? .................... it's a good one!

Maharnab Mitra - 7 years, 3 months ago

I thought that it is said in the question that any sub-multiset of A fulfills the criteria...my bad.

Prasun Biswas - 7 years, 3 months ago

"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?" this wording is really wrong

David Christopher - 7 years, 3 months ago

Cool, that's what I did

Robert Fritz - 7 years, 3 months ago
Jai Banthia
Mar 15, 2014

It's simple really. The numerators must be all rational numbers , and it is always possible to get an integer out of rational numbers [even fractions] by multiplying [multi sub set] and adding. For example 3.1416 repeated 10,000 times gives us 31416 , an integer.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...