<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Sat, Nov 21, 2015 at 10:06 PM, spike <span dir="ltr"><<a href="mailto:spike66@att.net" target="_blank">spike66@att.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div link="blue" vlink="purple" lang="EN-US"><div><p class="MsoNormal"><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)"> </span><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)"></span>I will be damned if I can prove this is the optimal bid but the gradient seems to zero out at that point.  Anders?  Adrian?</p><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)"></span><div><p class="MsoNormal"><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)"> </span></p></div></div></div></blockquote></div><br></div><div class="gmail_extra">Easy.  Even if we allow fractions, the problem stated that there's actual cash in US dollars, and there are no half-cents in physical US currency as of today, so there's an even probability of anywhere from 0 to 1 billion pennies.  We want the number that gives the highest total payout for each value, and that's a trivial matter of evaluating candidate values against each of 500,000,001 possibilities (we can eliminate bids over $5,000,000 because we know that either we'd guess too high and get nothing, or we wouldn't but we'd get less than if we bid $5,000,000).  There are of course several optimizations that can be taken to reduce run time; for instance, for each bid X (in pennies), you know already that each possible sum Y < X will get 0.<br><br>We can also simply sum up the possible gains to us.  For bid X, the probability N that we get nothing, i.e. that X >= Y, is (X+1) / 1,000,000,001.  The probability H of a too-high bid, i.e. that X >= Y/2, is ((2*X)+1) / 1,000,000,001.  With probability 1-H we get X, with probability H-N we get Y-X (and for each X in this case, the possible Ys are evenly distributed from X to 2*X, so the average Y is X + (X/2), meaning the average payout in this case is (X + (X/2)) - X = X/2), and with probability N we get 0.  So we need to select X to maximize ((1-H) * X) + ((H-N) * (X/2)) + (N * 0).  Reducing this equation in steps:<br><br>((1-(((2*X)+1) / 1,000,000,001)) * X) + (((((2*X)+1) / 1,000,000,001)-((X+1) / 1,000,000,001)) * (X/2)) + 0<br><br>(((1,000,000,000-(2*X)) / 1,000,000,001) * X) + ((X / 1,000,000,001) * (X/2))<br><br>X * ((1,000,000,000-(2*X)) + (X/2)) / 1,000,000,001<br><br></div><div class="gmail_extra">And this is something that can simply be computed.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Now, we can also do heuristic look-aheads so we don't have to evaluate the whole set.  As you noted, it seems highly unlikely that X < 250,000,000 is the value, and indeed evaluating it around there shows an increasing slope.  The function does not seem to allow for discontinuities or anything other than a simple curve, so a local maximum (so long as it is not at the edge of a section evaluated) should be the global maximum.<br><br></div><div class="gmail_extra">When I run it, I get a maximum of 333333333 pennies ($3,333,333.33) with an average expected payout of 166666666.5 pennies ($1,666,666.665).  Check your floating point buffers if you run the calculation, because the difference between the payouts for 333333333 and 33333334 is quite small, but 333333333 is higher (likely because it is closer to what would be the maximum if fractional pennies were allowed: 333333333.333...).<br><br>Note that this is evaluating for maximum payout to us, and we don't care what the other guy gets.  If the other guy getting as much as or more than us is a significant problem, the answer may be some variant on, "arrange for the vault to be burned to the ground unopened and make it look like an accident".<br><br></div><div class="gmail_extra">As to the other problem (the "Anders branch"), it is in fact technically bounded too: <a href="http://www.federalreserve.gov/faqs/currency_12773.htm">http://www.federalreserve.gov/faqs/currency_12773.htm</a> shows there is less than $1.4 trillion out there, so this serves as an upper bound of how much currency the vault could contain.  (It was stipulated that the vault contains dollars - as in, only US cash.)  But that aside, I'd bid $10 million: if it's less than $20 million, the other side isn't waving all that much in my face, while if it's more, I suspect I could bootstrap $10 million much faster than most extant bad guys could usefully exploit $10 billion or even $10 trillion.<br></div></div>