Payoff of drawing card You have 100 cards with face value 1-100, randomly shuffled in a bag. Your payoff is the face value (in dollar) of the last card you draw. You can draw as many time as you want (with replacement), but each time you draw, it costs 1 dollar. What would be the best strategy to play this game? Does this game has a analytical solution?
 A: Clearly you should draw the first card, as your expected profit is $49.5$.  After the first card, your strategy is to quit whenever you draw a card higher than $n$ and draw on $n$ or less.  The question is what $n$ should be.  Clearly it should be at least $49$.  
Having chosen $n$, your average accepted card is $\frac {101+n}2$.  The chance of drawing an acceptable card is $\frac {100-n}{100}$.  The expected number of cards you will draw is 
$1\left(\frac {100-n}{100}\right) +2\left(\frac {100-n}{100}\right)\left( \frac n{100}\right)+3\left(\frac {100-n}{100}\right)\left( \frac n{100}\right)^2+4\left(\frac {100-n}{100}\right)\left( \frac n{100}\right)^3+\ldots=\left(\frac {100-n}{100}\right) \left(1+\sum_{k=1}^\infty (k+1)\left(\frac k{100}\right)^k \right)=\left(\frac {100-n}{100}\right) \left( \frac 1{(1-\frac n{100})^2}\right)$ 
Our expected profit if we draw is then $$\frac {101+n}2-\left(\frac {100-n}{100}\right) \left( \frac 1{(1-\frac n{100})^2}\right)=\frac {101+n}2-\frac {100}{100-n}$$  
Searching for the maximum finds it at $n=100-10\sqrt {2}\approx 85.8579$  As we must have $n$ an integer, we try $85$ and $86$, finding the maximum at $n=86$ with value $\frac {1209}{14} \approx 86.357$.  You should draw any time your card is $86$ or less.  As a sanity check, your average accepted card will be $93.5$ and it should take about $\frac {100}{14} \approx 7.14$ draws to get one, so the profit is reasonable.  
An easier approach is to define $G(n)$ as the gain at $n$ andlook for the $n$ were $G(n+1)-G(n)$ turns negative.  This is $$G(n+1)-G(n)=\frac 12-\frac {100}{99-n}+\frac {100}{100-n}$$ which turns negative at about $n=85.349$, so we should increment from $n=85$ to $n=86$ but not further.  
A: Denote by $\xi$ the expected gain per game under optimal strategy. Then $\xi$ is a solution of the equation
$$x=\sum_{k=1}^{100}{1\over 100}\>\max\{k,x\}\ -1\ ,\tag{1}$$
because one will reject the first drawn number $k$ if continuing to draw seems more promising, and will accept $k$ otherwise. The function
$$f(x):=\sum_{k=1}^{100}{1\over 100}\>\max\{k,x\}\ -1$$
is increasing, continuous, and has derivative $f'(x)=\lfloor x\rfloor/100<1$ for noninteger $x$. Furthermore $f(0)=49.5>0$ and $f(100)=99<100$. It follows that $(1)$ has exactly one solution $\xi\in\>]0,100[\>$. Plotting $f$ shows that in fact $86<\xi<87$. We therefore write $\xi=86+\tau$ with $0<\tau<1$, and solve
$$86+\tau=\sum_{k=1}^{86}{86+\tau\over 100}+\sum_{k=87}^{100}{k\over 100}\ -1$$
for $\tau$. The result is $\tau={5\over14}$, so that $\xi=86.3571$.
The optimal strategy therefore turns out to be the following: Keep drawing until you get a number $\geq87$. The expected gain per game then is $86{5\over14}$.
A: here's what my simulation got

https://dotnetfiddle.net/lie2h4
quit on 87 yields expected £86.532
quit on 85 yields expected £86.3432
quit on 86 yields expected £86.2902
quit on 88 yields expected £86.2602
quit on 89 yields expected £86.2053
quit on 84 yields expected £86.0106
quit on 83 yields expected £85.9269
quit on 90 yields expected £85.7383
quit on 82 yields expected £85.6761
quit on 91 yields expected £85.6596
quit on 81 yields expected £85.6201
quit on 80 yields expected £85.1205
quit on 79 yields expected £85.0571
quit on 92 yields expected £85.0558
.....
quit on 4 yields expected £51.0134
quit on 3 yields expected £50.1926
quit on 2 yields expected £50.1084
quit on 99 yields expected £49.7115
quit on 1 yields expected £49.6166
quit on 100 yields expected £1.1244
