Each bacterium grows at a some constant rate, i.e. every minute the size of the bacteria increases by some constant value. Different bacteria can grow at different rate (they can also grow at same rate). Scientists observe $n$ bacteria under the microscope. Bacteria differ only in size and growth rate (in all other they are indistinguishable). Every minute, scientists identify the sizes of all $n$ bacteria and write down $n$ numbers - the sizes of bacteria (Scientists do not know which particular bacterium is of this or that size, because the bacteria move all the time). Prove that there is a number $m$ such that after $m$ minutes of observations, scientists will be able to unequivocally find a set of the growth rates of $n$ bacteria (The number $m$ should not depend on the sizes of the bacteria and their growth rates. The number $m$ may depend on the number $n$.).

My work. Scientists have numbers of $n$ arithmetic progressions. They need to find a set of common difference of arithmetic progressions. I proved that: a) if $n=1$ then $m=2$; b) if $n=2$ then $m=3$; c) if $n \ge 3$ then $m \ne 3$ (I do not know how to prove of the problem in the case when $n \ge 3$).


Look at the minimum of sizes of each datum.

Let $m_i$ be the minimum of sizes of bacteria at $i$th observation.

If $m_i+m_{i+2}=2m_{i+1}$ for some $i$, it means that at least one bacterium had size $m_i$ at time $i$ and has growth rate $m_{i+1}-m_i$ since if the $(i+1)$th minimum $m_{i+1}$ was not made by the bacterium it means there was another bacterium that was not smaller than the former one at time $i$ but had growth rate smaller than $m_{i+1}-m_i$, then that bacterium should be smaller than $m_{i+2}$ at the next observation.

That case, we just found out full information about that bacterium (size and growth rate) so we write that down and erase numbers in arithmetic progression with $i$th element $m_i$ and rate $m_{i+1}-m_i$, one element for each period of time. (we can iterate this to find full answer)

Now we are worried if we can always have $m_i+m_{i+2}=2m_{i+1}$ for some $i$. Note that if this does not hold, the bacterium that had size $m_i$ at $i$th and $m_{i+2}$ at $(i+2)$th are different and the latter one should have smaller growth rate so the former one can never be smaller then the latter one after then. Thus, $m_i+m_{i+2}\neq 2m_{i+1}$ can happen at most $2n-2$ times.

Therefore, $m=2n+1$ is enough.

  • $\begingroup$ Bacteria grow by arithmetic progression, and not by geometric progression. Therefore, the growth rate is not equal $\frac{m_{i+1}}{m_i}$. $\endgroup$ – Witold Jun 16 at 13:27
  • $\begingroup$ @Witold - Sorry for the mistake. I edited. Besides, the argument is the same. $\endgroup$ – C.Park Jun 16 at 13:37
  • $\begingroup$ Thank you very much! Very nice proof! $\endgroup$ – Witold Jun 16 at 14:12

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.