January 2004 - mathfun@mailman.xmission.com

[math-fun] Help wanted on Thue sequences
by Dean Hickerson 06 Jan '04

06 Jan '04

Here's a question (worth $60) from Sherman Stein (stein(a)math.ucdavis.edu) It asks if a certain process, described later, continues forever. I did some computing a few years ago, and found that it runs for at least 30 million steps. I suspect that it stops eventually, but my program wasn't fast enough to find out when. Sherman thinks it'll run forever. We're hoping that someone else can think of either a proof that it runs forever, or a faster algorithm that will determine when it stops. (Some of this is discussed in Sherman's book "How the other half thinks".) We want to construct an infinite string over a finite alphabet which doesn't contain any squares. (A square is a substring of the form XX where X is a nonempty string.) An infinite squarefree string is sometimes called a Thue sequence, because the problem was apparently first posed and solved by Axel Thue in 1912. It's easy to see that there's no Thue sequence over an alphabet with only 2 symbols; in fact every binary string of length 4 contains a square. But with 3 or more symbols, Thue sequences exist. Thue proved this using a method called "expansion". The expansion of a string is obtained by replacing every 0 by 01201, every 1 by 020121, and every 2 by 0212021. It can be shown that if a string has no squares then neither does its expansion. So we can get an infinite squarefree sequence by starting with 0 and repeatedly expanding: 0 -> 01201 -> 01201020121021202101201020121 -> 0120102012102120210120102012101201021202101201020121021202102012101201 0212021020121021202101201021202102012101201020121021202101201020121012 010212021012010201210212021020121 -> ... There are variations on this method, in which 0, 1, and 2 are replaced by different strings. This particular triple of strings has been shown to have the shortest total length among all triples for which the expansion of every squarefree string is squarefree. Sherman wondered if a Thue sequence could be constructed by a greedy algorithm: What if we start with the empty string and repeatedly append the smallest number in {0,1,2} which doesn't create any squares? After 7 steps we get 0102010. But now we're stuck: adding 0 gives the square 00, adding 1 gives 0101 and adding 2 gives 01020102. Even if we use more than 3 symbols, this process always stops. In fact, with n symbols it stops after 2^n - 1 steps. E.g. with 5 symbols we get 0102010301020104010201030102010. Instead of always adding the smallest possible symbol, suppose we alternate between adding the smallest and adding the largest. It turns out that the process again stops after 2^n - 1 steps if we use n symbols. E.g. with 5 symbols we get 0403040204030401040304020403040. We can try other variations: We can use any infinite string of S's and L's to decide whether to append the smallest or largest symbol at each point. So the two algorithms just discussed are represented by the strings SSSS... and SLSLSL... We're mainly interested in periodic SL-strings, so we'll shorten the names of these to just S and SL. Sherman and I experimented with other strings, and eventually conjectured that, with 3 symbols, every periodic SL-string gives only a finite squarefree string. Here are some examples of the lengths that we get for certain strings: S 7 SL 7 SSL 19 SLS 27 SLL 26 SSSL 7 SSLS 56 SSLL 39 SLSS 7 SLLS 79 SLLL 55 SLSLSSLSSLSLSL 1134 (shortest SL-string giving length >= 1000) SLLLLLSLLLSSSSSSLLSL 1706 Given any finite squarefree sequence of 0's, 1's, and 2's, duplicating the last symbol would give a square, so there are at most 2 symbols that can be appended to preserve squarefreeness. Each of these is either the smallest or the largest symbol that can be added, so every Thue sequence on {0,1,2} can be obtained by the algorithm above, for some infinite SL-string. As a consequence, the lengths that we can get from periodic sequences are unbounded. That argument doesn't work if there are more than 3 symbols, and at least some Thue sequences on 4 symbols can't be obtained from an infinite SL-string. In fact we don't know if there's even one Thue sequences that can be obtained that way. When we experimented with more than 3 symbols, we found that most SL-strings still produce finite strings. But some short strings ran for a long time before stopping; for example SSLLL on 6 symbols stops after 2353749 steps. Then we tried SSSSSSL on 4 symbols. This runs for at least 30 million steps, which took my program 3 days. For such a long string, checking to see if a particular symbol can be added is quite time-consuming. If the program only stores the string so far, then it has to check about n/2 possible squares when the length is n. We can speed this up by having the program keep track of additional information. My program also records, for each n, the largest m<n (if any) for which the substring of length 20 ending at position m is identical to the one ending at position n. This greatly reduces the number of possible squares that need to be checked. (I have no theoretical reason for using length 20 here; I just experimented with different values and 20 worked well for the cases I tried.) I'm sure there must be a better algorithm to speed things up even more, but I have no idea what would work best. So if anyone out there gets interested enough to do some thinking and/or computing, here are some questions we'd like to have answered: Is there some periodic SL-string that produces an infinite squarefree string on 3 symbols? If not (as we suspect), then how long a squarefree string can you get from an SL-string of period n? Is there some periodic SL-string that produces an infinite squarefree string on 4 or more symbols? Here the empirical evidence doesn't justify a conjecture about the answer. Does SSSSSSL on 4 symbols run forever? Sherman offers $50 for this, and I'll add $10 more. (If your answer is that it stops after a certain number of steps, based on running a computer program, we'll want a copy of the program and verification that it gets the right answers for some known cases.) What's the most efficient algorithm to do these calculations? Dean Hickerson dean(a)math.ucdavis.edu

