Neighboring non coprime

Let $n > 1$. A sequence $A_n$ of integers greater than 1 having length $n$ is called nice if any two elements are not coprime. That is, $$\gcd(A_i, A_{i+1}) > 1 \forall i, 1 \leq i \leq n-1$$

Find the smallest real number $t$ such that, given any sequence of integers $A_n$ of integers greater than 1 having length $n$, there exists a sequence of positive integers $B_n$ of length $n$ such that:

1. $\max{B_i} \leq n \max {A_i}$

2. $B_n$ differs from $A_n$ in at most $\lceil tn \rceil$ elements.

Solution

Note that for $t=1$ we can just change every single element to a small number like 2. We can try to do better. Satisfying condition 2 is easy, because for $t = 1/2$ we can just change every other element to the the LCM of it's neighboring elements, but this would make it failr condition 1. For example, suppose the sequence consists of very large primes, then this strategy would cause every other element to be the product of the two large primes, failing condition 1.

We propose that $t = 2/3$ satisfies the condition. That is, if $$A_n = a_1, a_2, a_3,a_4,a_5,a_6,\dots,a_n$$ $$B_n = 2a_2, a_2, 2a_2, 2a_5, a_5, 2a_5, \dots$$

We can see that every two neighboring elements are not coprime, and that the maximum of $B_i$ is at most twice that of $A_i$. We show that there is no smaller $t$ that can satisfy, using a series of counter examples.

For $n=3$, consider the sequence $p_1,p_2,p_3$ of very large primes. There is no way to only change one element to be nice, while keeping the maximum element manageable. The only way to change one element to be nice is to change $p_2 \to p_1p_3$, which then would fail condition 1. So we must change at least 2 elements, which means $\lceil 3t \rceil \geq 2$, so $t > \frac{1}{3}$

For $n=5$ consider the sequence $p_1,p_2,p_3,p_4,p_5$. If we were to change only 2 elements, either we change $p_2,p_4$, or we leave two neighboring primes intact. But if we change $p_2,p_4$, this could mean we have to change $p_2$ to LCM of $p_1,p_3$ and so on, violating condition 1. So we must change at least 3 elements, which means $\lceil 5t \rceil \geq 3$ so $t \frac{2}{5}$

Expected number of throws

$n$ fair coins are thrown all at once. Those that show Head are removed from the game, and the rest are thrown again. This process is repeated until there are no more coins left. What is the expected number of throws? Find a closed form formula, meaning that it may still be expressed as a sum but may not be expressed as a recurrence relation.

Solution Let $f(n)$ be the desired result. There is a $\binom{n}{k} / 2^n$ chance that $k$ of them will show heads, and the process is repeated with $n-k$ coins now. The rest of the game is expected to take $f(n-k)$ throws. If $k=0$ then we still have the same situation as before. If $k=n$, we have 0 throws left. In all of these situations, we do have to spend 1 turn doing the throw. So the recurrence relation is:

$$f(n) = 1 + \sum_{k=1}^{n-1} \frac{\binom{n}{k}}{2^n} f(k) + \frac{1}{2^n}f(n)$$ $$f(n) = \frac{2^n + \sum_{k=1}^{n-1} \binom{n}{k} f(k)}{2^n-1} $$

Given a large $n$, computing this would take $O(n^2)$ time as we have to calculate and store the previous $f(k)$ values, and each take $O(k)$ time. We can manipulate this expression further to come with a summation formula for $f(n)$ that would allow it to be computed in linear time.

First we claim and prove the following lemma. For $1 \leq m < n$

$$ \sum_{k=m}^{n} \binom{n}{k}\binom{k}{m} = \binom{n}{m}2^{n-m}$$

Proof: given $n$ white balls, we wish to pick $m$ of them and paint them black, and the rest may stay white or be painted gray. The RHS side is obvious, there are $\binom{n}{m}$ ways to choose black balls, and the rest may be painted white or gray.

To show the LHS, first we pick a number $k \in [m,n]$. We choose $k$ balls and paint them gray. Out of these $k$, we further choose $m$ to be painted black.

Alternatively we can prove the lemma by dividing both sides by $\binom{n}{m}$: $$ \sum_{k=m}^{n} \frac{n!}{k!(n-k)!} \frac{k!}{m!(k-m)!} \frac{m!(n-m)!}{n!} = 2^{n-m}$$ $$ \sum_{k=m}^{n} \frac{(n-m)!}{(n-k)!(k-m)!} = 2^{n-m}$$ $$ \sum_{i=0}^{n-m} \frac{(n-m)!}{(n-m-i)!i!} = 2^{n-m}$$

which is a well-known identity

Given the lemma, now we claim the following statement: let $a_n = \frac{2^n}{2^n-1}$ then: $$f(n) = \binom{n}{1}a_1 - \binom{n}{2}a_2 + \binom{n}{3}a_3 + \dots + (-1)^{n+1} \binom{n}{n}a_n$$ We will show that this formula matches our recurrence relation above by strong induction. Suppose they hold for $1,2,\dots,n-1$, then we first evaluate the following expression: $$\sum_{k=1}^{n-1} \binom{n}{k}f(k) = \binom{n}{1}f(1) + \binom{n}{2}f(2) + \dots + \binom{n}{n-1}f(n) $$ $$= \sum_{k=1}^{n-1} \binom{n}{k} \sum_{m=1}^{k} (-1)^{m+1} \binom{k}{m}a_m $$ we rearrange and collect each $a_m$ terms: $$= \sum_{m=1}^{n-1} (-1)^{m+1}a_m \sum_{k=m}^{n-1} \binom{n}{k} \binom{k}{m} $$ Apply the lemma: $$= \sum_{m=1}^{n-1} (-1)^{m+1}a_m \left(\binom{n}{m}2^{n-m} - \binom{n}{m} \right) = \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m} a_m \left(2^{n-m} - 1 \right) $$ We can plug this expression to our recurrence formula and compare against our claim (induction hypothesis). After multiplying both sides by $2^n-1$, we are left to show that: $$(2^n-1) a_n + \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m} a_m \left(2^{n-m} - 1 \right) = (2^n-1) \left( \sum_{m=1}^{n-1} (-1)^{m+1} \binom{n}{m}a_m + (-1)^{n+1}a_n \right)$$ Collect $a_n$ terms to the LHS, and the rest of the terms to RHS: $$(2^n-1)(1 + (-1)^n)a_n = \sum_{m=1}^{n-1}a_m(-1)^{m+1} c_m $$ where $$c_m = (2^n-1)\binom{n}{m} - \binom{n}{m}(2^{n-m}-1) = \binom{n}{m}(2^n - 2^{n-m}) = \binom{n}{m}2^{n-m}(2^m-1) = \binom{n}{m}2^{n-m} \frac{2^m}{a_m}$$ so what we need to show becomes: $$(2^n-1)(1 + (-1)^n)a_n = \sum_{m=1}^{n-1}a_m(-1)^{m+1} \binom{n}{m}2^{n-m} \frac{2^m}{a_m} $$ $$2^n(1 + (-1)^n) = \sum_{m=1}^{n-1}(-1)^{m+1} \binom{n}{m}2^{n} $$ $$1 + (-1)^n = \sum_{m=1}^{n-1}(-1)^{m+1} \binom{n}{m} $$ $$1 + \sum_{m=1}^{n-1}(-1)^{m} \binom{n}{m} + (-1)^n = 0$$ $$(1 -1)^n = 0$$