1
$\begingroup$

I have some sort of a math issue : I have to implement an algorithm that randomly generates winners and losers based on :

  • a maximum number of players
  • a percentage of winners to reach

Of course, the more winners, the smaller the effective percentage will be, but in the end, when the total number of players reach the maximum number that was set, the exact percentage of winners must be reached too.

In other words, if I set the maximum number of players to 500 and the percentage to 10%, I have to reach exactly 50 winners (no less, no more) by the time I reach 500 players. I tried to do some math, but I'm not really good at it, so I'm looking for your help ;)

EDIT : here's another try to explain my problem since it seems that I'm confusing people :D :D

It's a game on iPad where people come and play. An admin first sets the maximum number of users and the percentage of winners he'd like.

Then, people come and play, one at a time, and when they do, they are notified instantly if they won or not. By the time the game reaches the maximum number of players that was initially set, I must have the correct percentage of winners based on what was initially set. I hope this description is more clear ;)

Thanks a lot for your help.

  • 0
    is this homework?2012-02-27
  • 0
    Do you just want to pick a random subset of some fixed size from a big pool of candidates? Eg, you have 10 numbers (== players), and you want to pick 3 (== winners) of them?2012-02-27
  • 0
    rrenaud --> OK I got it! Definitely no. Players will play this game and for each, I have to tell if he won or not. And eventually, I must have the exact number of winners by the time I reach the max number of players.2012-02-27
  • 1
    I still don't have any idea what you're trying to do.. "by the time I reach 500 players" "played this game".. what's this game? what makes somebody a winner? are they playing against each other? everyting you wrote is very confusing... please give sample input and output for your app2012-02-27
  • 0
    I think this is a streaming sampling problem. He sees players one at a time, and he needs to decide if a given player will be a winner or not at that instant, and he needs to guarantee that at the end of the sampling process, he has generated enough winners.2012-02-27
  • 0
    @rrenaud: could be, but then it really sounds like homework...2012-02-27
  • 0
    This is impossible for an arbitrary N. Forget random, let's just say 10% of the entrants win, and we have every 10th person win. For the first 9 players, no one wins, and the probability of a winner is 0%. When the 10th player plays, he wins, and the effective probability is now 10%. And so on, with the effective probability less than 10%, except when the number of players is divisible by 10. Even government lotteries don't guarantee their percentages in this manner.2012-02-27
  • 0
    @rrenaud --> exactly, you got it right2012-02-27
  • 0
    I'm sorry to add another answer rather than a comment, but I still can't comment existing posts (not enough reputation I assume). I just wanted to thank all of you guys for helping me out ;) And doesn't it work like StackOverflow? I can't set an answer as "accepted" to tell people that the answer helped me a lot? Thx.2012-02-28
  • 0
    @Khal: the question has since then been merged into your account. Now you should be able to comment on this question and/or mark an answer as accepted.2012-05-24

2 Answers 2