Suppose we were to take a finite alphabet of letters, say , and we considered all the possible ‘words’ of a given length. For instance, the worlds of length 2 are:
and there are many of these. Let’s denote the set of length- words using the alphabet by .
What I am interested in now is “For a given and , what is the minimum length string of letters I can write down and still be sure that every word in appears somewhere in it as a substring?”. Why might I be interested in such a thing? Because I really should be working on my PhD, that’s why.
contains every length-2 word of 2 letters, in order 01, 11, 10, 00. It’s of optimal length, too, because if we start with just ’01’ and successively add ‘1’, ‘0’, and ‘0’, we find that at every stage the newly added letter creates a new sub-word not previously seen, and so every element of appears exactly once. We cannot delete a letter to make a shorter string without losing one of the words. Similarly,
are examples of optimal tours through and respectively, as they both have this property that each letter added after the first adds a previously unseen word.
Notice I’ve introduced the terminology tour for any string that contains all words in a given , with optimal tour being the tour that is of minimum possible length for that and .
One of the interesting things about mathematics is that it allows us to reason about objects (like fractals, dimensionless points or infinite sequences) and processes (limits, the axiom of choice) that, while logically sound and often even intuitive, cannot actually exist or be feasibly carried out in real life. This is arguably one of the main reasons for a common popular view of pure mathematics as being “too theoretical”, aka. of no practical use. Admittedly this ability of what is known as “classical” mathematics to talk about infinities, infinitesimals and ambiguous choices has given rise to some strange results, like the notorious Banach–Tarski paradox, which informally says that a 3-dimensional ball can be divided into finitely many pieces and reassembled into two balls each identical to the original, or the Riemann rearrangement theorem, which states that a conditionally convergent real infinite series can be rearranged to converge to any real number whatsoever, or to .
Effective or not?
Both these theorems are statements about our ability to accomplish certain actions, and the proof of each consists of a description of a procedure to do so. So are these surprising results actually practicable in real life? The latter is; we can obtain an algorithm that, given a conditionally convergent series, rearranges its terms to either diverge or converge to a specified real number [BB09]. The former is not, as it relies on the axiom of choice to select points from an infinite number of sets, and while we can infer non-trivial things about the resulting set, there is no way for finite, mortal mathematicians to actually construct it. So while both theorems are statements of the logical possibility of accomplishing a certain seemingly impossible task, only the rearrangement of the infinite series to converge to any sum is “physically” possible; the feasibility of cutting an orange into five pieces and putting them back together to get two oranges remains firmly in the realm of logic, out of the material world.
This illustrates a subtle but important distinction between the procedures described in the respective proofs. We say that there is an effective procedure for the series rearrangement problem: for any conditionally convergent series the procedure always terminates in a finite number of steps and returns the desired result, a permutation of the terms of the series which sums to a given number, or diverges. This is characteristic of what we call effective procedures in general: a series of instructions guaranteed to end in a finite number of steps, always returning a correct result. The procedure for decomposing a 3-ball into a finite number of pieces and reassembling them into two identical 3-balls is a non-effective process; since an infinite number of selections must be made in order to obtain those pieces in the first place, we can never hope to actually get our hands on any of the pieces, much less reassemble them!
Guessing numbers in a random real sequence
I would like to discuss another example of a non-effective procedure which “enables” us to accomplish an impossible feat. Consider the following
Problem. A house has a hundred rooms. In each room are an infinite number of boxes labelled with the natural numbers , each containing an arbitrary real number. The rooms are identical, so that in each room the -th box always contains the same number. We kidnap a hundred mathematicians and into each room send one, where they are allowed to open up boxes to reveal the numbers inside. They may open as many boxes as they like (possibly infinitely many) as long as at least one box is left unopened. Each mathematician’s task is to guess the number inside a particular unopened box of their choice. They know that the rooms are identical, and once they have been sent into the rooms no further communication is allowed. Before they are sent to the rooms they are given a chance to discuss a strategy.
Find a strategy that will enable at least 99 of the 100 mathematicians to correctly guess their real number. Continue reading