1 0

Re: [math-fun] looking for state-of-knowledge logic puzzles
by asimovd＠aol.com 06 Jan '04

06 Jan '04

Scott asks: << ... Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ... and after a few rounds of this one of them can deduce the answer. Can anyone supply some puzzles of this flavor? (without answer :-) >> I vaguely recall one of this type (in a 1958 book, "Puzzle-Math", by G. Gamow & M. Stern) which concerned determining which wives were cheating on their husbands, but I can't recall the details -- except that it took 40 days to deduce who the cheaters were. The book is, I fear, out of print, but many local libraries may have copies. Dan Asimov

11 13

Re: [math-fun] looking for state-of-knowledge logic puzzles
by Dan Hoey 06 Jan '04

06 Jan '04

Eugene Salamin <gene_salamin(a)yahoo.com> wrote: > --- Joshua Singer <singer(a)stanford.edu> wrote: > > As it was originally told to me . . . > > A traveler passes through a small village, each of whose inhabitants > > has a single colored dot .... > > ... As the traveler > > passes through, he casually remarks, "Some people in this village > > have blue dots". Ten days later, .... > This can't be right. The information provided by the traveler was > already known to everybody. In the case of the problem of the > unfaithful wives, the king issues an edict, which starts the clock > ticking. I believe the phrase "he casually remarks" should read "he publically announces," meaning that he states it in a way that (1) everyone hears and believes him, (2) everyone knows that (1) occurs, (3) everyone knows that (2) occurs, (4) everyone knows that (3) occurs, etc. all at the same time. It takes about N such pieces of information to make the clock tick for N days. Dan

4 4

[math-fun] Re; small area convex lattice polygons
by Dan Hoey 06 Jan '04

06 Jan '04

Chris Landauer wrote: > well, the systematic search program i wrote to find minimum area > convex lattice polygons took 20 hours for n=20 and 80 for n=21, with > results as follows.... My understanding is that this still does not establish a lower bound on area even for the 11-gon, unless we can somehow prove that there is a minimum-area 11-gon with no edge more than 10 units long. Given the use of SL(2,Z) to force a unit edge, we would have to prove the existence of an 11-gon with a unit edge _and_ no edge longer than 10. I don't know any way of proving such a thing. I gave an argument earlier that would allow us to establish a lower bound rigorously, though I don't know if it's feasible, and I'd like to improve it. I should note that that argument does not allow us to assume a unit edge (since the transform yielding the unit edge might not yield the minimum diameter). Also, in case it wasn't obvious, I was speaking of Euclidean diameter, rather than the Manhattan diameter that Carl uses in his statistics. I've been looking for the net-accessible materials for help with the problem. Steven Finch has a good survey paper http://people.bu.edu/srfinch/cvxl.pdf though I would quibble with his statement that Barany & Tokushige ... computed that a_n lim --- = 0.0185067... n->oo n^3 via a heuristic solution of ~10^10 constrained maximization problems. The paper, which Finch links to at http://www.renyi.hu/~barany/cikkek.ps/hide.ps is more clear in saying that they prove that the actual value of the limit is the minimum of about 10^10 extremal problems (which are too many to solve), and that their heuristic computations indicate that the minimum is "most likely" 0.0185067.... It's possible that Finch means "heuristic" to imply "most likely", but I would be a lot more comfortable if "computed" were changed to "conjectured". Most surprising, to me at least, is that the minimal area n-gon (when mapped via the appropriate linear transformation) seems to approximate an ellipse (x/c)^2 + (y/d)^2 = 1, with c ~ .003573 n^2 and d ~ 1.656 n. Imagine the minimum eccentricity near n=463 . Another item that may be of interest is the fact that we may take the minimum-area 2n-gon to be centrally symmetric, based on a circular descent argument. Dan

