April 2007 - mathfun@mailman.xmission.com

[math-fun] Re: Path Question
by James Propp 17 Apr '07

17 Apr '07

David Wilson wrote: > Suppose there is a man standing on a random square of a random polyomino. At regular intervals, we may instruct the man to move in one of the directions north, south, east or west. If the adjacent square in the specified direction is part of the polyomino, the man will move to that square, otherwise he will stay on his current square. > > Is there a single infinite sequence of directions we can give to the man that guarantees he will eventually visit every square of the polyomino, regardless of its shape or size or of the man's initial square? Here's another solution: Generate a random string of instructions. With probability 1, it will have the property you desire, since it will contain every finite sequence of instructions. Of course, randomness plays no essential role here, as other people's solutions to David's question have made clear. This topic provides me with a good opportunity to raise a question that has been on my mind for a year or two: Can anyone find an explicit construction of an infinite sequence S of 0's and 1's with the property that for any finite bit-string s, the relative frequency with which s occurs in the first N bits of S converges to (1/2)^(length of s) with error that falls like (log N)/N? Note that the Champernowne sequence A030190 has error 1/(log N). An explicit construction of Alon, Kohayakawa, Mauduit, Moreira and R\"odl allows one to achieve error 1/N^c for any exponent c greater than 2/3 (which beats what one would get from a random sequence of bits). Jim Propp

3 4

[math-fun] Pythagorean quadrilateral
by Michael Kleber 16 Apr '07

16 Apr '07

A friend recently mentioned to me the following ARML problem from 1989: "A convex hexagon is inscribed in a circle. If its successive sides are 2, 2, 7, 7, 11, 11, compute the diameter of the circumscribed circle." (Anyone who wants to solve this on their own may go do so now, and come back later for the rest of my question.) Since we can reorder sides of this cyclic hexagon, the question is the same as asking for the diameter D of a circle in which you can inscribe a quadrilateral with side lengths 2,7,11,D. So maybe we should generalze from Pythagorean triangle, and say that a convex n-gon is Pythagorean if it has integral "hypotenuse" D and edges a1, a2,...,a_{n-1}, and can be inscribed in a semi-circle with diameter D. The obvious question is, what's the generalization of the Pythagorean theorem? In the quadrilateral case, the relation you get -- necessraily symmetric on the edges a_i -- turns out to be D * (a1^2 + a2^2 + a3^2) + 2 a1 a2 a3 = D^3 It's maybe more elegant-looking if you say that you're searching for rational solutions to the D=1 version, a^2 + b^2 + c^2 + 2abc = 1 but maybe not, since the LHS isn't homogeneous. Solutions include all Pythagorean triangles, by setting a3=0, and lots of solutions like 2-2-7-8, whose trigonometric meaning I'll leave you to ponder. Hmm, I suppose the regular hexagon's sol'n 1-1-1-2 also falls into this category. But the interesting solutions start with the 2-7-11-D from the ARML, then 2-9-12-16, 6-11-14-21, 1-12-22-26, 3-14-25-30, and so on. Do these come up anywhere else? And what's the relation between the edges and the hypotenuse for the n-gon case? Likely this is all well-known to those who know it, but not to me... --Michael -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

1 0

[math-fun] Re: Path Question
by James Propp 16 Apr '07

16 Apr '07

>> Note that the Champernowne sequence A030190 has error 1/(log N). >> An explicit construction of Alon, Kohayakawa, Mauduit, Moreira and >> R\"odl allows one to achieve error 1/N^c for any exponent c greater >> than 2/3 (which beats what one would get from a random sequence of >> bits). > > *Less than* 2/3? Oops: right, less than 2/3. Jim

1 0

[math-fun] hexadoku grids
by Kerry Mitchell 16 Apr '07

16 Apr '07

Hi, I'm looking for solved hexadoku grids (like sudoku, but 16x16 instead of 9x9). Ideally, I'd like to find symmetric grids or grids where each contiguous 4x4 block uses each character only once, not just the main 4x4 blocks. Any hints? Thanks, Kerry Mitchell -- lkmitch(a)gmail.com www.fractalus.com/kerry

3 3

Re: [math-fun] Geometry/topology puzzle
by Daniel Asimov 14 Apr '07

14 Apr '07

