Ernie and the Alien Invasion

Question

Yesterday I dropped in on Ernie to show off my new j-watch. Ernie wouldn't be impressed by instant wrist-mounted access to social media sites like me-tube, tweeter and farce-book so I thought I would concentrate on it's technical aspects - 1024 GB RAM, green-tooth, USB5, high-res touch screen and 6G networking. As he brewed us coffee I demonstrated the trump-card of the j-watch: its 8K UHD camera - 120 FPS at 7680x4320 pixels, with surround-sound directional microphones! In my enthusiasm I must have bored myself to sleep because the next thing I remember was waking to hear Ernie complaining that his coffee was cold. I was late for an appointment and had to leave in a hurry.

At least that is what i thought happened until this morning! After breakfast I tried to use the j-watch's Memo app to remind myself to buy eggs. To my dismay the watch just displayed a flashing "MEMORY FULL" warning. It didn't take long to find the problem - a massive 1023.9 GB MP5 file. I realized that I must have left the camera running when I fell asleep at Ernie's. I was going to delete it but thought I would review the first few minutes to see the picture quality. The following is a precis of what I saw and heard:

Picture: A shaky (but crystal clear) view of my face in close-up as my voice explains the magnificence of my j-phone in exuberant detail. Ernie puts two cups of coffee on the table. The next 30 seconds is blanked out as my sleeve drops down over the camera's lens while recording. (I began to wonder at the practicality of a wrist-mounted camera and if the added expense of the UHDV camera had been worth it. I was just about to delete the file when...) The sound of Ernie's door-bell can be heard on the sound-track. ("Curious", I thought, "I can't remember any visitors").

Me: "I'll get it" (This was really weird - I definitely couldn't remember answering the door!).

Picture: Door opens, momentary view of two men in wrap-around dark glasses and black suits; sleeve slides back down to block camera again.

Me: "Not to be rude - but whatever you are selling, we don't want any".

MIB1: [Pushing his way somewhat rudely into the hall] "We are from MIB - it is imperative that we speak to Professor Ernie immediately!".

Me: "MIB - are you the Men in Black?"

MIB2: "Don't be ridiculous - we are from the Ministry of Interstellar Bureaucracy". [The two men greet Ernie and explain that the Ministry was created when an alien-manufactured Tachyon wave radio receiver and universal translator were discovered in the wreckage at area 63! Apparently, the galaxy teems with a multitude of intelligent species. Until recently the radio hadn't provided any useful information to aid mankind as the only signal was live coverage of rather boring Interstellar Council meetings dealing with minor issues such as spiral-arm planning consents and sales taxes on micro-black-holes. But just a few hours ago a very worrying message was heard. An Eviction Notice had been lodged at the Council by a race of carnivorous lizard-people. They were planning to return to their home planet after a 'temporary' absence of ~64 million years (some sort of problem with the environment after a failed attempt at asteroid mining) but discovered the planet was 'infested by bald tailless apes'].

MIB1: "We realized they were talking about us - humankind!"

Ernie: "Eviction - that doesn't sound very nice"

MIB2: "We fear the worst. The lizard-men have a mass of heavily armed and technologically advanced worm-hole drive space ships ready and waiting - they can be here within hours of the court giving consent."

Me: "Has the court made a decision yet?"

MIB1: "No. One of the council members reminded the lizard-men that parts of Earth had been declared a wild-life refuge."

Me: "A refuge for bald tailless apes?"

MIB2: "No - for a rare species of woodlouse that lives in the rain-forests of Sumatra. Seems that it bears a slight genetic similarity to the councilor's distant ancestors. And it is only a temporary reprieve. The lizard-men only need to confirm they are willing to comply with a list of Intergalactic Environmental Laws. Then the 'eviction' can commence immediately. Ernie - we want you to invent a Tachyon transmitter so we can contact the court and make an appeal - our best lawyers are already preparing their arguments".

Ernie: "Well I'll do what I can. But I always work best when I multi-task, so tell me more about these environmental laws while I think". [The MIB's go on to explain that the Galactic Empire operated under a binary legal system with two laws labelled '1', and '2'. Of course things were a bit more complicated than that, as each law had two sub-clauses '11', '12', '21', and '22', and each of these had two sub-sub-clauses '111', '112' ... '221', '222' and so on to deeper and deeper levels of sub-sub-sub...sub clauses].

MIB1: " The court requires written confirmation that the lizard-men will obey all relevant laws in a list defined by a special Environmental Law Identification Algorithm."

Ernie: "An algorithm, tell me more!" [The MIBs described the algorithm as follows...]

The first relevant sub-clause is the one labelled '1111111'  

Each next relevant sub-clause is the one with a label:
   a) that is one digit longer than that of the previous sub-clause
   b) which contains no previously identified label as a sub-sequence 
   c) that is the alphabetically first label complying with a) and b) above.