1 0

Re: [math-fun] looking for state-of-knowledge logic puzzles
by gale＠Math.Berkeley.EDU 05 Jan '04

05 Jan '04

>Sorry. I mentioned the book in an earlier message. "Tracking the Automatic Ant and othe mathematical explorations", Springer, 199?. DG You wouldn't believe what you get when you are searching for David Gale on > Amazon ("The Life of David Gale" included!). What is the name of your > book? > > Helger > > On Mon, 5 Jan 2004, David Gale wrote: > > > Here are some more subtle examples. > > > > 1.You and I have numbers on our foreheads and are told (truthfully) that > > their total is either 5, 8 or 15. > > A bell rings every ten seconds and after each ring if either of us knows > > our number we announce it and win. > > Prove: For any pair of forehead numbers one of us will know our number > > after at most 10 rings. > > (Curiously, if the numbers are 5,9,15 then the bell can ring until the cows > > come home and there will be no winner). > > > > 2. (Conway-Paterson) In the three player game with forehead numbers 2,2,2 > > and possible totals 6,7,8 the players will know their numbers after on the > > 15th ring. > > > > To see why buy my book. (Amazon usually ships in 24 hours) > > > > David > > > > > > > > At 04:52 PM 1/5/04 -0800, you wrote: > > >As it was originally told to me . . . > > > > > >A traveler passes through a small village, each of whose inhabitants has a > > >single colored dot on his or her forehead. Some have a blue dot, some > > >have a red dot, some have a green dot, etc. Each person can see every > > >other person's dot, but cannot see his > > >own. Because the village is small, every person knows the color of every > > >other person's dot, except his own. It is taboo in the village to know > > >the color of one's own dot. The village's strict rule is that anyone > > >discovering the color of his own dot must > > >leave the village within 24 hours, never to return. As the traveler > > >passes through, he casually remarks, "Some people in this village have > > >blue dots". Ten days later, the ten people from the village who had blue > > >dots have all vanished. > > > > > >The problem is to explain how the departure of the ten people occurred. > > > > > >JSS > > > > > > > > >asimovd(a)aol.com wrote: > > > > > > > Scott asks: > > > > > > > > << > > > > ... > > > > Then two mathematicians iterate for awhile, > > > > A: I can't deduce the answer. > > > > B: Neither can I. > > > > A: I still can't deduce the answer. > > > > ... > > > > > > > > and after a few rounds of this one of them can deduce the answer. > > > > > > > > Can anyone supply some puzzles of this flavor? (without answer :-) > > > > >> > > > > > > > > I vaguely recall one of this type (in a 1958 book, "Puzzle-Math", by G. > > > Gamow & M. Stern) which concerned determining which wives were cheating > > > on their husbands, but I can't recall the details -- except that it took > > > 40 days to deduce who the cheaters were. > > > > > > > > The book is, I fear, out of print, but many local libraries may have > > > copies. > > > > > > > > Dan Asimov > > > > > > > > _______________________________________________ > > > > math-fun mailing list > > > > math-fun(a)mailman.xmission.com > > > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > > > >_______________________________________________ > > >math-fun mailing list > > >math-fun(a)mailman.xmission.com > > >http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

1 0

[math-fun] looking for state-of-knowledge logic puzzles
by Scott Huddleston 05 Jan '04

05 Jan '04

