Here are two riddles, the solutions of which I will discuss next week. Interested readers are welcome to email me solutions.

Thanos Problem

Thanos, the all-powerful supervillain, can snap his fingers and destroy half of all the beings in the universe.

Suppose now there are n Thanoses, each snapping his fingers in a sequence, one after the other. When a Thanos snaps his finger, each being (Thanos or human) dies independently with probability 1/2.

Question: Out of K people on Earth, how many can we expect to still be alive at the end? More formally, let p_n be the probability that a human being survives. Initial values: p_1=1/2, p_2=3/8.

    1. Show that p_n = \Theta(1/n), that is, n \cdot p_n is bounded between positive constants.

    2. Does (p_1 + \ldots + p_n)/ \log{n} converge? If so, to what limit?

    3. Does n \cdot p_n converge? If so, to what limit?

 

Note: this problem was posted (with fewer details) by Oliver Roederon on the 538 blog, but without an analytical solution. The plot is due to Laurent Lessard (github).

Particles Problem

Suppose there are n particles in the unit square. Initially one particle is awake and all others are sleeping. Each awake particle moves in the unit square at speed 1 in a direction you prescribe and wakes up any sleeping particle it encounters. The particles that are awake move simultaneously and particles can change direction at any point in time.

Question: Show that you can wake up all the particles by time 10. Note: I learned this problem from Maria Gringlaz.

 

Lake Covering Problem

A circular lake of radius 10 meters must be covered by rectangular boards of length 30 meters.
Rectangular boards of all widths are available, but the cost of a covering is the total width of the boards used. Clearly the lake can be covered by using parallel boards of total width 20 meters.
Is there a more efficient covering possible? Here are examples of two competing coverings.

 

Solution to Particles Riddle

In a previous post I discussed the Particles riddle, a solution of which is as follows. Cover the unit square by four closed subsquares of side length 1/2, denoted A, B,C,D as in the figure. Suppose that the initially awake particle is located at x_A \in A, and there are sleeping particles in B,C,D (the case when some of these are unoccupied is easy to handle.) The particle at x_A wakes up a particle at some point x_B \in B by time \sqrt{5/4}. During the next \sqrt{2} time units, one of these two particles can travel to wake a particle in some x_D in D, and at the same time, the other  can travel to wake a particle at some x_C in C. In another 1/2 time unit, one of the particles from x_D can travel to B and one of the particles at x_C can travel to A. Thus by time \sqrt{5/4}+\sqrt{2}+1/2<3.1, there will be an awake particle in each of the originally occupied subsquares A, B,C,D. The argument can now be iterated in each of these subsquares. Repeated subdivision will yield a geometric series 3.1(1+1/2+1/4+\ldots)=6.2 as an upper bound for the time needed to reach all n particles. The constant 6.2  can certainly be improved; we will not try to optimize this constant. See also a similar solution posted by Sang-il Oum here.

The argument above readily generalizes to higher dimensional cubes (where the constant will depend on dimension) and to other self-similar sets. Compactness and convexity are not enough, however: Let e_1,e_2,\ldots be an orthonormal sequence in Hilbert space. Then the closed convex hull of \{e_k/\sqrt{\log{k}}: k \ge 1\} is compact, but the time needed to reach the first n vertices \{e_k/\sqrt{\log{k}}: 1 \le k \le n \} is of order \sqrt{\log{ n}}.

A metric space (X,d) is called a {\bf length \; space} if the distance between any two points equals the length of the shortest curve between them (In this case one also says that d is an instrinsic metric on X). In particular, a convex set in  a  Banach space is a length space; for the particle problem, it is natural to restrict attention to length spaces. The assumption that the particles travel at most at unit speed means that their paths are Lipschitz maps from [0,1] to X with Lipschitz constant 1.

A large class of length spaces where any finite collection of points can be reached in bounded time are {\bf doubling} length spaces.  A metric space (X,d) is called  {\bf doubling}  if there is some doubling constant M>0  such that every ball B(x,r) in X of any radius r, can be covered by at most M balls of radius r/2. See https://en.wikipedia.org/wiki/Doubling_space.

The following statement is easily proved by induction on n:  Given n particles, one of them awake, in a doubling length space with doubling constant M and diameter D, all particles can be woken up by time 3D (\log_2(M)+2). (As before, awake particles travel at unit speed).