Distribute prizes for a tournament system

Question

I'm looking for a way to distribute a number across x units. I don't even know how to put this words so I'll give an example:

There's a tournament in which the total prize is $1000. I want that the top 20 winners/entrants will win something out of it.
I need a mathematical algorithm/formula which will distibute it across those players, and which gives me the power to control certain other factors of the distribution.

A factor for example is that I want the top #1 winner will get $300. The top #2 winner will get smaller percentage of it. The total distribution must give everyone something, until the top #20 winner (the last one) which will get at least X$.
X$ is another factor I want to control.

Any idea? Does this problem has a name (and what's that name is)? Any code example?

Edit #1 - my first proposal:

#include <conio.h>
#include <vector>

#define TOTAL                       100
#define WINNERS                     15
#define FIRST_WINNER_PERCENTAGE     0.30

void distribute_1(::std::vector<double> * const prizes)
{
    prizes->clear();

    double total = TOTAL;
    double winning_percentage = FIRST_WINNER_PERCENTAGE;
    double slope = 0.5;
    int winners = WINNERS;

    double winning = 0;
    for(int i = 0; i < winners; i++, total -= winning, winning_percentage /= 2)
    {
        winning = total * winning_percentage;
        prizes->push_back(winning);
    }
}
void distribute_2(::std::vector<double> * const prizes)
{
    prizes->clear();

    double total = TOTAL;
    double winning_percentage = FIRST_WINNER_PERCENTAGE;
    double slope = 0.5;
    int winners = WINNERS;

    double winning = 0;
    for(int i = 0; i < winners; i++, total -= winning/*, winning_percentage /= 2*/)
    {
        winning = total * winning_percentage;
        prizes->push_back(winning);
    }
}
void distribute_3(::std::vector<double> * const prizes)
{
    prizes->clear();

    double total = TOTAL;
    double winning_percentage = FIRST_WINNER_PERCENTAGE;
    double slope = 0.0005;
    int winners = WINNERS;

    double winning = 0;
    for(int i = 0; i < winners; i++, total -= winning, winning_percentage -= slope)
    {
        winning = total * winning_percentage;
        prizes->push_back(winning);
    }
}
void distribute_4(::std::vector<double> * const prizes)
{
    prizes->clear();

    double total = TOTAL;
    double winning_percentage = FIRST_WINNER_PERCENTAGE;
    double slope = 1 / WINNERS;
    int winners = WINNERS;

    double winning = 0;
    for(int i = 0; i < winners; i++, total -= winning, winning_percentage -= slope)
    {
        winning = total * winning_percentage;
        prizes->push_back(winning);
    }
}

void main()
{
    ::std::vector<double> prizes;

    distribute_1(&prizes);
    distribute_2(&prizes);
    distribute_3(&prizes);
    distribute_4(&prizes);

    double total_granted = 0;
    for(int i = 0; i < WINNERS; i++)
    {
        total_granted += prizes[i];
        printf("%lf\n", prizes[i]);
    }
    printf("-\n%lf\n", total_granted);

    _getch();
}

This is as far as I could reach. The issue with this one is for example, if that if you set 'WINNERS' to 5 for example, the algorithm doesn't reach the 'TOTAL' amount (100 in this example) or even closer (I get a total of 83).

Cristy's solution:

#include <conio.h>
#include<iostream>
//using arithmetic progression
using namespace std;
int i;
float ratio;
float first_prize;
float s;
int main()
{
    float money=1000;
    const int total_prizes =        10;
    float last_prize =              99;
    float prizes[total_prizes+1];

    /**/first_prize=2*money/total_prizes-last_prize; //last member of the progresion
    ratio=(first_prize-last_prize)/(total_prizes-1);
    prizes[total_prizes]=last_prize;
    for(i=total_prizes-1;i>=1;i--){
       prizes[i]=prizes[i+1]+ratio;
       money-=prizes[i];
    }
    for(i=1;i<=total_prizes;i++){
        printf("%d) %.2f\n",i,prizes[i]);
        s+=prizes[i];
    }
    printf("TOTAL SUM:%.2f\n",s);
    printf("Ratio: %.2f", ratio);
    _getch();
}

Answer 1

I spent a few hours trying to come up with an algorithm that will distribute prizes. Here is my solution based off things I saw on various forums. This code is in Ruby. This has worked great for me.

def self.get_prize_array(money,total_prizes)
    prizes = []  
    p = 0.7 # tweek this for distribution of payout 
    n = total_prizes
    l = money
    (1..total_prizes).each do |r|
       prizes[r-1] = ((1 - p) / (1 - p**n) * p**(r - 1)) * l   # p**n is p to the nth power
    end   
    return prizes
  end 

Answer 2

Formula in first line of Cristy is wrong. first_prize=2*money/total_prizes+last_prize; It should be first_prize=2*money/total_prizes - last_prize;

Here is my solution in python, this will add residual amount to top winners.

starting_amount = (((winnings * 2) / float(no_of_winners)) - last_amount)

difference = (last_amount - starting_amount) / float(no_of_winners - 1)
for rank in range(1, no_of_winners + 1):
    reward = starting_amount + difference * (rank - 1) 
    reward = round_amount(reward)
    winnings -= reward
    winning_amount[rank] = reward

residual_winnings = winnings
residual_shares = {1: 0.5, 2: 0.3, 3: 0.2} 

if no_of_winners < 3: 
    winning_amount[1] += residual_winnings
else:
    for rank in residual_shares:
        reward = residual_winnings * residual_shares[rank]
        reward = round_amount(reward)
        winning_amount[rank] += reward

Answer 3

I had this problem for a pool - I wanted the 3 levels of individual prizes to have the same relative ratio (70%/20%/10%) but recognized the likelyhood of ties, so I had to account for that. I didn't want to just split the pot then award prizes since you might end up with ties for second and an individual second place winner getting less than the third place winner.

P(i) = Size of Prize N(i) = Number of winners

1) Sum (over i) P(i)*N(i) = $1000

