Split by percentage

Question

I need to give $n$ apples to three persons $A$, $B$ and $C$.

$A$ should get $50\%$, $B$ should get $30\%$, and $C$ should get $20\%$ of however much ever I give.

For example, if I have given $10$ apples, $A$ should have $5$, $B$ should have $3$, and $C$ should have $2$.

Apple   A   B   C
1st     1       
2nd         1   
3rd     1       
4th         1   
5th     1       
6th             1
7th     1       
8th         1   
9th     1       
10th            1

What would be the formula to split $n^{th}$ apple by percentage?

Answer 1

It looks like you want to give the $n^{\text{th}}$ apple to whoever is due most of it. You look at then number you have given out, the number each has received of the first $n-1$, the exact number they are due out of $n$ and give it to whoever it gets closest. In your example, however, it seems the fourth apple should go to $C$. $A$ should have two of the first four, and does. $B$ should have $1.2$ and has $1$. $C$ should have $0.8$ and has none. So I would think you give $A \ \ 1,3,5,7,9;B\ \ 2,6,10;C\ \ 4,8$

The procedure I am following is as follows. Let $a$ be the fraction due $A$, $b$ the fraction due $B$ and $c$ the fraction due $C$. Let $aa(i)$ be the number of apples that $A$ has out of the first $i$, similar for $bb(i), cc(i)$. To give out apple $n$, we would want $A$ to have $an$, $B$ to have $bn$, and $C$ to have $cn$. Calculate $an-aa(n-1), bn-bb(n-1), cn-cc(n-1)$ and award the $n^{\text{th}}$ apple to whoever has the greatest value. In your example the pattern will repeat every $10$ apples.

Example: $A$ gets $0.47$, $B$ get $0.31$, $C$ gets $0.22$ The second to fourth columns give the number each person is due out of $n$ apples. The next three give how many they got out of the first $n-1$. The nth apple is awarded to whoever is most short. $$\begin {array} { r|r|r|r|r|r|r|c}n&A&B&C&aa&bb&cc&\text{apple to} \\ \hline 1&.47&.31&.22&0&0&0&A\\ 2&.94&.62&.44&1&0&0&B\\3&1.41&.93&.66&1&1&0&C\\4&1.88&1.24&.88&1&1&1&A\\5&2.35&1.55&1.10&2&1&1&B\\6&2.82&1.88&1.32&2&2&1&A\\ 7&3.29&2.17&1.54&3&2&1&C\\8&3.76&2.48&1.76&3&2&2&A\\9&4.23&2.79&1.98&4&2&2&B\end{array} $$ If you are presented with a pile of apples, you can give each person the integer part of what they are due, then deal with the ones left. So here, if you got eight apples at once, you would give $3$ to $A$, $2$ to $B$, $1$ to $C$ and then run this calculation for the last two.

Answer 2

Here's a greedy algorithm that should work. Ross seems to have a similar idea. Here's some pseudocode:

initalize:  n = 0 (total number of apples so far)
            a = 0 (number of apples A has)
            b = 0 (number of apples B has)
            c = 0 (number of apples C has)

repeat until n == total number of apples
    a' = 0.5(n+1) - (a+1)
    b' = 0.3(n+1) - (b+1)
    c' = 0.2(n+1) - (c+1)
    list = [a',b',c']
    sort list
    if a' is the greatest
        a = a+1
    if b' is the greatest
        b = b+1
    if c' is the greatest
        c = c+1
    n = n+1
end repeat