Optimal bet given a repeated coin flip game A brainteaser question obtained from here states:

Flip 10000 fair coins. You are offered a 1-1 bet that the sum is less than 5000. You can bet 1, 2, ..., 100
  dollars. How much will you bet. How much will you bet if someone tells you that the sum of the coins is
  less than 5100?

I believe that maximizing the expected value would give you 100 for the first situation because there are 5001 win cases and 5000 loss cases, and betting 1 (the minimum) in the second case because now the probability of losing is greater than 0.5.
However the question of "how much will you bet" is ambiguous to me. Is expected value the right metric for betting? Are there other reasonable metrics to consider before making a bet?
 A: Let's think about the problem with fewer coins, say 10. It is the same problem as if you had 1 fair coin with 10 flips. For 10 coins with 2 sides each there are $2^{10}$ possible outcomes. The number of ways to get exactly 4 heads from 10 is the binomial coefficient, 10C4 = 210. Dividing 210 by 1024, we get 20.5%. Now what's the probability that there are less than 5 heads? Sum up the binomial coefficients for $n < 5$ and divide by all potential outcomes, 210. That gives us 37.7%.
Now we can introduce the notion of expected value. You have a probability of 0.377 of the number of heads being less than 5, for 10 flips. That means there is a (1-0.377) probability of there being 5 or more heads. How much can you expect to make from betting $X$ dollars that there are less than 5 heads? That is simply the sum of the dollar amount associated with each of your probabilities. You've got X for 0.377, and you've got $-X$ for (1-0.377). The expected value is then $0.377X-X+0.377X=-0.246X$.
Whatever $X$ you have, you should expect to lose 24.6% of it!
Using Wolfram Alpha to solve the problem for 10000 coins and less than 5000 heads, you've got a probability of 0.496 of getting your money back. That means on average, you can expect to lose 0.8% of your money X.
For less than 5100 you get a probability of 0.977. That means your expected value is 0.954 and thus you should expect to get your money back plus 95.4% of it. An extra 100 heads of cushion makes this a slam dunk bet, despite intuition.
The correct number to bet depends on your risk tolerance and basically gives insight to your interpretation of risk-reward, given the probability of each outcome. The Kelly Criterion mentioned above could be a useful rule of thumb. Using that, we get 0.977*2-1=95.4% of capital.
Now moving on to the second question: how much will you bet if you are given the information that the sum of the coins is definitely less than 5100. That is a Bayesian conditional probability problem.
You're basically gaining a measurement, and that will affect your probabilities. The formula is given as:
$$
{\rm P}(A | B) = \frac{{\rm P}(B|A){\rm P}(A)}{{\rm P}(B)}.
$$
The formula is actually pretty easy to calculate for this situation. Event A is the probability of getting less than 5000 heads. Event B is the probability of getting less than 5100 heads. The bar means given. So the probaility of A given B is the probability of B given A times ${\rm P}(A)/{\rm P}(B)$. What is the probability of B given A? Well, if it's given that it is less than 5000, then it's certainly less than 5100! So ${\rm P}(B|A) = 1$. Plug in the two values we calculated above: ${\rm P}(A)=0.496$ and ${\rm P}(B)=0.977$. That means ${\rm P}(A|B)=0.508$. So that bit of extra knowledge gives you an edge in the game. If you are doing it a million times, then you can expect a positive return, no matter how much you put up.
