# Rounding error?

Logic Level 3

Consider the following scenario.

A group of $$n$$ friends together gather an amount of money, contributing $$a_1, a_2, \ldots, a_n$$ of the total. Collectively, they manage to buy $$m$$ horses. They now want to distribute these horses according to the money they contribute. Normally, the $$i$$-th person should get $$m a_i$$ horses, but since horses cannot be divided, these numbers need to be rounded. The $$i$$-th person starts by getting $$\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$$ 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$$; that is, the first person contributes twice as much as each of the others. They manage to buy $$m = 5$$ horses. They are now distributed: the first person should get $$m a_1 = 2.5$$ horses, the second and third $$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$$, the second person would get an additional horse (to 2), and with $$m = 7$$, the third person would also get one more (to 2 as well).

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

×