Gareth wrote: << (I wrote): > Consider the cubical 3-torus T^3 := R^3/Z^3 -- 3-space > factored out by the group of integer translations. > > Endow it with the quotient metric. (The distance between > [p] := p + Z^3 and [q]:= q + Z^3 for p,q in R^3 is the least > distance of the form |x-y| where x is in [p] and y is in [q].) > > PUZZLE: Consider two points P, Q of T^3 that are the maximum > distance apart, namely sqrt(3/4). What is the topology of the > locus of points of T^3 equidistant from P and Q ? Prosaic solution follows after spoiler space. [omitted] >> Gareth's solution is indeed the one I had in mind. (I admit that the answer to such a prosaic problem suprised me.) N.B. Scott Huddleston also came up with the same picture, in private e-mail.) --Dan

1 0

[math-fun] Path Question
by David Wilson 14 Apr '07

14 Apr '07

Suppose there is a man standing on a random square of a random polyomino. At regular intervals, we may instruct the man to move in one of the directions north, south, east or west. If the adjacent square in the specified direction is part of the polyomino, the man will move to that square, otherwise he will stay on his current square. Is there a single infinite sequence of directions we can give to the man that guarantees he will eventually visit every square of the polyomino, regardless of its shape or size or of the man's initial square?

3 2

[math-fun] Geometry/topology puzzle
by Daniel Asimov 14 Apr '07

14 Apr '07

Consider the cubical 3-torus T^3 := R^3/Z^3 -- 3-space factored out by the group of integer translations. Endow it with the quotient metric. (The distance between [p] := p + Z^3 and [q]:= q + Z^3 for p,q in R^3 is the least distance of the form |x-y| where x is in [p] and y is in [q]. PUZZLE: Consider two points P, Q of T^3 that are the maximum distance apart, namely sqrt(3/4). What is the topology of the locus of points of T^3 equidistant from P and Q ? --Dan

2 1

[math-fun] Re: prime generating cellular automata
by Dean Hickerson 11 Apr '07

11 Apr '07

Richard Schroeppel wrote: > Dean Hickerson produced a Conway Life pattern in the 1980s which created a > glider stream with gliders at (only) the prime numbered positions. Fun to > watch. Actually 1991. In 2005, Jason Summers built 3 more efficient patterns that do the same thing, but twice as fast. All are shown, in RLE format, at: http://www.math.ucdavis.edu/~dean/RLE/primer.html Dean Hickerson dean(a)math.ucdavis.edu

1 0

[math-fun] prime generating cellular automata
by Richard Schroeppel 11 Apr '07

11 Apr '07

simon plouffe > > I just met Jean-Paul Delahaye in Montreal and at the conference he gave, showed to us a cellular automata that produces the primes one after the other. I will try to find a pointer to this thing, which was quite interesting to watch, it ran on a mac and I think this comes from an old program that I used to have where you could copy and paste a bitmap image and run it as if it was a cellular automaton. Except that in this case , it produces the primes. Dean Hickerson produced a Conway Life pattern in the 1980s which created a glider stream with gliders at (only) the prime numbered positions. Fun to watch. I'll pose a query of my own: It's easy to show that a cellular automaton with two states and a 4-cell neighborhood (using only the orthogonally adjacent cells, and not the diagonal cells) is relatively boring: The pattern - 0 - 0 0 1 - 0 - must produce a 1 in the center, or else the rule won't let patterns grow. And if this pattern produces a 1, then patterns grow in all directions at speed 1. (This does include Winograd's xor rule, which is surprising but still has quite limited behavior complexity.) Conway's great idea was to use the 8-cell neighborhood, including the diagonal neighbors. This leads to Life, and a raft of interesting goodies. My question: Suppose we stick with the 4-cell neighborhood, but break the 2-state limitation. If we allow three states, can we get interesting stuff? (Von Neumann's self-replicator construction used 29 states, and the 4-cell neighborhood.) Rich rcs(a)cs.arizona.edu

4 3

[math-fun] Cellular automaton question
by David Wilson 11 Apr '07

11 Apr '07

Is there a 2d cellular automaton that (a la Conway's Game of Life) that - Does not oscillate when run on an infinite random pattern. - Tends to preserve the apparent randomness of an infinite random pattern over many generations, except... - Certain large patterns tend to introduce structure, if only temporarily, in succeeding generations. In other words, can we describe a CA that occasionally produces "universes" out of random "quantum noise"?

3 2