12
$\begingroup$

There are two bacteria. Both of their DNA sequences are only one letter long:

 Bacteria #1 has the DNA sequence 'A'
 Bacteria #2 has the DNA sequence 'T'

Every minute, two things happen:

  • The bacteria mate. They produce a single child whose DNA is the concatenation of the DNA of its parents, in either order. Example: if AAT and T mate, the child would be either TAAT or AATT.

  • After the mating, one of the parents dies.

Prove that after any number of matings, both of the bacteria will have DNA sequences which are either palindromic or a concatenation of two palindromes.

Example, with explanation:

A      T         |  
A      AT        |  AT = A + T,           T dies
A      AAT       |  AAT = A + AT,         AT dies
AATA   AAT       |  AATA = AAT + A,       A dies
AATA   AATAATA   |  AATAATA = AAT + AATA, AAT dies

Note that AATA = A + ATA and AATAATA = A + ATAATA are both a concatenation of two palindromes.

Source: All Russian Math Olympiad, 2003, Final Round, Grade 11, Problem 4.
http://www.imomath.com/index.php?options=Rus&mod=23&ttn=Russia
http://imomath.com/othercomp/Rus/RusMO03.pdf


This puzzle has been posted here before, and was deleted because it did not provide attribution. I am posting again because it is an interesting, accessible puzzle, and I know at least one user was excited to share their solution.

$\endgroup$
  • $\begingroup$ Wouldn't A and AAT already be valid? $\endgroup$ – somebody Mar 2 '18 at 0:19
  • $\begingroup$ @somebody They are. The goal is to prove that they are always valid, not just find a single valid instance. $\endgroup$ – Mike Earnest Mar 2 '18 at 0:27
  • $\begingroup$ Does it need to be a mathematical proof? $\endgroup$ – somebody Mar 2 '18 at 0:37
  • 1
    $\begingroup$ @somebody It just needs to be a 100% convincing argument, so basically yes. $\endgroup$ – Mike Earnest Mar 2 '18 at 0:56
  • 2
    $\begingroup$ Last time this was posted, I took a shot at this puzzle. When I decided to drop it, I was well into my second sheet of paper and inventing the third layer of shorthand.. $\endgroup$ – Bass Mar 2 '18 at 13:06
3
$\begingroup$

At any point we have two strings $X$ and $X'$. Either, $X$ is a substring of $X'$, denoted $X \subset X'$ or vice versa. Assume that $X \subset X'$ which means we can write.

$$X \subset X' \implies X' = XU \text{ or } X' = UX.$$

(We repeat this process until we have replaced the substrings by $A$ and $T$)

Due to the circular-shift property outlined by @Tyler, we may consider one of the shifts, since we are doing substitution only -- iff property holds for one, it must hold for the other. So how can we assert that is this a concatenation of two palindromes?

Consider the following argument with symbols $\circ, *$. Suppose we have two palindromes

$$\underbrace{\circ \circ \cdots \circ}_{n_1} * \underbrace{\circ \circ \cdots \circ}_{n_2} * \cdots * \underbrace{\circ \circ \cdots \circ}_{n_k} | \underbrace{\circ \circ \cdots \circ}_{m_1} * \underbrace{\circ \circ \cdots \circ}_{m_2} * \cdots * \underbrace{\circ \circ \cdots \circ}_{m_j} $$

with $n_1 = n_k, n_2 = n_{k-1}, \ldots$ and $m_1 = m_j, m_2 = m_{j-1}, \ldots$.

