Polymers

Let us define a polymer like described here: https://adventofcode.com/2018/day/5

A polymer is formed by smaller units which, when triggered, react with each other such that two adjacent units of the same type and opposite polarity are destroyed. Units’ types are represented by letters; units’ polarity is represented by capitalization. For instance, r and R are units with the same type but opposite polarity, whereas r and s are entirely different types and do not react.

For example:

• In aA, a and A react, leaving nothing behind.
• In abBA, bB destroys itself, leaving aA. As above, this then destroys itself, leaving nothing.
• In abAB, no two adjacent units are of the same type, and so nothing happens.
• In aabAAB, even though aa and AA are of the same type, their polarities match, and so nothing happens.

Now, consider a larger example, dabAcCaCBAcCcaDA:

1. dabAcCaCBAcCcaDA The first ‘cC’ is removed. dabAaCBAcCcaDA
2. This creates ‘Aa’, which is removed. dabCBAcCcaDA
3. Either ‘cC’ or ‘Cc’ are removed (the result is the same). dabCBAcaDA
4. No further actions can be taken.

After all possible reactions, the resulting polymer contains 10 units.

We are not going to solve the question in the link, although that is a very interesting question, but we are going to solve a different one:

What is the shortest polymer that can be formed with all 26 letters such that the polymer is fully destroyed when all occurrences of any single letter, -upper and lower case- are removed.

An alternative way to frame this question is this:

How to hang a picture with 26 pins such that if one pin is removed, the picture falls on the ground, in the least amount of windings possible.

Our polymer is equivalent to this is we give each pin a letter and make sure that left windings around the pin are lowercase and right windings are uppercase.

First, we can see that all polymers are element of the 26th order free group, with the lower case letters the 26 generating elements and the upper case letter their inverse.
Secondly, we can see that removing a letter is similar to replacing this letter with unity.

If we look at a system with only two letters. To have the property to remove everything if one letter is removed, we can make the following observations:

• Letters never commute with each other.
• Letters always commute with unity.

This means that the cummutator ABab, which is only equal to unity if the two elements commute, perfectly equals the polymer we need.

Now, how can we extend this to larger cases? When we nest the commutator, like for example $[[a,b],c]$ we can easily see that wherever the commutator becomes unity, all commutators containing this polymer also become unity. This means that our final polymer is composed of nested commutators. Instead of writing this as commutators, we can write this as proper binary trees. For example, the $[[a,b],c]$ case can be written as:

The number below the polymer is always its length.
Now, each graph with 26 leaves will create a valid polymer, but some graphs will do this way more efficient than others. Compare for example these two polymers:

One of them has a length of 16 while the other has a length of 22.
We see that each branch has a length of twice the sum of its children. This means that if $x_i$ is the depth of each leaf, the total length will be $\sum 2^{x_i}$. Besides, for any proper binary tree $\sum 2^{-x_i}$ is always equal to one, and given a set of numbers satisfying this property, a proper binary tree can always be built.
So we can simplify our optimisation strategy to system where $\sum 2^{-x_i} = 1$ and $\sum 2^{x_i}$ is minimal.

Now, consider the weaker system "$\sum 2^{-x_i} \leq 1$ and $\sum 2^{x_i}$ is minimal."

One can make the following observations:

Observation 1: $\sum 2^{-x_i}$ is always of the form $\frac{c}{2^{\max\{x_i\}}}$

proof: This is quite trivial

Observation 2: The system cannot be optimal if $\sum 2^{-x_i} \lt 1$

proof: Assume a system is optimal if $\sum 2^{-x_i} = \frac{c}{2^{\max\{x_i\}}} < 1$. If we replace the largest $x_i$ with $x_i-1$, the property $\sum 2^{x_i}$ will grow, and $\sum 2^{-x_i}$ will become $\frac{c+1}{2^{\max\{x_i\}}}$ wich is still lesser or equal to one, as $c$ and $2^{\max\{x_i\}}$ are integers. So there exists another system with a lesser value to optimise, so the system is not optimal.

Corollary 2: Optimal solutions of the weaker system are optimal solutions of the smaller system.

Observation 3: In the optimal system, two numbers can only have a difference of one.

A trivial consequence of the fact that increasing the smaller number by one and decreasing the bigger number improves the system.

Combining all this results in that the optimal system for 26 leaves results in 20 leaves with depth 5 and 6 leaves with depth 4. An example is given here:

A version of the image with the full polymer can be found here: https://gitlab.com/Elmosfire/blog-links/-/raw/master/polymer26.svg

This means that the shortest polymer is POpoNMnmOPopMNmnLKlkJIjiKLklIJijNMnmPOpoMNmnOPopJIjiLKlkIJijKLklHGhgFEfeGHghEFefDCdcBAbaCDcdABabFEfeHGhgEFefGHghBAbaDCdcABabCDcdLKlkJIjiKLklIJijPOpoNMnmOPopMNmnJIjiLKlkIJijKLklNMnmPOpoMNmnOPopDCdcBAbaCDcdABabHGhgFEfeGHghEFefBAbaDCdcABabCDcdFEfeHGhgEFefGHghZYzyXWxwYZyzWXwxVUvuTStsRQrqSTstQRqrUVuvRQrqTStsQRqrSTstXWxwZYzyWXwxYZyzTStsRQrqSTstQRqrVUvuRQrqTStsQRqrSTstUVuvHGhgFEfeGHghEFefDCdcBAbaCDcdABabFEfeHGhgEFefGHghBAbaDCdcABabCDcdPOpoNMnmOPopMNmnLKlkJIjiKLklIJijNMnmPOpoMNmnOPopJIjiLKlkIJijKLklDCdcBAbaCDcdABabHGhgFEfeGHghEFefBAbaDCdcABabCDcdFEfeHGhgEFefGHghLKlkJIjiKLklIJijPOpoNMnmOPopMNmnJIjiLKlkIJijKLklNMnmPOpoMNmnOPopVUvuTStsRQrqSTstQRqrUVuvRQrqTStsQRqrSTstZYzyXWxwYZyzWXwxTStsRQrqSTstQRqrVUvuRQrqTStsQRqrSTstUVuvXWxwZYzyWXwxYZyz