Harmonic differences

Do there exists two positive integers $h$ and $l$ such that $\sum_{i = l}^h \frac{1}{i}$ is an integer other than the trivial case?

Every natural number can be written as $2^\alpha x$. More specifically for each number $n$, $\alpha$ is the n-th element of this sequence, and $x$ is the n-th term of this sequence.
Let us first have a look at $\alpha$. If you take a consecutive subset, from index $l$ to $h$, the maximum always appears ones.

Proof:

Assume the maximum $y$ appears at least twice. As the index of the number has to be of the form $2^\alpha x$, the two appearances can be assumed to be $2^y a$ and $2^y b$ with $a$ and $b$ odd and $a < b$. As $2^y a < 2^y (a+1)< 2^y b$, and both ends are in the consecutive subset, $ 2^y (a+1)$ has to be in the subset. But as $a$ is odd, $a+1$ is even, and such $a+1$ can be written as $2^k z$ with k nonzero and $z$ odd. Hence, $2^y (a+1) = 2^{y+k} z$, so there exists a value $y+k$ larger than $y$ for the exponent, so $y$ was not the maximum, which leads to a contradiction.

Now, take the sum $\sum_{i = l}^h \frac{1}{i}$. By the previous lemma, there is one single element that contains the largest power of two, if written like $2^\alpha x$. Remove that element from the sum. The sum of all other elements can be written as $\frac{p}{\text{lcm} (i)}$ with $a$ an integer and $\text{lcm} (i)$ the least common multiple of all denominators. As all of the denominators have a lower exponent for two than $\alpha$, $\text{lcm} (i)$ is not a multiple of $\alpha$. Let us write this is $2^\beta y$ with $\beta < \alpha$

Our total sum is now $\frac{1}{2^\alpha x} + \frac{p}{2^\beta y} = \frac{2^\beta y + 2^\alpha x p}{2^\alpha x 2^\beta y}$
As the denominator is a multiple of $2^\alpha$ and the numerator is not, this can never be an integer. QED

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

Exponential Coins

There is a population of 1 million people, of which some are infected by a disease. Each two weeks the following happens:

1. Every infectious person has 50% chance to be cured.
2. Each infectious person infects 2 other healty people (if healty people still exist).

What is the change the disease will eventually be eradicated?

A more interesting (and at the time of the writing of this blog, actual) way to look at this problem other than the abstract notion of coins in a jar, we can model as a pandemic spreading through a population.

Suppose a jar that can hold a million coins, with a certain number of coins in it. You can do the following procedure:

1. Take out all coins
2. Flip all of them
3. Count number of heads
4. Put 3x the number of heads back into the jar.
   If the coins to not fit in the jar, we only leave a million, and toss the rest away

If we start with a jar with a single coin in it, what is the chance that we eventually the jar will be empty.

I would like to note that this thought experiment, even tough -as we will see- will have some properties in common with how a real pandemic spreads, is a vast oversimplification and can in no way to be used to model a real pandemic. The interesting quirk of probability that is displayed here most certainly does not work in real life.

Infinite case

First, let us take a look at the infinite case, so where there is no limit on the size of the jar.

Expected value

An observation that can be made is that the expected value of the number of coins gets multiplied with 1.5 after each step. This might seem obvious, as for example if we have exactly 10 coins, it is easy to see that we will have an expected value of 15 coins next step, but the truth is even stronger, as for example, if we would have 50% change to have 6 coins, and 50% to have 14 coins, the expected value is $0.5 \times 1.5 \times 6 + 0.5 \times 1.5 \times 14$ which is still 15. It works in general for any given distribution, that after each step, the expected value will increase by 50%.
This means that the expected value will grow to infinity, and specifially, the expected value after $i$ steps is
$E_i = \left(\frac{3}{2}\right)^i$

Jar duplication

