harey

@phil1882: The solution does not require a computer. I do not see well encrypting decrypting by hand. All you need: scissors, paper, pencil.

@CaptainEd Good work.... But why so complicated? No need for a third person. <spoiler> 1) The solver secretly creates a matrix with the complete solution. Known numbers are preceded by a star. 2) The challenger writes a program that takes as input this matrix. The program displays numbers preceded by a star and blanks for numbers not preceded by a star and makes the necessary checks. (If the solver fears the program would display everything, it can be tested on another grid.) 3) The solver wipes the harddisk (optional). </spoiler> Almost there. Just the computerized solution does not have the beauty of the manual solution - as I said, it is an intermediate step. How can it be done without a computer? All you need: scissors, paper, pencil.

@Jason Not bad, we might come to the solution this way in 2-3 steps. (Just YOU solved the sudoku, so YOU enter the answer). Hint: Be a little more specific about the program. How should I write the program that you cannot fool it by entering shifted 1 2 3 4 5 6 7 8 9 for every line/column?

Well... suppose I want the proof now and I am not willing to wait unless someone else solves it. Hint: scissors might come handy.

You solved a particularly hard sudoku and you are eager to prove it. Just you do not want to give me any hint, nor, God bless, reveal the solution. How will you proceed?

Bonanova wrote: @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. If I claim that I still have quite correct reactions after drinking a glass of wine, it is on you to prove me that I am wrong. If I claim that I still have quite correct reactions after drinking two bottles of whisky, it is on me to prove that I am right. In this case, it is on him to prove that the statistical properties change. Anyway, both methods use the same proceeding: Step 1) build a table of speeds Step 2) split the table into 2 parts: 'to reject' and 'to reexamine' Step 3) reexamine the part 'to reexamine'. Where they differ is the definition of 'to reject'. One method rejects vn< ... <v3<v2<v1. One method rejects v1>vi (i=2,3, ... ,n). Interpretation of partial products: (number of cases we retained/rejected)/(total before retention/rejection). The partial products of the second method describe what happens collision after collision; the first method might be much less clear, depending on proceedings in step 3. Bonanova wrote: For example, in the case of n=4, the probability for at least one collision is not 3/4, it's 23/24. I agree that p(at least one collision) is not 3/4. I agree that p(at least one collision) is 23/24. Just I do not consider ALL cases with at least one collision: I deselect cases v1>vi (i=2,3, ... ,n). For n=4, 3/4 of cases will remain. It is NOT the full set of cases with at least one collision.

@k-man great graphics!!! Do you know an easy to learn freeware? It might be very handy to attack the problem of collisions before all bullets have been fired.

Suppose the leading bullet has 1/k chance of being the fastest. Then we will not get complete annihilation. So far, so good. But *still* we could get another collision, between other bullets. We could and very often we would, but we do not care. We ONLY consider the complementary case where the leading bullet is NOT the fastest. And that happens with the probability (1-1/k). 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. Look at it this way: - If the LB is the fastest, we quit the game. p=1/k - Necessary condition to continue the game: LB may not be the fastest. p=1-1/k. There SURE will be a collision. We have k-2 bullets Example for k=8: We do not care what happens if LB is the fastest because there will be no annihilation. EXIT In 7/8 cases, LB is not the fastest, so we are sure there will be a collision. It does not matter whether 3 collides with 4, 6 with 7 or 7 with 8. Just two bullets are gone. For future convinience, we renumber the bullets. Now, we have k=6 We do not care what happens if LB is the fastest... EXIT In 5/6 cases, LB is not the fastest, so we are sure there will be a collision. Again, it does not matter who collides with whom. Again, we renumber. We got here with the p that the LB was not the fastest when we had 8 bullets AND with the p that the LB was not the fastest when we had 6 bullets: 7/8 * 5/6 Now, we have k=4 We do not care what happens if LB is the fastest... EXIT In 3/4 cases, LB is not the fastest, so we are sure there will be a collision. Again, it does not matter who collides with whom. Again we renumber. We got here with the p that the LB was not the fastest when we had 8 bullets AND with the p that the LB was not the fastest when we had 6 bullets AND with the p that the LB was not the fastest when we had 4 bullets: 7/8 * 5/6 * 3/4 Now, we have 2 bullets We do not care what happens if LB is the fastest... EXIT In 1/2 cases, LB is not the fastest, so we are sure there will be a collision. To get here: 7/8 * 5/6 * 3/4 * 1/2 Think of it this way. For an initial ensemble of n bullets, there are n! permutations of their speeds, Oh, not again!!! It took me a long time to get freed of the relative speeds. The trouble is that it works well for k=2, but it gets very complicated for higher k. Take 4 bullets with v1>v2>v3>v4 when the distances are equal: 9 8 2 1 at first, 8 hits 2 9 8 6 1 at first, 6 hits 1 To know what happens, you have to consider not only the speed hierarchy, but the speed differences. There remain two bullets, it can be managed. However, imagine 6 bullets. After the first collision, the distances are not equal so the speed differences do not help. Gets really, really complicated.

