tetration

Here is a problem from fakalin. Find the error in the following proof:

Let \(x^{x^{x\cdots}} = 2\). Then \(x^{x^{x\cdots}} = x^{x^{x^{x\cdots}}} = 2\). Substituting, we get \(x^2=2\) and \(x=\sqrt{2}\). Now let \(x^{x^{x\cdots}} = 4\). Similarly, \(x^{x^{x^{x\cdots}}} = 4\), \(x^4=4\) and \(x=\sqrt{2}\). But then \(2=x^{x^{x\cdots}}=4\) and \(2=4\).
(Read the article)

a problem of moments

We would like to prove the following fact:

For any non-negative random variable \(X\) having finite first and second moments, \(\mathbb P(X>0) \ge (\mathbb EX)^2/\mathbb EX^2\).

The proof isn’t difficult. Here are three different ones.
(Read the article)

two inductive problems

Terrence Tao quotes an (apparently) widely known problem, briefly paraphrased:

There is an island upon which 1000 people with various eye colors live. 900 have brown eyes, and 100 have blue. Each resident can (and does) see the eye colors of all other residents, but is forbidden by custom to try to discover one’s own (no talking about it, etc.). If (and only if) one does discover one’s own eye color somehow, then one commits suicide the following day for all to witness.

One day a visitor unaware of island customs comes to the island and announces (truthfully) to everyone: I see at least one blue-eyed person among you. What happens next?

One might be tempted to say that nothing happens, since every islander already sees either 99 or 100 blue-eyed people, so the visitor seemingly brought no new information.
(Read the article)

some propositions on the game of go

I’ve been meaning to learn the game of “Go” (weiqi) for quite a while now, and finally got around to it now that there are some people at Harvard at beginner’s levels to play with.

The usual adage is that the rules of “Go” are simple, but the strategies are difficult. Sometimes they cite the fact that computers can’t play “Go” very well (compared to, say, chess). I’m not in a position to defend or refute this sentiment yet, but I think this stuff is easier than it first appeared to me years ago, if you think about it the right way. “Go” seems a very mathematical game, almost a counting and topological reasoning game. And all the difficulties arise out of the fact that the counting and reasoning is done in 2D (rather than 1D, which would be simple).

So there is this list of terminology like “liberties,” “eyes,” “false eyes,” “alive and dead regions,” etc., but sometimes they greatly confuse the matter, so I found it easier to recast these basic concepts in more general terms.

(Read the article)

Cell synthesized

Scientists create synthetic cell, version 1.0 | [paper]

Our synthetic genomic approach stands in sharp contrast to a variety of other approaches to genome engineering that modify natural genomes by introducing multiple insertions, substitutions, or deletions (18–22). This work provides a proof of principle for producing cells based upon genome sequences designed in the computer. DNA sequencing of a cellular genome allows storage of the genetic instructions for life as a digital file.

This seems significant, equivalent to booting up the first stored-program computer.

Scientists who were not involved in the study are cautioning that the new species is not a truly synthetic life form because its genome was put into an existing cell.

That’s sour grapes, because the original cell cytoplasm decays to zero exponentially fast in the number of replications, a point well made in the paper. It’s only needed for booting. What’s more useful to know is how much of the 1.08Mbp genome consists of existing genes. The paper says it’s a close copy of M. mycoides:

The synthetic genome described in this paper has only limited modifications from the naturally occurring M. mycoides genome. However, the approach we have developed should be applicable to the synthesis and transplantation of more.

The next step will be a basic cell with a minimal genome, a barebones cell OS, if you will. Then, on to synthetic functions. Pretty soon we’ll have cell API’s, fancy-pants programming frameworks, and bugs and viruses. I mean real ones.

minimax vs. maximin

An elementary, nice lemma relating to the optimization of multivariable functions says that the smallest “big thing” is still bigger than the biggest “small thing”, in other words,

\(\min_x \max_y f(x,y) \ge \max_y \min_x f(x,y)\).
(Read the article)

another combinatorial puzzle (allocation)

Well, the original problem was X-rated, so let me recast it.

Three surgeons (A, B, C) participate in an operation involving three patients (a, b, c). For simplicity, each surgeon operates with just one hand, and operates just once on each patient. There are a bunch of sterile surgical gloves that stop contamination from one side to the other. What’s the minimum number of gloves needed to ensure that no body part ever comes into contact with another, even indirectly? Note, surgeons do not want to contaminate each other either.

Clearly, the upper bound is 9, for the 9 pairings. The lower bound is 3, for the 3 patients, or alternatively the 3 surgeons. Is the answer something in between?
(Read the article)