Imagine instead of a single jar, we have multiple jars that we apply the process to. So for each jar, we take out all the coins, flip them, count the heads, multiply by three, and put them back in the original jar. It is easy to see that this process is equivalent to combining all the different coins in a single jar, as the total number of coins added back in is equal to the total number of flipped heads.

This means that a jar with $n$ coins can be considered as $n$ jars, with each a single coin in it. The total jar will be empty only if every jar ends up empty, and all jars are independant.

So if the chance a jar with a single coin ends up empty is called $p$, then the chance that a jar with $n$ coins ends up empty is $p^n$, as it is the same as $n$ independant jars ending up empty.

Chance

As $p$ is a global independant property, it is conserved with our porcedure. After one step of our porcedure, we have 50% chance to become empty (so a chance of 1) and 50% to end up with three coins. This means that $p$ follows the following equation:
$p = \frac{1}{2} \left(1+p^3 \right)$

The equation has three solutions, $1$, $\phi-1$ and $-1-\phi$, with $\phi$ the golden ratio. The last solution is smaller then zero, so that is impossible. It might be natural to scrap the solution of $1$, and keep $\phi-1$, and while it is correct, the mathematical reasons why this is actually are quite complex.
An important note to make is that most of the chance to empty the jar (or eradicate the disease) happens when the number of coins is low. For example, if there is one coin, there is already a 50% chance that the jar will end up empty after the first step, while the chances of ending up empty after any other number of steps is only about 23% chance of successfull eridication if it fails the first step.
Even worse, if we ever reach a million, the chance to ever empty the jar drops to $(1-\phi)^{1000000}$, which equals about $2 \times 10^{-208988}$, so basically impossible.

Finite case

One might reasonably assume that, as most of the chances to empty the jar are contained in the low numbers, that adding a constraint to the maximum number of coins in the jar will only change the chance slightly. One would be wrong. To show this, let us look at a slight variant of the problem:

You have a jar that can hold a million coins. Each step you do the following procedure:

1. Take out all coins
2. Flip all coins
3. If there is at least one head, refill the jar again up to a million coins.

It is easy to see that the jar will always contains more coins then in the original problem, so it is a stronger version, with a lower chance to eradicate.

Markov chain

The above problem can be represented by a Markov chain with two possible states: a million coins, or no coins. As the chance of going from a million coins to no coins is nonzero (But very small, about $10^{-30103}$) and constant, the chance to eventually have an empty jar follows from the following equation:
$(1-p) = (1-10^{-30103})(1-p)$
$10^{-30103}(1-p) = 0$
And even tough that the coefficient of $(1-p)$ is very small, it is nonzero, so $p$ has to be one. This means that even this extreme system, were a million coins are added, there is still a 100% chance (almost surely) To end up with zero coins. On the other hand, the expected number of steps has to be lower than $10^{30103}$.

Infimum

There is a chance of $2-\phi$ that the ininite system grows beyond one million (because it needs to not surely finish, and it had a chance of $\phi - 1$ to not finish.) This means that this is also the chance that our finite system reaches a million. If it has reached a million, it has a chance of $p$ to get out of this state of a million. We can calculate p as follows:
$p$ is the chance that a million coins throw less then 333333 heads. This folows the binonial distribution, but is estimated really well in this region by the normal distribution with avarage 500000 and standard deviation of 500. The zscore of 333333 in this normal distribution is (333333-500000)/500= 333. The p value of the left tale is: $10^{-24083}$ which means that in 30% of the cases it takes at on avarage more than $10^{24083}$ steps, not including the steps to get to one million, and the steps to get back to zero afterwards, and the large chance that when you go below a million, you will probably immedaitly get stuck again. This means that the expected value has to be bigger than $10^{24082}$ steps.

Conclusion

The combination of this means that the expected number of steps falls between $10^{24083}$ and $10^{30103}$. We could narrow this further down, but both numbers are so unphantomably huge, that there will be no point, just rest assured that even if there is certainty that the system will end up without any coins, it will take a very long time.