bonanova

I don't know of a strategy to win coin tosses. I would expect to go broke or double my money with equal likelihood. Even so, here's what I would probably do:

I never was never able to figure Keno odds, but after placing a few $1 bets in Vegas a few years back I vowed to stay away. My intuition was the payoff was ridiculously low. I since have seen that was a wise move on my part. In case you've never done the calculation, I'll offer you the option of four different games and ask you to determine the expected return. There are 80 numbers, from which you pick from 1 to 4, and from which the casino picks 20, at random. Your winnings depend on the number of "matches" between your numbers and the casino's. In each case you bet $1, which the house keeps. Your winnings are as follows: You pick 1 number. If it matches one of the 20 picked by the casino, you are paid $3. You pick 2 numbers. If they both are matches (with the casino's 20 numbers) you are paid $12. There is no payoff in only one of your numbers is a match. You pick 3 numbers. If all three are matches you are paid $42. If exactly two are matches you are paid $1, breaking even. You pick 4 numbers. If all four are matches you are paid $120. If exactly three are matches you are paid $3. If exactly two are matches you are paid $1, breaking even.If you play ten $1 games of your choosing, what is your best expected return?

;-) animated gif not needed.

First thoughts are that it depends on the odds of the bet.

What does "exactly between" mean?

Count your example as one of the "solutions."

How many solutions exist for xy = yx? xy=yx

Perhaps sailing around, as well? Nice puzzle!

