title: How to maximize the total probability?
body: <p>I want to maximize the total probability of winning in a game of random selection which is played as follows,</p>
  
  <p>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.</p>
  
  <p>If i draw an unlucky ticket master will add k unlucky tickets to the pile of tickets.</p>
  
  <p>We have at max m moves to play, each move is one of the following </p>
  
  <ol>
  <li>Either we draw a ticket</li>
  <li>Either we ask master to remove X tickets (X is multiple of k)</li>
  </ol>
  
  <p>I want to maximize the probability.</p>
  
  <p>And output the total probability P/Q as P*Q^(-1) where Q is modular inverse of Q.</p>
  
  <p>After observing and playing the game I think the total probability will be maximum only when we play the game in the following way</p>
  
  <ol>
  <li><p>First move we draw a ticket and probability of winning is 1/n.</p></li>
  <li><p>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.</p></li>
  <li><p>In third move we again draw ticket and probability of winning now is<br>
  ((n-1)/n)*(1/n) .</p></li>
  </ol>
  
  <p>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</p>
  
  <p>n
  
  <p>for example : 
  n = 3 k = 20 m = 3</p>
  
  <p>total probability is 1-(2/3)^2 = 5/9</p>
  
  <p>n = 5 k = 7 m = 1</p>
  
  <p>total probability of winning is = 1/5 </p>
  
  <p>Final output : </p>
  
  <p>5*(9)^(-1) % 1000000007 = 555555560</p>
  
  <p>1*(5)^(-1) % 1000000007 = 400000003  </p>
  
  <p>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.</p>
  
  <p>we again put the ticket that we picked in the pile again so after drawing wrong we have n+k instead of n+k-1, and also n &lt; k ( for the starting always)</p>
  
  <p>EDIT :  Proof of my strategy  </p>
  
  <p>for each move we take there are 2 possibilities </p>
  
  <p><strong>either we gain 1/n*(n-1)/n or we gain (n-1)/n*(1/n+k) + (n-1/n)<em>((n+k-1)/n+k)</em>(1/n+2*k)</strong> </p>
  
  <p>now after solving both sides we get to equation 1/n left hand side and right hand side is (2*n+3*k-1)/((n+2*k)*(n+k) and i found that R.H.S is always less than or equals to R.H.S </p>
  
  <p>So after further solving i get L.H.S as 2*(k^2) and R.H.S as n^2-n and as given n &lt; k so L.H.S is always greater than R.H.s</p>
  
  <p>Hence proved.</p>
  
  <p>Please provide feedback for the proof.</p>