Yes, I should have written that. Jim On Friday, October 5, 2018, Michael Kleber <michael.kleber@gmail.com> wrote:

For all of your comments about the number of explosions, are you actually looking at number of explosions *minus* number of un-explosions? Seems like you ought to be, but I don't think I've seen it mentioned yet. (Still reading though.)

--Michael

On Fri, Oct 5, 2018 at 4:44 PM James Propp <jamespropp@gmail.com> wrote:

...

Usually I publish on the 17th, but this time I'm publishing on the 10th (in connection with Global Math Week). I'm not expecting many of you to spend your weekend hours perusing this, but even if only a couple of you do, I'm sure your comments will be helpful.

http://mathenchant.org/040-second-draft.pdf

Thanks,

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Steve, Two minor comments. First, computer scientists don’t consider O(n^2) moves

to sort “good,” since there are many O(n log_2(n)) algorithms out there. Order n^2 is adequate at best.

What an embarrassing mistake for me to make, considering that once upon a time I taught about sorting algorithms in Introduction to Discrete Mathematics at MIT! Thanks so much for catching it. Second, I think you might get somewhere with understanding what is

happening with the n in the middle puzzle by considering the fact that each number has a specific number of moves it needs to make to get to the correct location.

As I recall, the absolute number of moves a chip needs to make is not deterministic (though of course the number of rightward moves minus the number of leftward moves is deterministic). So when you do the explosions, you need to make sure the one is on the left

edge all the time.

It's not necessary to satisfy this condition throughout: *− − 12345 − −* *− 2 134 5 −* *− 12 3 45 −* etc. There might be something said for small cases to explicitly build the full

decision tree and see if 1/3 is in fact correct for n=3,5. That should be doable by pen and paper. Looks like a great open ended undergraduate research project!

One subtlety one runs into is that there are (at least) three sensible definitions of doing the process randomly. (1) Choose a random path in the full decision tree uniformly. (2) Repeatedly choose a random pair of bubbles that are in the same column uniformly. (3) Repeatedly choose a random column with two or more bubbles uniformly and then choose a random pair of bubbles in that column uniformly. All three appear to follow the 1/3 law. Steve

Jim On Oct 5, 2018, at 10:32 PM, James Propp <jamespropp@gmail.com<mailto:

jamespropp@gmail.com>> wrote:

Yes, I should have written that.

Jim

On Friday, October 5, 2018, Michael Kleber <michael.kleber@gmail.com <mailto:michael.kleber@gmail.com>> wrote:

For all of your comments about the number of explosions, are you actually looking at number of explosions *minus* number of un-explosions? Seems like you ought to be, but I don't think I've seen it mentioned yet. (Still reading though.)

--Michael

On Fri, Oct 5, 2018 at 4:44 PM James Propp <jamespropp@gmail.com<mailto: jamespropp@gmail.com>> wrote:

Usually I publish on the 17th, but this time I'm publishing on the 10th (in connection with Global Math Week). I'm not expecting many of you to spend your weekend hours perusing this, but even if only a couple of you do, I'm sure your comments will be helpful.

https://urldefense.proofpoint.com/v2/url?u=http-3A__mathenchant.org_040-2Dse...

Thanks,

Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com>

https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...

-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com>

https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com>

https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun