IBM Research | Ponder This | January 2009 solutions

# Ponder This

## January 2009

<<December January February>>

The answer to the first part is

1-sqrt(2*c) for c < .5
0 for .5 < c

This can be seen as follows. Clearly the best strategy will be to keep buying tickets until you obtain one greater than some threshold x and then to stop (or for large c to buy no tickets at all). You can expect to buy 1/(1-x) tickets on average each at a cost of c. The expected value of the final ticket will be (1+x)/2. Hence your expected winnings are .5*(1+x)-c/(1-x). So we must find the threshold x which maximizes this. Setting the derivative to 0 we obtain .5-c/((1-x)**2)=0 or (1-x)**2 = 2*c or 1-x = sqrt(2*c) or x=1-sqrt(2*c). Substituting, the expected winnings are then 1-.5*sqrt(2*c)-c/sqrt(2*c) = 1-.5*sqrt(2*c)-.5*sqrt(2*c) = 1-sqrt(2*c). For c>.5 these values are less than 0 which means you shouldn't buy any tickets.

The answer to the second part is the same. This is because if it is correct to buy an additional ticket it will be correct to keep on buying additional tickets until you get one which is better than the best one that you already hold. Thus when you are allowed to buy an unlimited number of tickets it will never be best to cash an earlier ticket. Note this is not the case when there is a limit on how many tickets you can buy.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com