If we replace $*$ by $\circ \diamond$ (which corresponds to the above $X' = XU$), we get

$$\underbrace{\circ \circ \cdots \circ}_{n_1+1} \diamond \underbrace{\circ \circ \cdots \circ}_{n_2+1} \diamond \cdots \diamond \underbrace{\circ \circ \cdots \circ}_{n_k+1} | \underbrace{\circ \circ \cdots \circ}_{m_1} \diamond \underbrace{\circ \circ \cdots \circ}_{m_2+1} \diamond \cdots \diamond \underbrace{\circ \circ \cdots \circ}_{m_j+1} \diamond \underbrace{\circ \circ \cdots \circ}_{m_j} $$

which is also two palindromes. When we get to the base case, we have substituted the strings with symbols $A$ and $T$ (or two length-$1$ strings if you will). Therefore it must be a palindrome or the concatenation of two.

Edit:

For clarification: if you doubt that $X' = UX$ also works:

$$\underbrace{\circ \circ \cdots \circ}_{n_1} * \underbrace{\circ \circ \cdots \circ}_{n_2} * \cdots * \underbrace{\circ \circ \cdots \circ}_{n_k} | \underbrace{\circ \circ \cdots \circ}_{m_1} * \underbrace{\circ \circ \cdots \circ}_{m_2} * \cdots * \underbrace{\circ \circ \cdots \circ}_{m_j} $$

Replace $*$ by $\diamond \circ$ (which corresponds to the above $X' = UX$), we get

$$\underbrace{\circ \circ \cdots \circ}_{n_1} \diamond \underbrace{\circ \circ \cdots \circ}_{n_2+1} \diamond \cdots \diamond \underbrace{\circ \circ \cdots \circ}_{n_k} | \underbrace{\circ \circ \cdots \circ}_{m_1+1} \diamond \underbrace{\circ \circ \cdots \circ}_{m_2+1} \diamond \cdots \diamond \underbrace{\circ \circ \cdots \circ}_{m_j+1} \diamond \underbrace{\circ \circ \cdots \circ}_{m_j+1}$$

which are two palindromes.

Edit to clarify:

I am doing backward induction from step $n$, reducing to the base case when the substrings are A and T, which occurs after $n-1$ steps.

The induction step starts with $X$ and $X'$, both are trivial substring palindromes (note: when we treat them as symbols, XXX and X'XX' are substring palindromes as well, even if they may not be real character-wise palindromes).

Then, after substituting $X' = X\|U$, we have two substring palindromes ATA...$\|$TTA... We are agnostic to what these strings are -- as mentioned before -- just think of them as symbols. The argument above shows that no matter how the substrings were constructed, we will end up with a substring palindrome. Now, in order to be certain it is also a real palindrome (not just a palindrome in terms of substrings), we need to make the substrings either

  1. real palindromes themselves, or
  2. single characters (trivial palindromes).

1) is not so easy to show, but 2) is since we can perform substitution all the way down to the first step where Bacteria #1 has sequence A and Bacteria #2 has sequence T.

$\endgroup$
  • $\begingroup$ I think you are thinking the same thing I am thinking, but it feels like your solution is missing some details. Why are you talking about replacing $*$ with $\circ\diamond$? $\endgroup$ – Mike Earnest Mar 7 '18 at 19:34
  • $\begingroup$ The symbols are representing substrings. Since at every step we may split one of the genetic strings into two substrings according to the above, we can see this as a substitution. I was only showing that no matter how we do the substitution and which of the two (current) strings we replace, we end up with two palindromes. $\endgroup$ – Carl Löndahl Mar 7 '18 at 19:38
  • $\begingroup$ This is what I did when I replaced $X' = XU$. I just used $\diamond, \circ, *$ to denote arbitrary substrings. $\endgroup$ – Carl Löndahl Mar 7 '18 at 19:41
  • 2
    $\begingroup$ I see. If the two strings at the end are X and X', then you there are four cases, one of which is X = X'U for some U. Then considering X' and U, you again have something like X' = UV for some V, so that A = UVU. Continuing, the result of the concatenations is the same as the result of a sequence of corresponding substitutions (in reverse order). Then you show these substitutions preserve 2-palindromes. $\endgroup$ – Mike Earnest Mar 7 '18 at 20:47
  • 1
    $\begingroup$ ^(should be X = UVU instead of A = UVU.) Anyways, nicely solved! $\endgroup$ – Mike Earnest Mar 7 '18 at 20:54
2
$\begingroup$

Not a complete solution, but here is something I noticed. Take any string formed in this way:

ATAATATAATAAT

Now shuffle it by taking any length from the end and moving it to the start:

ATAATATAATAAT $\Rightarrow$ ATAATATAATATA

It still has the property of being a palindrome or the concatenation of two palindromes. Also, you can shuffle it again and again ... shuffling changes where you start but not the order of the letters. It'll always be a concatenation of two palindromes. Furthermore, if you do choose the just the right shuffle:

ATAATATAATAAT $\Rightarrow$ ATATAATAATATA

This is an honest-to-goodness palindrome. And it is easy to see that any shuffle of a palindrome will yield at least a concatenation of two palindromes.


Let's try another sequence:

ATTTATTTATTATTTATT

This still has the property that any shuffle will be the concatenation of two palindromes. Alas, this one can't be shuffled to be a palindrome, since there are an even number of letters but an odd number of As and Ts. But we can still get close:

ATTTATTTATTATTTATT $\Rightarrow$ TATTATTTATTTATTATT