2) P(1)/P(2) = 70/20

3) P(2)/P(3) = 20/10

In my case, 3 equations in 3 unknowns - which I solved to get a unique solution.

For your example P(1) = $300. I would just specify successive ratios of prizes and solve the linear system of equations.

Also consider looking here for the distribution of golf prizes at the recent British Open Championship. I'm not saying that the PGA could do a better job than the talent at this website, but it a demonstration of your question in action.

Answer 4

Suppose total money M, you want distribute in n pools such that first person will get k times more than second and second gets k times more than third and so on. Suppose last one get x amount money then

x + k*x + k^2*x ... k^(n-1)*x = M x(k^n-1)/(k-1) = M

Solve for x from this equation based on value of k you choose and distribute money :-)

Answer 5

It's 1:15 AM here and I'm solving maths :)).
Using arithmetic progression.
I made all using defines so you can easily change them.

#include<iostream>
//using arithmetic progression
using namespace std;
FILE *g=fopen("output.out","w");
#define last_prize 10
#define total_prizes 20
int i;
float prizes[total_prizes+1];
float money=1000;
float ratio;
float first_prize;
float s;
//a1=last_prize
//an=first_prize
int main(){
 first_prize=2*money/total_prizes+last_prize; //last member of the progresion
 ratio=(first_prize-last_prize)/(total_prizes-1);
 prizes[total_prizes]=last_prize;
    for(i=total_prizes-1;i>=1;i--)
       prizes[i]=prizes[i+1]+ratio;
 for(i=1;i<=total_prizes;i++){
  fprintf(g,"%d) %.2f\n",i,prizes[i]);
  s+=prizes[i];
 }
 fprintf(g,"TOTAL SUM:%.2f",s);
return 0;
}

OUTPUT:

1) 90.00
2) 85.79
3) 81.58
4) 77.37
5) 73.16
6) 68.95
7) 64.74
8) 60.53
9) 56.32
10) 52.11
11) 47.89
12) 43.68
13) 39.47
14) 35.26
15) 31.05
16) 26.84
17) 22.63
18) 18.42
19) 14.21
20) 10.00
TOTAL SUM:1000.00

As you can see they sum up to exactly 1000.00$ :D

Other results:
INPUT:

#define last_prize 30
#define total_prizes 5

OUTPUT:

1) 370.00
2) 285.00
3) 200.00
4) 115.00
5) 30.00
TOTAL SUM:1000.00

Answer 6

You could make a simple formula like.

#include<iostream>
using namespace std;
FILE *g=fopen("output.out","w");
int i;
int prizes[21];
int money=1000;
int main(){
    for(i=1;i<=20;i++){
       prizes[i]=(float)(15+(20-i))/100*money;
       money-=prizes[i];
    fprintf(g,"%d) %d\n",i,prizes[i]);
      }
return 0;
}

This will output:

1) 340
2) 217
3) 141
4) 93
5) 62
6) 42
7) 29
8) 20
9) 14
10) 10
11) 7
12) 5
13) 4
14) 3
15) 2
16) 2
17) 1
18) 1
19) 1
20) 0

But you can change the values to anything you would like :).
This is just a fast&easy way to do this.

The starting ideea for this algorithm was:
1st prize: 30% from all the money (1000$) = ~330$
2nd prize: 30% from the rest (670$) = ~201
3rd prize: 30% from the rest... etc...
If you replace (15+(20-i)) with 20 let's say, you get this output:
Just change that value to get diffrent results.

1) 200
2) 160
3) 128
4) 102
5) 82
6) 65
7) 52
8) 42
9) 33
10) 27
11) 21
12) 17
13) 14
14) 11
15) 9
16) 7
17) 6
18) 4
19) 4
20) 3

EDIT: And one more thing. After splitting all the money using that algorithms there may still be some money left (because the last one gets x% from the rest). You can add the left-over to the first place...