Crack the Code

Can you decode the message below?

“NQV ARC RMWQLP ATXPROCMN FOC R YOMMOQC KQMMRXL OU NQV LPRXP FOPH QCT KQMMRX RCK YTP R LWRMM TCQVIH UXRAPOQC TCQVIH POWTL.”

This message was encoded by replacing each letter using a one to one map of the set of 26 letters of the alphabet onto itself.

Bacterial Population Growth

In this problem P(t) is the population of the bacterium at discrete time periods (measured in seconds) t = 0, 1, 2,… and P(t+1) = P(t) + P(0) Exp[-P(t)/P(0)]. So P(1) = 137% P(0), P(2) = 162% P(0). You are asked to determine the “cap” or “equilibrium level” for the maximum population (as a multiple of P(0)), at what time (t) the population reaches 50 percent of this cap and, hypothetically, what the population (as a multiple of P(0)) would be after a trillion (1012) years of growth.

Here is a simple solution to the first two questions based on an idea in a solution submitted by Brad Rosin. If L > 0 is the least upper bound for P(t), the P(t) converges strictly monotonically to L. So for any d > 0, it is possible to find a t1 such that L – d < P(t) < L when t > t1. Consequently P(t+1) – P(t) = P(0) Exp[-P(t)/P(0)] < d. Taking logarithms results in Log[P(0)] – P(t)/P(0) < Log[d] and it follows that P(t) > P(0) (Log[P(0)/d]). So, for any L > 0, if we pick d < P(0) Exp[– L/P(0)] then P(t) > L. So, P(t) has no upper bound and increases toward infinity.

For an explicit estimate of P(t), it turns out that Log[t+e] asymptotically converges to P(t)/P(0) for large t.

A trillion (1012) years is 1012 x 365 x 24 x 60 x 60 = 31,536,000,000,000,000,000 and Log[31,536,000,000,000,000,000 + e] = 44.8977. So, although the population increases to infinity without an upper bound, it grows incredibly slowly.

Although intuitively sensible, to prove this requires some real analysis. Let y(t) = P(t)/P(0). It follows that y(t+1) – y(t) = Exp[-y(t)]. Consider the analogous differential equation z‘(t) = Exp[-z(t)] and boundary condition z(0) = 1, which has the solution z(t) = Log[t + e ]. Also note y(t) can be extended to a continuous function for all t ≥ 0 as the solution to the differential equation y‘(t) = Exp[-y(Floor[t])], where Floor[t] is the greatest integer ≤ t and boundary condition y(0) = 1. Let a(t) = y(t)-z(t). y(1) = 1 + e and z(1) = Log [1 + e] < 1 + e and therefore a(1) > 0.

Consider what happens between t and t+1 for any integer t >=1 if a(t) > 0. Since y(t) > z(t) it follows that z‘(t) > y‘(t) > 0. For u in the interval (t, t+1) if z(u) > y(t) then z‘(u) < y‘(u). So z(u) < y(u) since if z(u) were to exceed y(t) < y(u) it would grow more slowly than y(u). By induction from t = 1, it follows that y(t) > z(t) and hence a(t) > 0 and a(t+1) < a(t) for t > 0.

Suppose that a(t) has a lower bound L > 0 for integer values t > 0. Then y(t) ≥ z(t) + L and for integers t it follows that y(t+1) – y(t) ≤ Exp[-L]/(t+e). Since z(t+1) – z(t) > 1/(t+e+1), consequently a(t+1) – a(t) < Exp[-L]/(t+e) -1/(t+e+1) < Exp[-L] /(t+e)-1/(t+e+1). The sum of Exp[-L]/(t+e) -1/(t+e+1) from t =1 to k is, by grouping terms differently, equal to Exp[-L]/(1+e) + [Sum from t = 2 to k of (Exp[-L]-1)/(t+e)] – 1/(k+e+1). Since Exp[-L]-1 < 0 and the sum of 1/(t+e) diverges to infinity as k increases, [Sum from t = 2 to k of (Exp[-L]-1)/(t+e)] diverges to negative infinity. This leads to the contradiction that a(t) < 0 for t large enough. So, the greatest lower bound of a(t) must be 0. Since a(t) is strictly decreasing with increasing, it asymptotically converges to 0 and hence z(t) asymptotically converges to y(t).

Solutions were also submitted by Bob Conger and Rob Kahn.