Rounding error?

Logic Level 3

Consider the following scenario.

A group of n n friends together gather an amount of money, contributing a 1 , a 2 , , a n a_1, a_2, \ldots, a_n of the total. Collectively, they manage to buy m m horses. They now want to distribute these horses according to the money they contribute. Normally, the i i -th person should get m a i m a_i horses, but since horses cannot be divided, these numbers need to be rounded. The i i -th person starts by getting m a i \lfloor m a_i \rfloor horses. At the end, some horses will remain; these will be given in order to the people with the highest fractional part of m a i m a_i until none is left. (In case of a tie, begin with the person with the lowest index.)

For example, consider a 1 = 0.5 , a 2 = 0.25 , a 3 = 0.25 a_1 = 0.5, a_2 = 0.25, a_3 = 0.25 ; that is, the first person contributes twice as much as each of the others. They manage to buy m = 5 m = 5 horses. They are now distributed: the first person should get m a 1 = 2.5 m a_1 = 2.5 horses, the second and third m a 2 = m a 3 = 1.25 m a_2 = m a_3 = 1.25 . We first ignore the fractions, so the first person gets 2, and the other two 1 each. Now, the highest fractional part comes from the first person, so the first person gets an additional horse; that's 3 for the first person and 1 for the other two.

With m = 6 m = 6 , the second person would get an additional horse (to 2), and with m = 7 m = 7 , the third person would also get one more (to 2 as well).

The above example shows that increasing m m wouldn't make someone to get less horses. Is this true? That is, for any fixed a 1 , , a n a_1, \ldots, a_n , is it true that if we raise m m , nobody will lose horses?

True False

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

Ivan Koswara
Jan 11, 2016

The answer is false; it's possible that adding more horses causes people to lose them. This is known as the Alabama paradox . One example is with a 1 = a 2 = 3 7 , a 3 = 1 7 a_1 = a_2 = \frac{3}{7}, a_3 = \frac{1}{7} ; with m = 10 m = 10 , the distribution is 4 , 4 , 2 4, 4, 2 , but with m = 11 m = 11 , the distribution is 5 , 5 , 1 5, 5, 1 . Adding more horses gives less horses to the third person.

Moderator note:

As an explanation of why this results, the additional horse will make those with a high fractional part { m a i } \{ma_i\} , more likely to get an nth horse. This happens when ( m + 1 ) a i n > m a i (m+1) a_i \geq n > ma_i . If it happens twice, then since we only had one additional horse, it means that someone else will have received fewer horses.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...