From: kasdan@news.cs.columbia.edu (John Kasdan) Newsgroups: sci.math Subject: Re: Sequence with all n-letter words Date: 18 Nov 1995 10:26:13 -0500 In article <48jqta$col@muir.math.niu.edu>, Dave Rusin wrote: >In article <48ihn2$e96@age.cs.columbia.edu>, >John Kasdan wrote: > >>I think it is generally true that for any m and n there exists a >>sequence of length m^n which contains all of the n letter words in m >>characters, (wrc.) (In fact, I am pretty sure I once heard Percy >>Diaconnis give a talk in which he demonstrated a card trick depending >>on such a sequence.) However, I don't remember how to construct the >>sequence. So I would appreciate it if anyone could tell me how the >>construction works, or give me a pointer to where I can find it >>in the literature. > >Seems like I just did this in this forum. >http://www.math.niu.edu/~rusin/papers/known-math/95/1000digits [URL updated 1999/01 -- djr] > wherein Mr. Rusin has posted a very pretty piece which appears to generalize to completely answer my question. (Although a nagging memory still suggests that Diaconnis had a purely combinatorial proof, avoiding the arithmetic in Galois fields which occurs in Mr. Rusin's paper.) >(I still don't quite see why people want to know this.) Funny you should ask. I am currently working on converting some computer generated drawings from a proprietary vector format to TIFF files. The problem of what font we should use has arisen. My boss asked to see "all triples of printable characters" in the font we are considering. Since there are over 90 such characters, the difference between 90^3 and 3*90^3 seemed significant. However, upon due consideration, it turned out that even a mere 729,000 characters were considered too many to scan, so, instead, he asked for all pairs. And there is a cute way to do that, unrelated to Mr. Rusin's general method. (By the way, I thought of the following after I made my original post.) If you consider all of the printable characters to be vertices of a graph you can build a directed multi-graph (dim-graph?) by drawing a directed path in both directions between each pair of vertices and adding a loop at each vertex. The resulting dim-graph satisfies the bridges of Koenigsberg condition and hence there is an Euler path through the dim-graph, which clearly solves the original problem. Furthermore, the proof of the B. of K. theorem provides a greedy algorithm for solving the problem. When I taught the bridges problem many years ago, I too failed to see any application of it, and didn't even stop to think that the proof was constructive. >dave -- John Kasdan; http://www.columbia.edu/~law9023/ ============================================================================== From: jacob@matematik.su.se (Jacob Jordan) Newsgroups: sci.math Subject: Re: Sequence with all n-letter words Date: Fri, 08 Dec 1995 20:34:17 +0100 In article <48sau7$5uf@newsbf02.news.aol.com>, kptben@aol.com (KPT Ben) wrote: > In article <48ihn2$e96@age.cs.columbia.edu>, > John Kasdan wrote: > > >I think it is generally true that for any m and n there exists a > >sequence of length m^n which contains all of the n letter words in m > >characters, (wrc.) (In fact, I am pretty sure I once heard Percy > >Diaconnis give a talk in which he demonstrated a card trick depending > >on such a sequence.) However, I don't remember how to construct the > >sequence. So I would appreciate it if anyone could tell me how the > >construction works, or give me a pointer to where I can find it > >in the literature. > > I once got this problem on a final exam in discrete mathematics, phrased > as follows: > > "A thief wishes to break into a house, protected by a numeric 4-digit > password. The alarm will switch itself on/off whenever the appropriate > code is entered. (The alarm has been reset in such a way that the first 3 > key presses cannot complete the code and switch off the alarm.) > > 1: Assume the alarm state is visible (a red/green indicator). What is the > shortest sequence of keys needed to be pressed to ensure that the red > light will turn green? (The brute-force method of entering all 10,000 > possible combinations (40,000 key presses) can be improved upon > substantially). > > 2: Suppose there is _no_ visible indication of the alarm's on/off state > (it is assumed to be initially on). Can the thief still break into the > house, without any risk of setting off the alarm? (assume he/she is a > sufficiently careful thief). > > Bonus: Show how to construct a sequence of the shortest possible length. > > > The first two are relatively easy, once you know the trick. The bonus is a > tad trickier; I can't remember off the top of my head how it's done. > > Good luck finding your solution! > > -- > Ben Weiss > Senior Software Engineer > MetaTools Inc. (formerly HSC Software) The sequences mentioned are called de Bruijn sequences after the Dutch mathematician N.G. de Bruijn, who solved the problem about the number of such sequences. Namely, for integers m,n, the number of sequences of length m^n such that each word of length n appears exactly once is equal to m^(n-1) (m!) . Here, we treat rotations of the same sequence as different (otherwise, we have to divide the number by m^n). There are several proofs, all using graph theory. One can define a digraph D(m,n) with the words of length (n-1) as its vertices and an arc from (a(1), ..., a(n-1)) to (a(2), ... , a(n)) for every set {a(1), ... , a(n)} of numbers between 1 and m. This digraph is called the de Bruijn (-Good) digraph. The problem may now be restated as follows: How many Eulerian tours (that is, cycles in the digraph using all arcs exactly once) are there in the digraph D(m,n)? (To prove that there _are_ Eulerian tours, one just have to prove that the digraph is Eulerian, i.e., that it is connected and that the number of arcs ending in a vertex always equals the number of arcs starting in the same vertex. The first condition is proved by constructing a path between every pair of vertices in the digraph. Namely, if the vertices are a = (a(1), ... , a(n-1)) and b = (a(n), ... , a(2n-2)), then the sequence (a(1), ... , a(2n-2)) corresponds to a path in the digraph such that the first vertex is a and the last vertex is b. The second condition is trivially true by definition. See below for further information.) This problem can be solved by the aid of the Tutte Matrix Tree Theorem and the BEST Theorem. Namely, for any digraph D, let M(D) be a matrix with a row and a column for every vertex in D and let m(ij), the element on position (i,j) in M(D), be equal to \delta_{i,j} * x(i) - a(i,j) where x(i) is the number of arcs ending in the vertex v_i corresponding to the i'th row and a(i,j) is the number of arcs from v_i to v_j. TUTTE MATRIX TREE THEOREM. The number of spanning directed trees in D with root vertex v_i is equal to the determinant of the matrix obtained from M(D) by removing the i'th row and column. BEST THEOREM. Put T(D,i) = the number of directed spanning trees with root v_i in D, E(D) = the number of Eulerian tours in D, d(v) = the number of arcs ending in v = the number of arcs starting in v (the last equality is a necessary condition for the following to hold if T(D,i)>0). Then _____ E(D) = T(D,i) . | | (d(v)-1)! v (the choice of i is hence immaterial). Those results are discussed in e.g. William T. Tutte, Graph Theory, Addison-Wesley Publishing Company (1984); the results themselves are rather old and published in journals not easily available. For example, The BEST Theorem is proved in Simon Stevin 28 (1951), 203-217 (Circuits and Trees in Oriented Linear Graphs by de Bruijn and T. van Aardenne-Ehrenfest). In Journal of Combinatorial Theory (1967), Donald E. Knuth showed how to prove the result by induction over n. Note that the determinant in the Tutte matrix tree theorem is not at all trivial to compute; in fact, one must use either an induction argument (see Knuth above) or some transformation matrix to simplify the computations. There are other ways of proving the result in the case where m=2. E.g., one may map the Eulerian tours in D(2,n) onto the Eulerian tours in D(2,n-1) in such way that each tour in D(2,n-1) corresponds to the same number of tours in D(2,n). Construction of an Eulerian tour in any Eulerian digraph is not difficult though cumbersome; consider any constructive proof of the existence of Eulerian tours in Eulerian graphs in any elementary graph theory book. Constructing a de Bruijn sequence without using any digraph is rather difficult; there are no _straightforward_ algorithms or nice formulas generating those sequences. There is something called a Feedback Shift Register (FSR). By the aid of an FSR with the right settings, one may generate de Bruijn sequences (or rather sequences of length one less than the length of the de Bruijn sequences; the (0...0)-word is often missing in applications). However, to find those settings, one has to work just as hard as if one wants to find a sequence by hand. What is an FSR? Considering m=2, it is a Boolean function f : B^n -> B, where B = {0,1}. By the aid of f and an n-word (a(1), ... , a(n)) we may construct a sequence by putting a(n+1) = f(a(1), ... , a(n)), a(n+k) = f(a(k), ... , a(n+k-1)). E.g., if f(x,y,z) = x+z, then f(0,0,1) = 1, f(0,1,1) = 1, f(1,1,1) = 0, f(1,1,0) = 1, f(1,0,1) = 0, f(0,1,0) = 0, f(1,0,0) = 1, so we obtain the sequence 0011101 which will be repeated infinitely often. FSR's are often used in cryptology to construct seemingly random sequences. However, they are less "random" than they seem to be. When f is linear, one may use a very elegant algorithm (Massey algorithm) to reconstruct the generating function f if one is given a sufficiently long part of the generated sequence (this part does not have to be so long, in general much much shorter than the period of the sequence). There is a book, Shift Register Sequences written by S.Goloumb (1967), with further information about FSR's. /Jakob Jonsson ============================================================================== From: clong@cnj.digex.net (Chris Long) Newsgroups: sci.math Subject: Re: Door combination lock Date: 28 Jan 1996 03:42:05 -0500 In article , Paul J. Campbell wrote: >Hugo is right. See >Discrete Algorithmic Mathematics, by Stephen B. Maurer and Anthony Ralston, >where the problem is investigated. Yes, the entity the original person asked about is well-known in mathematics as a de Bruijn sequence, and many graph theory textbooks should cover it (e.g. Chartrand and Oellermann's _Applied and Algorithmic Graph Theory_). Constructing de Bruijn sequences is actually quite simple. -- Chris Long, 265 Old York Rd., Bridgewater, NJ 08807-2618 http://www.webcom.com/~clong Score: 0, Diff: 1, clong killed by a Harvard Math Team on 1