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 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 2

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...

Answer 3

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 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 :-)