Ernie: "So the first few clauses to be tested would be..."[the sound of a white-board marker squeaking]

Picture: a momentary view of the white-board before my sleeve slips down over the lens again as I scratch my itchy nose - (I am allergic to stress - it always makes my nose run).

 1     1111111
 2     11111122
 3     111112212
 4     1111122221
 5     11111222222
 6     111122122222
 7     1111222212221
 8     11112222212222
 9     111122222221212
10     1111222222221221
11     111...

Ernie: "...and when the Lizard-men reach the last sub-clause the court will accept the eviction order?"

MIB1: "Precisely! But the lizard-men are already way past that point on the list - they and the council are using super-fast quantum computing legal engines to write and test their legal arguments, it takes precisely one second for each sub-clause to be accepted. So as you can imagine, we don't have much time to make contact with the court and send an appeal!" [long pause with just the sound of Ernie humming to himself as he does when he is thinking hard, plus me sneezing more and more]

Ernie: "To be honest, I don't know the first thing about how to build a tachyon transmitter but I can tell you that the last sub-clause the lizard-men have to satisfy will have a label of the form..." [sound of white-board marker again, but my sleeve is still in the way and the picture is blank]

Ernie: "...and I recon that the time it will take before the last sub-clause is reached will be about ..." [at that very moment my allergy strikes again and Ernie's next words are drowned out on the sound-track by an enormous sneeze]

MIB1: "We need to get this information back to the Ministry immediately. My apologies, but to maintain security we now need to use the brain scrambler we found in the wreckage to delete your memory of our visit. This won't hurt a bit..." [a momentary buzz on the sound-track and the video image fills with static for a few seconds, then the sound of footsteps heading off. Followed by a few minutes of quiet snoring then...]

Ernie: "Dang - I must have dozed off - and now my coffee is cold".

Picture: My face (in unflattering close-up) appears as I pull back my sleeve to check the time.

Me: "And I am late for my meeting in town..." [video ends with Memory Full warning]

So here is my problem - I just rang Ernie and he doesn't have any memory of the visitors. I tried to explain but he thinks I just had a bad dream and won't take me seriously. I would show him the video but I think the brain scrambler may have damaged my watch because now it just displays a "file not found" message. Should I try and find a hiding place right now to escape from an imminent invasion, or is it better to try and convince people to make preparations to repulse the lizard-men and protect themselves?

Can anyone let me know what the number of the last sub-clause will look like and how much time I have to prepare for the invasion of the lizard-men?

Click on the link to confirm what I mean by subsequence

Answer 1

The last sub-clause must be:

all twos: $222...2$.

To prove that, we need to show that (a) it is always possible to have such a sequence as long as there wasn't such a sequence before, and that (b) once we used such a sequence we can't have any more sequences.

(a) is true because, as long as we only had sequences with at least one $1$ in them, none of them can be a sub-sequence of the last one - it has no $1$'s. (b) is true because, having used a sequence of $N$ $2$'s means that we couldn't have used a sequence with any $1$'s (otherwise we would have used it, as it comes first alphabetically). So there is no option for a $(N+1)$-long sequence - either it has $N$ $2$'s, or it has an $N$-long sub-sequence with at least one $1$'s, which we already know is not allowed.

---

It will be

over 72 million years

before the Lizard-men can begin their eviction.

I'm very much building on John Stevens' answer, and I'll be using the terms that are defined there.

Consider these extra tier-$n$ suffixes: all $2$'s apart from up to $(6-n)$ $1$'s in the last $(7-n)$ places.

Why are these suffixes allowed? Such a suffix makes a sub-clause, $S$, of the form $1^{(n)}2^{(m)}s$, where $s$ is of length $(7-n)$ and has up to $(6-n)$ $1$'s. The middle part, $2^{(m)}$, is 'useless' in checking whether $S$ is forbidden, as any previous-tier sub-clause needs at least $n+1$ $1$'s before a $2$. So only $7$ characters out of $S$ are relevant, and therefore only the first sub-clause can possibly be a sub-sequence of $S$. But the total number of $1$'s in $S$ is smaller than $7$, and therefore the first sub-clause cannot be a subsequence either, and $S$ is not forbidden.

Why are these suffixes different to John's? John's suffixes, of the form $2^{(d)}2^{(b)}12^{(c)}S_{(k-1)}$, all have a single $1$ outside of the last $a_{(n+2)}$ places, and these extra ones don't $(a_{(n+2)} > n)$. So all of these extra suffixes are new ones. In fact, they will always appear after John's sub-clauses.

Therefore, apart from John's $\frac{1}{2} K_{(n+1)}(K_{(n+1)} + 1)$ suffixes, there are another $\sum_{k=0}^{6-n}{7 - n \choose k}$.

Let's demonstrate this for tier-$4$. Here are all the sub-clauses up to this point:

 1    1111111
 2    11111122
 3    111112212
 4    1111122221
 5    11111222222
 6    111122122222
 7    1111222212221
 8    11112222212222
 9    111122222221212
10    1111222222221221
11    11112222222221222
12    111122222222222112
13    1111222222222222121
14    11112222222222222122
15    111122222222222222211
16    1111222222222222222212
17    11112222222222222222221
18    111122222222222222222222

(Note that tier-$4$ is actually 13-long rather than 10, which already increases the bound. But this is not the point.)

Sub-clauses 6-11 are constructed in John's way. Indeed, one of the first three characters of the suffix is always $1$, and the two last characters are always a tier-$3$ suffix. Sub-clauses 12-18 are the new ones - they only have up to 2 $1$'s (apart from the prefix), all in the last 3 places.

Let's re-calculate $K_0$ according to this:

\begin{align} K_3 &\ge \frac{1}{2} K_4 (K_4 + 1) + \sum_{k=0}^{3}{4 \choose k} = \frac{13*14}{2} + 15 = 106 \\ K_2 &\ge \frac{1}{2} K_3 (K_3 + 1) + \sum_{k=0}^{4}{5 \choose k} = \frac{106*107}{2} + 31 = 5702 \\ K_1 &\ge \frac{1}{2} K_2 (K_2 + 1) + \sum_{k=0}^{5}{6 \choose k} = \frac{5702*5703}{2} + 63 = 16259316 \\ K_0 &\ge \frac{1}{2} K_1 (K_1 + 1) + \sum_{k=0}^{6}{7 \choose k} = \frac{16259316*16259317}{2} + 127 = 132182686523713 \end{align}

Obviously, the extra suffixes become negligible at low-$n$ tiers, but the accumulative effect is great.

In addition, I wrote a function to generate the first tiers of the series of laws. It's a nice programming challenge, and I used John's observations about the prefix and the centre to make it efficient. The function doesn't assume anything about the possible suffixes, though, but checks all possibilities (efficiently). I put the function at the bottom.

The function gives $K_3 = 141$, $K_2 = 11623$. The highest bound I can give is according to this $K_2$:

\begin{align} K_1 &\ge \frac{1}{2} K_2 (K_2 + 1) + \sum_{k=0}^{5}{6 \choose k} = \frac{11623*11624}{2} + 63 = 67552939 \\ K_0 &\ge \frac{1}{2} K_1 (K_1 + 1) + \sum_{k=0}^{6}{7 \choose k} = \frac{67552939*67552940}{2} + 127 = 2281699817545457 \end{align}

At one second per sub-clause, this will take:

over 72 million years.

Here's the Python function ('calculate_chain' should be used. It calls the recursive 'generate_suffixes'):

def generate_suffixes(suffix, i, previous_tiers, sub_lens, res):

    if i == len(suffix):
        res.append(suffix[:])
        return
    vals = [False, True]
    for v in vals:
        suffix[i] = v
        new_sub_lens = []
        for x in range(len(previous_tiers)):
            new_sub_lens.append(sub_lens[x] +
                                (previous_tiers[x][sub_lens[x]] == suffix[i]))
            if new_sub_lens[x] == len(previous_tiers[x]):
                break
        else:
            generate_suffixes(suffix, i + 1, previous_tiers, new_sub_lens, res)
    return res

def calculate_chain(n_falses=7, min_l_prefix=2):

    res = [[False] * n_falses,
           [False] * (n_falses - 1) + [True] * 2]
    l_prefix = n_falses - 2
    l_suffix = 2
    max_falses = 1
    while l_prefix >= min_l_prefix:
        suffixes = generate_suffixes([False] * l_suffix, 0, res, [l_prefix] * len(res), [])
        for s in range(len(suffixes)):
            res.append([False] * l_prefix + [True] * (2 + s) + suffixes[s])
        l_suffix = len(res[-1]) - l_prefix
        l_prefix -= 1

    return res

Answer 2

It will be

at least 22000 years

before the Lizard-men can begin their eviction.

The sequence of sub-clauses they must obey is finite, by Higman's Lemma.

The number of the last sub-clause has the form

all twos: $222...2$

by the argument in Angkor's answer.

I'll divide each clause into three parts:

• the $1$-prefix, of the form $1^{(n)}$, consisting of the substring of all the $1$s at the beginning of the clause. The $1$-prefix may be empty. Claused will be divided into tiers based on the length of the $1$-prefix. A tier-$n$ clause has $1$-prefix of length $n$.
• the central part, $C$, of the form $2^{(m)}$, which immediately follows the $1$-prefix
• the suffix, $S$, consisting of the remainder of the clause. $S_k$ indicates the suffix of the $k^{th}$ clause in a tier

All clauses have the form $1^{(n)}2^{(m)}S$, for some (possibly $0$) values of $n$ and $m$.

Call a clause or subsequence of a clause forbidden if it contains a previous clause as a subsequence.

Some observations:

---

Observation 1: The length of the $1$-prefix never increases.

This can be seen by applying the argument in Angkor's answer to just the substring of each clause starting from the first $2$ to the end of the clause. This shows that the index of the first $2$ cannot increase, and thus the $1$-prefix length cannot increase.

Since the $1$'s-prefix length does not increase, then the tier of the clauses int he sequence does not increase. The sequence of clauses will consist of all the tier-$7$ clauses (just $1111111$), then all the tier-$6$ clauses, then the tier-$5$ clauses, and so on down to the tier-$0$ clauses, which are those that start with a $2$.

---

Observation 2: The final clause in tier-$n$ is of the form $1^{(n)}2^{(a_n)}$ for some $a_n$

This again follows from applying Angkor's argument to the substring starting from the first $2$. $a_n$ is the number of $2$s in the final clause of tier-$n$, and has a different value for different tiers.

---

Observation 3: The first $1$ in a clause in tier-$n$ after the $1$-prefix must occur no more than $a_{n+1}$ places from the end of the clause.

Suppose this were not the case. Then such a clause clause would have the form $1^{(n)}2^{+}1X$, where $2^+$ indicates a string of one or more $2$s and $X$ is some string of $1$s and $2$s of length at least $a_{n+1}$. This clause has a subsequence of the form $1^{(n+1)}Y$, with $Y$ of length $a_{n+1}$. This is formed by removing all of the $2$s between the $1$-prefix and the next $1$, and taking $Y$ as some subsequence of $X$ of length $a_{n+1}$. This subsequence has length $(n+1) + a_{n+1}$, the same as the final clause in tier-$(n+1)$.

This subsequence is forbidden. If it is identical to the final clause in tier-$(n+1)$, then it is clearly forbidden. If it is not, then $Y$ contains at least one $1$, and thus this subsequence comes earlier alphabetically than the last clause of tier-$(n+1)$. This clause must have been forbidden at that point in the sequence of clauses, or else it would have been used there instead of the clause of the form $1^{(n+1)}2^{(a_n)}$.

---

I'll now define the suffix $S$ of a clause in tier-$n$ to be of length $a_{n+1}$. This is possible based on the previous observation and the definition of the center of a clause as a string of $2$s between the $1$-prefix and the suffix. Only the suffix can contain a $1$ outside of the $1$-prefix, and such a $1$ can be no more than $a_{n+1}$ places from the end of the clause. Thus, I define the suffix to be the part of a clause that may contain a $1$ outside of the $1$-prefix.

---

Observation 4: Suffixes for clauses in the same tier appear in alphabetical order.

Suppose in tier-$n$ we have clauses $X_a$ with suffix $S_a$ and $X_b$ with suffix $S_b$, $a<b$, but $S_b$ comes before $S_a$ alphabetically. Generate a new clause $X'_a$ by replacing $S_a$ with $S_b$ in $X_a$. $X'_a$ is a subsequence of $X_b$, and so is allowed if $X_b$ is allowed, but it comes before $X_a$ alphabetically, and so would have been used instead of $X_a$ if allowed. Therefore, suffixes within a tier appear in alphabetical order.

---

Observation 5: The length of the center, $C$, of the $k^{th}$ clause in tier-$n$ is $k+1$.

All clauses in tier-$n$ are of the form $1^{(n)}2^{(m)}S$. $n$ is fixed within a tier, and the length of $S$ is fixed within a tier. Since the length of the clauses must increase, the length of the center of the clause must increase, since it is the only part of the clause not fixed in length. In particular, since the final clause of tier-$(n+1)$ is of the form $1^{(n+1)}2^{(a_{n+1})}$ and has length $n + a_{(n+1)} + 1$, the length of the first clause in tier-$n$ must have length $n + a_{(n+1)} + 2$. The $1$-prefix has length $n$, the suffix has length $a_{(n+1)}$, so the center must have length 2 = $k+1$.

In general, the $k^{th}$ clause in tier-$n$ must have length $n + a_{n+1} + k + 1$, so the center of that clause must have length $k+1$.

As a consequence, if there are $K_n$ total clauses in tier-$n$, then $a_n = K_n + 1 + a_{n+1}$.

---

Observation 6: If a clause $X_a$ with suffix $S_a$ in tier-$n$ is contained as a subsequence in another tier-$n$ clause $X_b$ with suffix $S_b$, then $S_a = S_b$.

$X_a$ has the form $1^{(n)}2^{(m_a)}S_a$, and $X_b$ has the form $1^{(n)}2^{(m_b)}S_b$, with $m_a<m_b$. $1^{(n)}2^{(m_b)}$ clearly contains $1^{(n)}2^{(m_a)}$ as a prefix, so if $X_a$ is a subsequence of $X_b$, then $S_a$ is a subsequence of the remainder of $X_b$, which is of the form $2^{(m_b-m_a)}S_b$. This is just $S_b$ with a number of extra $2$s prepended. Since $S_b$ comes after $S_a$ alphabetically by observation 4, these extra $2$s don't need to be used, and so $X_a$ is a subsequence of $X_b$ only if $S_a$ is a subsequence of $S_b$. Since the length of $S_a$ and $S_b$ are the same, this implies that $X_a$ is a subsequence of $X_b$ only if $S_a=S_b$.

---

All of the interesting variation of the clauses within in tier happens in the suffix of each clause. We can now look at bounding how many allowed suffixes are in tier-$n$. It turns out that we can construct allowed suffixes of clauses in tier-$n$ from clauses in tier-$(n+1)$.

Observation 7: If $CS$ is the concatenated center and suffix of a clause in tier-$(n+1)$, with $C$ of the form $2^{k+1}$, then we can construct $k$ valid suffixes for clauses in tier-$n$.

Let $S_k$ be the suffix for the $k^{th}$ clause in tier-$n+1$. Then consider strings $\hat{S}$ of the form $2^{(d)}2^{(b)}12^{(c)}S_k$, where $b+c=k$, $c>0$, and $d$ is chosen so that the length of the string is $a_{(n+1)}$. These strings are formed by changing one of the $2$s in the center (except the last one) to a $1$, then padding with enough $2$s so that the length is equal to the suffix length for tier-$n$. For each $S_k$, there are $k$ of these strings, and all of them are unique. This is a total of $\frac{K_{(n+1)}(K_{(n+1)}+1)}{2}$ candidate suffixes for tier-$n$.

For tier-$n$ clauses of the form $1^{(n)}2^{(m)}\hat{S}$, no clause in a higher tier can be a subsequence. Such clauses have the form $1^{(n)}2^{(b)}12^{(c)}S_k$, with $c<k+1$. All clauses in higher tiers begin with at least $n+1$ $1$s, so the first run of $2$s will not be used in any forbidden subsequence. A forbidden subsequence must be a subsequence of $X'=1^{(n+1)}2^{(c)}S_k$. $c$ was chosen to be less than $k+1$. The clause $1^{(n+1)}2^{(k+1)}S_k$ appears in tier-$(n+1)$, and so is not forbidden, and has $X'$ as a subsequence, so $X'$ cannot be forbidden.

Each $\hat{S}$ was chosen to be unique, so by observation 6, no clause in tier-$n$ can contain another as a subsequence. Therefore, every one of these candidate suffixes can appear in tier-$n$. There may be additional possible suffixes that do not take the specified form, but this should be sufficient to establish some bounds.

---

We can now put a bound on the total number of clauses. Let's manually compute some possible clauses in tier-$4$:

 6     111122122222
 7     1111222212221
 8     11112222212222
 9     111122222221212
10     1111222222221221
11     11112222222221222
12     111122222222222122
13     1111222222222222212
14     11112222222222222221
15     111122222222222222222

We can inspect that $K_4=10$ (NOTE: Angkor's update shows that I missed some tier-$4$ clauses and that $K_4$ is actually $13$. My estimate can still be computed on the assumption that $K_4$ is at least $10$). From there, we can compute the following bounds:

$K_3\ge\frac{K_4(K_4+1)}{2}\ge\frac{10\cdot11}{2}=55$

$K_2\ge\frac{K_3(K_3+1)}{2}\ge\frac{55\cdot56}{2}=1540$

$K_1\ge\frac{K_2(K_2+1)}{2}\ge\frac{1540\cdot1541}{2}=1186570$

$K_0\ge\frac{K_1(K_1+1)}{2}\ge\frac{1186570\cdot1186571}{2}=703974775735$

At one second per clause, it will take

at least 22300 years

to process every clause. And this isn't a tight bound, since at the very least we didn't include the clause of the form $1^{(n)}2^{(m)}$ in the estimate! It will likely be

significantly longer than that. Anyway, I'm not worried about an impending lizard-man invasion. And hopefully humanity can invent a tachyon transmitter sometime in the next twenty millenia and file an appeal.