I want to maximize the total probability of winning in a game of random selection which is played as follows,
I have n lottery tickets and out of these n only 1 is the lucky ticket, now I have 2 option either draw a ticket or ask the master to remove some X unlucky ticket out of total tickets, X must be a multiple of k (available) and X must be smaller than total number of tickets.
If i draw an unlucky ticket master will add k unlucky tickets to the pile of tickets.
We have at max m moves to play, each move is one of the following
- Either we draw a ticket
- Either we ask master to remove X tickets (X is multiple of k)
I want to maximize the probability.
And output the total probability P/Q as P*Q^(-1) where Q is modular inverse of Q.
After observing and playing the game I think the total probability will be maximum only when we play the game in the following way
-
First move we draw a ticket and probability of winning is 1/n.
-
If we draw an unlucky ticket in first move k tickets are added and we can ask the master to remove k tickets in second move.
-
In third move we again draw ticket and probability of winning now is
((n-1)/n)*(1/n) .
Similarly if there are m moves than we can conclude that, total probability of winning is (1-((n-1)/n)^r) where we can find value of r
for example : n = 3 k = 20 m = 3
total probability is 1-(2/3)^2 = 5/9
n = 5 k = 7 m = 1
total probability of winning is = 1/5
Final output :
5*(9)^(-1) % 1000000007 = 555555560
1*(5)^(-1) % 1000000007 = 400000003
If there is other winning strategy in this game please provide it with proof and i don't have a proof for my strategy too so if you can prove my strategy i will be glad to have it as well as a psuedocode will help me to proceed.
Aucun commentaire:
Enregistrer un commentaire