[math-fun] Draft of my April 17, 2019 essay
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at http://mathenchant.org/047-draft1.pdf I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged. One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it. Thanks, Jim
I don’t have anything to add in terms of mazes or working a proof from both ends, but I am reminded of a classic cartoon that you might want to throw in — the “then a miracle occurs” cartoon. Here is a link from stack overflow, or you could try and find a link at the original artists site https://stackoverflow.blog/wp-content/uploads/2017/02/then-a-miracle-occurs-... Steve -- Stephen Lucas, Professor Department of Mathematics and Statistics MSC 1911, James Madison University, Harrisonburg, VA 22807 USA Phone 540 568 5104, Fax 540 568 6857, Web http://educ.jmu.edu/~lucassk/ Email lucassk at jmu dot edu (Work) stephen.k.lucas at gmail dot com (Other) Mathematics is like checkers in being suitable for the young, not too difficult, amusing, and without peril to the state. (Plato) On Apr 12, 2019, at 10:21 AM, James Propp <jamespropp@gmail.com<mailto:jamespropp@gmail.com>> wrote: I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at https://urldefense.proofpoint.com/v2/url?u=http-3A__mathenchant.org_047-2Ddr... I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged. One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it. Thanks, Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
The kinds of maze you often see as busywork have a single entrance and a single exit on the exterior wall, and have a single path between any two points in the maze. There's an algorithm for generating such mazes of arbitrary height when only the width is known in advance. I vaguely recall a story about Eller, the guy who came up with the algorithm, not thinking it was possible, but he heard that someone else had done it, so he worked it out---only to find that the other guy hadn't done it after all! Unfortunately, I can't find a source for this. On Fri, Apr 12, 2019 at 8:23 AM James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
On Fri, Apr 12, 2019 at 9:14 AM Mike Stay <metaweta@gmail.com> wrote:
The kinds of maze you often see as busywork have a single entrance and a single exit on the exterior wall, and have a single path between any two points in the maze. There's an algorithm for generating such mazes of arbitrary height when only the width is known in advance.
Hmm, that didn't quite capture how cool Eller's algorithm is. You only need to store one row of the maze in memory at any time, forgetting everything that went before. As soon as the "stop" signal is received, you print out the final row and the exit. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
There's a clever bijection between mazes (spanning trees of an m-by-n grid graph) and domino tilings of a (2m-1)-by-(2n-1) rectangle with the bottom-left corner removed. And you can greedily build such domino tilings, one layer at a time, by 'playing Tetris with dominoes'. I imagine that if you take this algorithm and pass it through the bijection, you get Eller's algorithm. -- APG
Sent: Friday, April 12, 2019 at 4:16 PM From: "Mike Stay" <metaweta@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Draft of my April 17, 2019 essay
On Fri, Apr 12, 2019 at 9:14 AM Mike Stay <metaweta@gmail.com> wrote:
The kinds of maze you often see as busywork have a single entrance and a single exit on the exterior wall, and have a single path between any two points in the maze. There's an algorithm for generating such mazes of arbitrary height when only the width is known in advance.
Hmm, that didn't quite capture how cool Eller's algorithm is. You only need to store one row of the maze in memory at any time, forgetting everything that went before. As soon as the "stop" signal is received, you print out the final row and the exit. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hi Jim! Thanks for this as always. Another nice application of the “meet in the middle” approach is to find a waypoint that any solution must go through. This is the good way to solve the Towers of Hanoi, for instance — which is a mazey problem in an exponentially large maze. The waypoint being, of course, the fact that at some point we have to move the largest disk. C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Great observation, Cris! I'll add this. Jim On Fri, Apr 12, 2019 at 12:08 PM Cris Moore <moore@santafe.edu> wrote:
Hi Jim! Thanks for this as always.
Another nice application of the “meet in the middle” approach is to find a waypoint that any solution must go through. This is the good way to solve the Towers of Hanoi, for instance — which is a mazey problem in an exponentially large maze. The waypoint being, of course, the fact that at some point we have to move the largest disk.
C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
p.s. in Endnote #2, "The trick is to encode x using all million possible single-stage encryption procedures, obtaining a list of a million nonsense strings, and decode x” using all million possible single-stage decryption procedures, obtaining another list of a million nonsense strings, and then look for a string that’s in both lists.”: you might want to challenge the reader to figure out how to “look for a string that’s in both lists” in time which is only about O(n log n) where n=a million. C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
And after figuring out how to do it in O(n log n) then they can realize you only need to store one list, and you can do it in amortized O(n) (ignoring the length of the message). Even better, you don't actually need to store the lists, but just some small number of bits per message . . . On Fri, Apr 12, 2019 at 9:10 AM Cris Moore <moore@santafe.edu> wrote:
p.s. in Endnote #2, "The trick is to encode x using all million possible single-stage encryption procedures, obtaining a list of a million nonsense strings, and decode x” using all million possible single-stage decryption procedures, obtaining another list of a million nonsense strings, and then look for a string that’s in both lists.”: you might want to challenge the reader to figure out how to “look for a string that’s in both lists” in time which is only about O(n log n) where n=a million.
C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.) Hints? Answers? References? Jim On Fri, Apr 12, 2019 at 12:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
And after figuring out how to do it in O(n log n) then they can realize you only need to store one list, and you can do it in amortized O(n) (ignoring the length of the message).
Even better, you don't actually need to store the lists, but just some small number of bits per message . . .
On Fri, Apr 12, 2019 at 9:10 AM Cris Moore <moore@santafe.edu> wrote:
p.s. in Endnote #2, "The trick is to encode x using all million possible single-stage encryption procedures, obtaining a list of a million
nonsense
strings, and decode x” using all million possible single-stage decryption procedures, obtaining another list of a million nonsense strings, and then look for a string that’s in both lists.”: you might want to challenge the reader to figure out how to “look for a string that’s in both lists” in time which is only about O(n log n) where n=a million.
C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
spoiler below… one approach is to sort both lists. then you can go through both of them in sorted order, advancing whichever list has its current value lower in sorted order, and find any duplicates. alternately, just sort the union of the two lists, and then scan for adjacent strings that are identical. sorting can be done on O(n log n) in lots of ways, and then the scanning process is just O(n). C
On Apr 12, 2019, at 11:29 AM, James Propp <jamespropp@gmail.com> wrote:
I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.)
Hints? Answers? References?
Jim
On Fri, Apr 12, 2019 at 12:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
And after figuring out how to do it in O(n log n) then they can realize you only need to store one list, and you can do it in amortized O(n) (ignoring the length of the message).
Even better, you don't actually need to store the lists, but just some small number of bits per message . . .
On Fri, Apr 12, 2019 at 9:10 AM Cris Moore <moore@santafe.edu> wrote:
p.s. in Endnote #2, "The trick is to encode x using all million possible single-stage encryption procedures, obtaining a list of a million
nonsense
strings, and decode x” using all million possible single-stage decryption procedures, obtaining another list of a million nonsense strings, and then look for a string that’s in both lists.”: you might want to challenge the reader to figure out how to “look for a string that’s in both lists” in time which is only about O(n log n) where n=a million.
C
On Apr 12, 2019, at 8:21 AM, James Propp <jamespropp@gmail.com> wrote:
I've posted a draft of the essay I plan to post on the morning of the 17th (or maybe the night before) at
http://mathenchant.org/047-draft1.pdf
I don't expect to get comments from many of you, but all comments will be appreciated and acknowledged.
One thing that's missing from the essay is a good reference for readers who want to learn more about modern mazes. For that matter, do any of you know of any good references about how to create proofs that explicitly advocate the work-from-the-outside-in tactic? I've never read "How to Read and Do Proofs" or the many similar books that are out there, but if you think readers of my blog would like a particular book in this genre, I'd be glad to mention it.
Thanks,
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cris Moore moore@santafe.edu I confess to an uneasy Physiocratic suspicion, perhaps unbecoming in an academic, that we are throwing more and more of our resources, including the cream of our youth, into financial activities remote from the production of goods and services, into activities that generate high private rewards disproportionate to their social productivity. — James Tobin, 1984
= James Propp <jamespropp@gmail.com> I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.) Hints? Answers? References?
For O(n log n) you can sort the two lists, then scan them in tandem. For O(n) you can put one of the lists in a hash table, then scan through the other. These days a million really isn't considered a large number, for some value of a million.
And to not store the lists explicitly (storing some smallish number of bits instead) you can use a Bloom filter or store a prefix of a good hash for one list, find the hits from the second list and store them explicitly and then redo the first list. And yes, these days even a billion (1E9) is considered pretty small; with multicore and GPU 1E12 is easy to reach. You can get to 1E15 in about a day for many things. On Fri, Apr 12, 2019 at 10:35 AM Marc LeBrun <mlb@well.com> wrote:
= James Propp <jamespropp@gmail.com> I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.) Hints? Answers? References?
For O(n log n) you can sort the two lists, then scan them in tandem.
For O(n) you can put one of the lists in a hash table, then scan through the other.
These days a million really isn't considered a large number, for some value of a million.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
participants (7)
-
Adam P. Goucher -
Cris Moore -
James Propp -
Lucas, Stephen K - lucassk -
Marc LeBrun -
Mike Stay -
Tomas Rokicki