11
$\begingroup$

I've found a very interesting problem that I want to share with you.

In the planet Abbab, the alphabet consists only of the letters A and B.
All the sentences are written without spaces between words, and each sequence of letters has a determined meaning.
The postmen, though, refuse to deliver messages which contain two consecutive A.
So, the inhabitants of Abbab have to manipulate their messages in a way that prevents the presence of two consecutive A in their text. Both the sender and the addressee know the algorithm, so there's nothing to decrypt. Of course, their conversion method must be reversible, otherwise the addressee wouldn't be able to read the original message!

  1. Show a possible conversion algorithm which can convert a message of $N$ letters into a sendable message of up to $\frac5 3N$ letters
  2. A skilled programmer claims to have a very efficient program for long messages: every message of $N$ letters ($N\geq100$) can be converted into a sendable message of up to $\frac6 5 N$ letters. Show that the software programmer is lying.
$\endgroup$
  • 1
    $\begingroup$ There once was a place named Abbab, / whose alphabet had a strange theme. / But also, it seems, / although it sounds drab, / an even more strange rhyming scheme. $\endgroup$ – Joe Z. Mar 27 '15 at 0:01
  • $\begingroup$ Sounds like a strange flipped mix of 8b/10b or 64b/66b encodings, or maybe Manchester, designed to avoid DC bias and/or guarantee some clock transitions $\endgroup$ – Nick T Mar 27 '15 at 6:02
20
$\begingroup$

1.Split the input into blocks of size 3. Make the following encryption :

  • AAA : BBBBB
  • AAB : BBBAB
  • ABA : BBABB
  • ABB : BABBB
  • BAA : ABBBB
  • BAB : BABAB
  • BBA : ABBAB
  • BBB : ABABB

This leaves us with what to do with the last 1 or two possible characters. This is easily accomplished with:

  • A : A
  • B : B
  • AA : ABA
  • AB : AB
  • BA : BA
  • BB : BB

It is easy to see that this encryption is easily invertible, and that total length of encrypted message is at most 5N/3.

  1. Number of N-length AB-strings is 2^N. Number of N-length AB-strings without AA as substring is F(N+2) where F(i) is the ith Fibonacci number. Since Fibonacci numbers grow as $\phi^N$ and $\phi^{(6/5)}<2$, the number of N-length AB-strings grows asymptotically faster than (6N/5)-length AB-strings without AA as substring. Hence the second claim is impossible.
$\endgroup$
  • 2
    $\begingroup$ Clear, fast and brilliant answer! Very good! $\endgroup$ – leoll2 Mar 26 '15 at 19:23
3
$\begingroup$

We can write an algorithm which is, in some sense, optimal - reaching, in the limiting case (since this number is obviously$^*$ irrational) the bound that at least $\log_{\phi}(2)N$ characters must be used for infinitely many input words - which is implied by the fact that, as mentioned in a previous answer, there are $F_n\sim \phi^n$ legal words of length $n$, but $2^n$ possible words.

A very simple method is this:

Order all the possible message by their length; i.e. to each message word, assign a natural number such that longer messages have higher numbers. Do the same for the legal messages. Find where your message lies in the list - send the corresponding legal message; i.e. if you want to send the $n^{th}$ message, encode it as the $n^{th}$ legal message.

It's obvious that this is effective, since we're essentially constructing a bijection from . In fact, any method can be thought of as an injection from the set of messages to the set of legal messages, and it is easily shown$^{**}$ that any other injection aside from the one above has that the there is some $n$ such that the $n^{th}$ message maps to the $m^{th}$ legal message where $m>n$ - so any other algorithm performs at least as bad on at least one word.

In particular, one can see that saying a message $M$ is the $n^{th}$ message if the binary representation of $n$ with its most significant bit dropped is the same as the message $M$ with $A$'s replaced by $1$ and $B$'s by $0$. So "ABBABA" (which means "hello" in Abbab) encodes as the $1100101_2=101^{st}$ word.

Then, our method for determining the $n^{th}$ legal message is very similar, but instead of using binary, we use a positional system where the place values are the Fibonacci numbers rather than powers of two - in particular, every number can be written uniquely as the sum of distinct non-consecutive Fibonacci numbers. Letting $F_n$ be the greatest number included in such a sum, we simply put an $A$ for each time we see an element of the sequence $F_{n-1},F_{n-2},\ldots,F_1$ included in the sum and a $B$ otherwise. For instance, the $101^{st}$ legal word can be found as $$101=89+8+3+1=F_{10}+F_5+F_3+F_1$$ which encodes as, starting by noting that $F_9$ through $F_6$ are not included: "BBBBABABA".

So, as long as the residents of Abbab have too much time or the ability to program computers (in esoteric languages of course - they want to send their code in the mail unencrypted, so it looks kind of weird), they can use this system which will outperform any replacement algorithm (since their efficiency is rational and no better than $\log_{\phi}(2)$).

$^*$Were it rational, $\phi^a=2^b$ for integers $a$ and $b$, but $\phi^a$ is only rational if $a=0$ which implies $b=0$, which does not correspond to a rational number $a/b$.

$^{**}$Suppose this were not true; then, the $n^{th}$ message maps to the $m^{th}$ legal message. However, the first message must then map to the first legal one - and the second message must map to the second, since the first was already taken. Proceeding inductively, we prove that the $n^{th}$ message maps to the $n^{th}$ legal message.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.