@Rainman: In Europe, we slowly quit Dark Ages and advanced countries switch to Euro. Coins are identical on one side and national on the other side: French, German, Austrian, Greek... The coins travel quite well over the borders - there are studies on it, but that's another story. I have three coins in my pocket. I take one coin out and look at it before putting it back: it is French. I do it three times and every time it is French. What is p(all are French)? Hell only knows how these coins got into my pocket.

@jasen: a computer simulation for such a problem is IMHO an overkill. Bonanova's approach is correct, he just did not finish it.

@bmad: yes, "non-mathematical" equivalence of "the jar is quite large" and "the marbles are quite small" @jasen: In overwhelming majority of cases, I base my decision on probability, very exceptionally on luck. @bonanova: The answer I expected. I would reason something like that: if there is one black marble, p(black)=1/100. Repeating 100 times, I would estimate p(all white) about 95% and would be very surprised if I were told it is less than 90%. Knowing the solution, I recall the problem of n people having birthday the same day. However, your formula is missing something. If you complete it, you will get another surprise. (Please hurry, I do not want to be faced with the problem of two best answers again.)

There are 100 (quite small) marbles in a (quite large) jar. Pull out one marble, look at it, put it back. You have done it 100 times. All marbles were white. Would you bet 5:1 that they are all white? Bonus (and most interesting) question: Suppose you have 15-20 seconds to decide.

The speed is a real number. As there is an infinity or real numbers, p(two bullets have the same speed)=zero, at least for a "small" n. The same way we do not suppose that 3 (or more) bullets can collide. However, there is something else that gives me headaches. It works when there are n bullets in line AFTER all n bullets were shot. What if the first two bullets collide and then n-2 bullets are shot? More generally, what if there are collisions before all bullets are shot?

Yes, the "official" one. But as I know it, it would be unfair to publish it. So I will leave it to someone else. We gave some hints now, did not we?

The list of given examples is not exhaustive nor limiting. You can tailor a property to any number and we can argue ad eternum whether this property is interesting or not. Just my personal opinion

Well, I know the "official" answer to this problem, but I do not agree with it. Human language is very imprecise, "interesting" is quite subject to interpretation. I.e. my ex does not find 4 interesting at all. 2+2=2*2=2^2? So what?

I hope I got it:

I calculated very roughly. Interpolating an exponential is quite dangerous. If the temperature was rounded by 0.2 degrees and measured 2-3 minutes before/after the whole hour, you can get quite a different result. Proof is left to the reader.

Not necessarily. v3>v2>v1 and diff_1<>diff_2 assumed diff_1=v2-v1 diff_2=v3-v2 if(diff_2>diff_1) then [3 reaches 2] else [2 reaches 1] I just cannot figure out p(diff_2>diff_1).

@hhh3: Can you tell how?

What about a supplementary rule excluding Fred has 354?

I have got 3 solutions, but I do not really understand the point (9)