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