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?

×

Problem Loading...

Note Loading...

Set Loading...