- mathfun@mailman.xmission.com - mailman.xmission.com

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

18 Apr '07

I wrote: >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? Dan Asimov asked: >May I ask for a clarification of exactly what >"error that falls like (log N)/N" means? Good question! What I think I mean is that if we let k denote the length of s and define f(N) as the number of occurrences of s in the first N bits of S, then the discrepancy d(N) = f(N) - (N-k+1)/2^k satisfies |d(N)| < C (log N) / N for some constant C, when N is sufficiently large. Note that I used (N-k+1)/2^k instead of N/2^k since a bit string of length k only gets N-k+1 chances to occur in a bit string of length N. Incidentally, that was a fun problem about the 3-torus, Dan! Jim

1 0

[math-fun] 3-state cellular automata with von Neumann neighborhood
by Dean Hickerson 18 Apr '07

18 Apr '07

Richard Schroeppel wrote: > 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? We can get around the problem described above if we have the transitions - 0 - - 0 - 0 0 1 -> 2 and 0 0 2 -> 0 - 0 - - 0 - and some way for a 2 to change into a 1. I've been playing around with such rules for a few days. I haven't found any that are very Life-like, and I haven't found any good ones that have simple verbal descriptions like Life does. But there are some that are at least somewhat unpredictable. The most interesting that I've seen has a c/6 spaceship, two 2c/4 spaceships, an 8c/16 puffer producing period 6 oscillators, and a lengthening spaceship that grows at 8c/16 (producting a period 10 wick) and decays at c/7. The wickstretcher can also decay at 6c/22, leaving behind period 3 oscillators. For anyone using Mirek's Cellebration, here's a pattern showing all of those: #MCell 4.20 #GAME Neumann binary #RULE 3020220000200220000002000001220020000220220000000000000000000201 #RULE 0000000000010001001010101000101000001000000000101000001000010100 #RULE 0001000010000000000001000000000000210100010000000000010200200000 #RULE 0000000000000000002000000100000220000000200000000000 #BOARD 1500x1500 #WRAP 1 #CCOLORS 3 #L 27.A$28.A$28.A$27.A9$24.B..AA8$19.B$18.BA.A..B$19.BA.A4.AA$20.B8$8.B.B #L 11.A.B$B.B4.BA.AB4.A3.A.B4.AA$8.B.B11.A.B9$18.B8.AA$14.B3.AB.A..B$18.B #L 8$8.B.B7.B8.AA$7.BA.A.A.B3.AB.A..B$8.B.B7.B Small random patterns usually settle down to a few oscillators and some of the moving things shown above. Larger random patterns seem to grow slowly for a while, often emitting some of the things shown above. But eventually they also produce messy 2c/4 puffers, which increase the rate at which they expand, since such puffers emit perpendicular puffers, which emit others, etc., filling space with their debris. (Unfortunately, MCell on my old PC isn't fast enough to see much of that.) To describe the rule, I'll write "c/nesw -> d" to mean that if a cell is in state c and its neighbors to the north, east, south, and west are in states n, e, s, and w, respectively, then the cell will change to state d in the next generation. The rule is symmetric, so I'll only list one transition from each equivalent group. E.g. 0/0001 -> 2 also implies 0/0010 -> 2, 0/0100 -> 2, and 0/1000 -> 2. The rule is: 0/0001 -> 2 0/0011 -> 2 0/0111 -> 2 0/1111 -> 2 0/0202 -> 2 0/0222 -> 1 1/0000 -> 1 1/0002 -> 1 1/0011 -> 1 1/0101 -> 1 1/1112 -> 1 1/2222 -> 1 2/0000 -> 1 2/0002 -> 1 2/0202 -> 2 2/0212 -> 2 Except for these, all transitions have the form c/nesw -> 0. This rule convinces me that there are interesting ones of this type, but it's probably not the best of the bunch. Dean Hickerson dean(a)math.ucdavis.edu

1 0

[math-fun] Permuter Puzzle
by David Wilson 17 Apr '07

17 Apr '07

Suppose you have a box with a hole on the top and the side. When you feed 10 marbles into the top hole, a mechanism in the box shuffles the marbles and sends them out in a specific permuted order. If you have 5 identical white and 5 identical black marbles, how many tries are necessary to determine the permutation?

2 1

Re: [math-fun] Re: Path Question
by Daniel Asimov 17 Apr '07

17 Apr '07

Jim writes: << 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? >> May I ask for a clarification of exactly what "error that falls like (log N)/N" means? I think I know what this means, but would like to see the condition expressed in formal language, just to be certain. --Dan

1 0

[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