Music on the planet Alpha Lyra IV consists of only two notes, called A and B. Also, songs never include three consecutive repetitions of any sequence nor does BB ever occur. A sequence of notes can have 1 or more notes in it.

What is the longest song on Alpha Lyra IV?

Since no one has provided more than a claim at an exhaustive proof that there is a limit, let me provide the following line of reasoning:

Any time a B occurs, it must be followed by an A, since BB can never occur. Also, since AAA itself is repititions of the sequence A, every song must be comprised of just two building blocks: BA and BAA, with the entire song possibly beginning with A or AA and/or ending in a single B.

Let's let a 0 represent BA and 1 represent BAA. Now, this is not a complete level of abstraction, as the sequence BABABAA contains BABABA, which is obviously three successive repitions of the sequence BA. So, in the 0/1 representation, we can never have a 001 appear. Any other arrangements that do not contain a triple recurrence of the 0s and 1s themselves will not contain a triple recurrence of the Bs and As they represent.

Thus, since 001 is specifically excluded, and 000 is of course a violation of the rules, then neither a 0 nor a 1 could follow 00. That means that any song cannot contain the sequence 00, except possibly once at the end.

So, the new task is to create a song of 0s and 1s, which does not contain any subsequence of 0s and 1s repeated three consecutive times, and which does not contain 00. This new problem is exactly the same as we started with, except now each 'note' is 2-3 times the size of they were originally. If, say, we let X represent 01 (which is BABAA) and Y represent 011 (BABAABAA), we would by the same reasoning come up with another abstraction of the problem, but where each piece is substantially larger.

Continuing to do this will result in larger and larger 'notes' to work with, and we will eventually be able to create a scenario in which each note we are looking is of some arbitrary length of Bs and As.

So, what's the flaw with this argument?

Posted by DJ on 2004-12-15 03:58:52