I'm looking for one or more logic puzzles I've seen in the past that run something like the following: Some core information is given to two people, possibly the sum and product of two integers or some relation thereon. Rusty memory says maybe one person is given the sum, the other is given the product. Then two mathematicians iterate for awhile, A: I can't deduce the answer. B: Neither can I. A: I still can't deduce the answer. ... and after a few rounds of this one of them can deduce the answer. Can anyone supply some puzzles of this flavor? (without answer :-) Thanks, - Scott P.S.- The original wording was probably an ambiguous "I don't know the answer" rather than the more accurate "I cannot deduce the answer". I don't think the puzzle(s) actually specified mathematicians, but realistically nonmathematicians are unlikely to make the necessary deductions.

4 4

[math-fun] Experimental mathematics book
by David H Bailey 05 Jan '04

05 Jan '04

I am pleased to announce that the new book "Mathematics by Experiment: Plausible Reasoning in the 21st Century" by Jonathan Borwein and myself is now available, either from the publisher (www.akpeters.com) or from www.amazon.com. A second volume, "Experimentation in Mathematics: Computational Paths to Discovery", will be out in February. Both volumes provides lots of examples of computational mathematics in action: discovering new formulas, using graphics, Mathematica, Maple, etc. If you would like to get a taste of these books, a *free* condensed version is available at: http://www.expmath.info. Cheers, David H Bailey dhbailey(a)lbl.gov

1 0

[math-fun] test
by Ray Tayek 05 Jan '04

05 Jan '04

--- ray tayek http://tayek.com/ actively seeking telecommuting work vice chair orange county java users group http://www.ocjug.org/ hate spam? http://samspade.org/ssw/

1 0

[math-fun] Re; small area convex lattice polygons
by Chris Landauer 05 Jan '04

05 Jan '04

hihi, all - well, the systematic search program i wrote to find minimum area convex lattice polygons took 20 hours for n=20 and 80 for n=21, with results as follows min min min area perim longest n found found edge 10 14 18 3 11 21.5 22 3 12 24 24 3 13 32.5 28 4 14 40 30 3 15 51.5 34 4 16 59 36 3 17 75.5 42 5 18 87 44 4 19 106.5 50 5 20 121 52 4 21 144.5 60 5 so i wrote a random search program that divides each polygon into four ``corners'', and only does the last corner systematically - here, the program runs for as long as i let it, and though it often finds smaller area polygons after a lot of time, it usually finds the best one it finds at all within a few minutes - the results are as follows (after some days on many machines) The random program did find the same smallest area polygons (also smallest perimeters and maximum edge lengths) as the systematic search program did for n<=21 It should be noted that the minimum perimeter found and minimum longest edge length found are not necessarily from the same polygon. However, they are from polygons that have the same minimum area min min min area perim longest n found found edge 22 164 62 5 23 193.5 66 5 24 210 72 5 25 248.5 76 5 26 274 80 5 27 315.5 86 5 28 345 90 5 29 394.5 94 5 30 430 98 5 31 485.5 104 5 32 527 108 5 33 594.5 114 5 34 661 120 6 35 715.5 126 6 36 764 128 5 37 845.5 134 6 38 912 140 6 39 994.5 144 6 40 1055 150 6 41 1170.5 156 6 42 1299 164 6 43 1439.5 186 7 44 1553 182 7 45 1677.5 190 7 46 1753 204 7 47 1867.5 202 7 48 1969 212 7 49 2105.5 216 7 50 2199 222 7 i will put the details of the algorithms, discussion of the results, and the source code on the web this week sometime, but i've been at this problem for a month now (even dreaming about arrangements of edges on graph paper), and it's time to stop for a while more later, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal(a)aero.org

1 0

Re: [math-fun] Permutation group problem
by Dan Hoey 05 Jan '04

05 Jan '04

"Allan C. Wechsler" <acw(a)alum.mit.edu> wrote about: > [...] the name of the algorithm for determining whether a given > permutation can be expressed as a product of given generators: it's > the Furst-Hopcroft-Luks algorithm. I should probably have responded earlier, when you mentioned you had learned the name from the Rubik's Cube list. I believe I introduced the algorithm there under that name. Since then, I have been reliably informed that the algorithm is more usually and properly known as Sims's algorithm. The paper by Furst, Hopcroft, and Luks was essentially a formalization and analysis of the algorithm that Charles C. Sims described in 1967. I regret the mistaken attribution. Dan

1 0