I think I know. I just have to figure it out. (I'm stuck on Pietro.)

@kman, I have argued this analysis in another venue, and my doubter objects to the proof. He accepts that 1/n is the probability that initially the first bullet is fastest, but not subsequently. He asks for proof that the first collision does not alter the statistical properties of the surviving bullets -- he says that 1/(n-2) cannot simply be assumed for the first remaining bullet to be the fastest of the remaining bullets. I pulled my hair out trying to disabuse him of that doubt. The best argument I could give is that the first collision is random (in the sense that it is governed by random placement and speed of the original bullets), and that random processes do not introduce bias. He asks for a stronger argument. I don't think there is one. And I don't think there needs to be one. It's self-evident. That is his only objection, btw. And it's the only possible objection, because it's a sufficient condition for the proof, as your diagram eloquently shows. Total annihilation happens according to the product of (k-1)/k terms, with k decreasing from n to 2 in steps of 2. One aspect of the analysis that led to confusion in our discussion is the meaning of these terms. At each step, (k-1)/k is *not* the probability of a next collision. It is a lower bound. Thus, while the formula seems intuitive, its partial products do not have their intuitive meaning. But that is a red herring. Only the complete expression has been offered as being meaningful. For example, in the case of n=4, the probability for at least one collision is not 3/4, it's 23/24. Accordingly, the probability for a second collision is not 1/2, it's 9/23. The annihilation probability for n=4 is thus 23/24 x 9/23 = 9/24 = 3/8. These factors have a clear interpretation, whereas 3/4 and 1/2 do not. It is tempting to think of 3/4 and 1/2 as sequential probabilities, but it is incorrect to do so. Except that, *given that k has become 2,* 1/2 is the probability for the last collision. But the priors are modified in that line of thinking. Also, for that last case, 1/n just happens to equal 1/n!. It would be interesting for someone who has a simulation program running (bubbled seems to have departed the scene) to start say with say n=20 and record the fraction of cases that get to each value of k (18, 16, ... ) remaining bullets, down to k=2. (By "get to" I do not mean "terminate with.") The ratios of those numbers give the probabilities of a next collision. The formula in question gives the correct number for which k gets to 0. But the intermediate results will be seen (I posit) to differ from the partial products of the formula. In only 1/n! of the cases will k not get to 18, for example. The complete formula applies to total annihilation. I don't see a simple interpretation for its partial products.

@harey, I agree that we are analyzing a string of n bullets that still exist after the nth bullet has been shot. I would say let's not worry about that -- I could even change the OP to reflect it. The other case just seems messy and not interesting enough (to me at least) to pursue. However ... I have some uncertainty about the derivation after giving this some thought. I'm not sure we are comparing apples to apples. Let me explain. Suppose the leading bullet has 1/k chance of being the fastest. Then we will not get complete annihilation. But *still* we could get another collision, between other bullets. So while it may seem true to say the probability of *at least* one future collision is 1-1/k, we are still measuring only a *sufficient* but not a *necessary* one. Meaning that (k-1)/k is a *lower bound* to the probability of future collisions, not that probability itself. Multiplying lower bounds may not be a justifiable path to determining a final annihilation probability. Think of it this way. For an initial ensemble of n bullets, there are n! permutations of their speeds, only one of which (monotonic speed profile, increasing back to front) does *not* have a collision in its future. So the initial probability for at least one collision is not (n-1)/n, but (n!-1)/(n!). For any appreciable n, say 10 or greater, that probability is *very* close to unity, not the mere 9/10 that obtains from cases where the leading bullet is not the fastest. So the meaning of 9/10 in that context seems unclear. Certainly (n-1)/n underestimates the true probability at the outset, while near the "finish line" where k=4 and k=2, it must over-estimate it. While the product of (k-1)/k terms gives the correct result (as verified by simulation, and perhaps amazingly), the individual terms don't have a clear meaning; at least they don't have the meaning that the derivation ascribes to them. It may well be the case that as k decreases, 1/k remains the escape probability for the leading bullet; even so, it's clear that most of the (k-1)/k terms underestimate the next-collision probability. I'm re-opening this thread. Perhaps more discussion will fill in the question marks. I'm open to reconsidering. I wish someone would simulate n=100 several times and compare the next-collision probabilities for each k against (k-1)/k. That would be definitive; either to verify harey's derivation or perhaps to suggest, by their empirical values, a derivation of a different kind. Add to that some simulations starting with n=50 and compare next-collision probabilities for k=50 and lower against those having n=100 as a starting point. If harey's analysis is right, they should be the same whether n=100 initially or n=50 initially. Anyone care to try that?

If we knew that, we could tell you the length of the rope.

I know. My answer was subtle. What happens next?

Getting things started. You can do it if ...

If I had only seconds to decide I would bet those odds.

Well deserved! This may have become, unintentionally the best "Aha!" puzzle on the site. Once you see it, you wonder why we thought it was difficult. But for me it took some thought to accept it..

I think pavan has it.

That would argue in favor of Peter's position then. Is there an even stronger argument?

Peter says all numbers are interesting, in the sense of his given examples. Paul says there are uninteresting numbers, in the same sense. Who can make the better case for his position?

Can you prove it?

Peter and Paul were overheard yesterday at the water cooler. Their conversation went something like this: Peter: I just love numbers. I find them all interesting. Paul: What do you mean by that? Peter: Look at the number six. It's perfect, because 1 x 2 x 3 = 1 + 2 + 3 = 6. And four is interesting because 2 x 2 = 2 + 2 = 4. No other number has that property. Two is the first, and only, even prime number. A really interesting number is 1729 = 13 + 123 = 93 + 103. It's the smallest number that is the sum of two distinct pairs of cubes. Then there's ... Paul: But can you consider all numbers interesting? Surely there are many that lack an interesting property of the type you have described. I would call such numbers uninteresting. With whom do you agree?

One of my favorite problems asks the best strategy to get the highest number possible from a finite collection (say of 100 random numbers) whose values are told to you sequentially, and you must choose one of them at the moment you hear it. It has been posted here before, so I won't repeat it as a puzzle. It's a "stopping" puzzle and you choose when to stop in a way that maximizes your expected "score." (Not that maximizes your chances of choosing the highest number from the collection.) Here's another "stopping" puzzle that uses a standard deck of cards. A shuffled deck is placed face down, in a stack. A dealer begins turning the top card face up and placing it in a discard pile. At a time of your choosing you say "stop." The dealer then turns over the next card, and if it's a red card, you win. Note you are free to say "stop" at any time. What is your strategy?

Right on. I meant to say 20 diagonals. But you understood the other eight are perimeter edges.

I had a thought. Suppose we treat the ensemble of n=2m bullets as nested clusters. So, for n=2 the bullets are aa. There are two cases: which of the two is faster. Annihilation in one case, Escape in the other. Now can we treat the n=4 case as the two "a" bullets nested within two "b" bullets like baab, and think along the lines that if aa annihilate, then the result depends on which of the two "b" bullets is faster? There's more to it than that, of course, (if aa don't annihilate then you have two ab pairs to consider) but I'm wondering if doing the analysis in that way will permit a way of seeing that the annihilation probability decreases by the factor (n-1)/n each time the previous case is nested between two additional bullets, one in front and one in back. Anybody see how that might work?

@jasen, You, I and CaptainEd and probably others all wonder that. We all think, it seems, that adding two bullets should modify the analysis incrementally rather than requiring us to start from scratch, because we see that p(A) is found by modifying (by a multiplicative factor) the previous result: pn(A) = pn-2(A) (n-1)/n But even the first step is hard to see. From the trivial p2(A) = 1/2 to p4(A) = 3/8 we need to discern a 3/4 factor. But where is it? It would be so cool if the n=4 cases could be grouped creatively to see this. If that grouping could then be made to be algorithmic, the above recursion might be derived, proving the general formula by induction.