It's a palindrome with an extra "T" on the end. So I would conjecture that you always get a "shuffled palindrome" or something that is close enough.


Why is this not a complete solution? It's not automatically true that two concatenated shuffled palindromes are again a shuffled palindrome. But I was hoping it would help.

$\endgroup$
2
$\begingroup$

We prove by induction on n that the nth bacteria born has DNA which is a sum of two palindromes (one of which might be the empty sequence).

By symmetry, we can assume the first mating/death results in A and AT. From this point on, the DNA of every descendant will be built out of copies of A and AT. Let's use the symbol 'B' as shorthand for AT.

Let S be the DNA of the nth bacteria born in the process, and let S' be the letter sequence where we use B as shorthand for AT. Note that S' is the result of starting with the sequences 'A' and 'B' and applying the last n – 1 steps of the same mating process. Therefore, by induction, S' is either palindromic or the sum of two palindromes.

Write

S' = T' + R',

where T' and R' are palindromes. (If S' itself is palindromic, then T' is a sequence of zero letters, while R' is all of S'). Now, let T and R be the result of expanding all of the Bs in T' and R' back into AT. We then have that

S = T + R.

Unfortunately, T and R are not palindromes. T' and R' were palindromes, but the replacement B → AT created a slight asymmetry. To fix this, note that R is built from 'A' and 'AT', so that R starts with the letter 'A'. Removing this A from the front of R and adding to the end of T, creating T* and R*, we have

S = T* + R*

and both T* and R* are palindromes.


Example: Let

S = AAATAAATAAT

Take each AT and replace it with B:

S' = AABAABAB

By induction, this is a sum of two palindromes:

T' = AABAA   R' = BAB

Do the inverse replacement B → AT on T and R:

T = AAATAA   R = ATAAT

These are no longer palindromes. To fix this, move the A from the start of R to the end of T:

S = T* + R* = AAATAAA + TAAT

$\endgroup$
0
$\begingroup$

I haven't done a tone of proofs but here is my attempt.

A rule I'm using is something I noticed about palindromes, which is that a palindrome repeated indefinitely (like ABA + ABA + ABA...) is still a palindrome. Throughout this I use the + sign means "added to end here."

We start from child 1, which is two parent palindromes (P1 and P2) concatinated together.

P1 + P2 = C1

From here we can do four things. Add P1 to beginning, add P1 to end, add P2 to beginning or add P2 to end.

1) we add P1 to beginning
C2 = P1 + C1 = P1 + P1 + P2 Since any palindrome repeated is still a palindrome, this still works as palindrome + palindrome.

2) add P1 to end C2 = C1 + P1 = P1 + P2 + P1 This is obviously a palindrome

3) add P2 to beginning
C2 = P2 + C1 = P2 + P1 + P2
This is obviously a palindrome

4) add P2 to end
C2 = C1 + P2 = P1 + P2 + P2
Same as case 1.

Next, we test case 1 against 4 possible options from there.

1) C3 = C2(P1 + P1 + P2) + P1
This is clearly still two palindromes, the first being P1 and the second being P1 + P2 + P1.

2) C3 = P1 + C2(P1 + P1 + P2) This is also two palindromes, (P1 + P1 + P1) and P2.

3) C3 = C1(P1 + P2) + C2(P1 + C1(P1 + P2))= P1 + P2 + P1 + P1 + P2 This is two palindromes, P1 and the last 4. This could be written C1 + P1 + C1, or as C1 + C2.

Edit: corrected mistakes of and adding proof idea

4) C3 = C2(P1 + P1 + P2) + C1(P1+P2) = P1.+ P1 + P2 + P1 + P2. This is clearly still 2 palindromes, first 2 and last 3. This could be written P1 + C1 + C1.

All C's ultimate unravel to begin with P1 so u know automatically that anything P1 + C1 starts with a palindrome of one or more characters, depending on how many P1s in C1.

And you know that anything C1 + C1 will end in a palindrome that starts from (wherever the first character change is), and this goes for any C such that it is made of (palindrome + palindrome), which all C's will.

Therefor adding as many C1s to the end I'd you want will not change the status of start palindrome + end palindrome.....

$\endgroup$
  • 1
    $\begingroup$ Showing that it works for two or three generations is not a proof that it will continue to be so for the 100th generation for example. Once neither of the parents are palindromes it gets interesting. $\endgroup$ – Jaap Scherphuis Mar 3 '18 at 10:45
  • $\begingroup$ Yes that's true,hopefully someone else can clear this up. $\endgroup$ – Follow Mar 3 '18 at 11:43

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.