Math Puzzles/Riddles, Part II

Hi! For this month, we have two new math problems/riddles, once again posted without solutions (in order to encourage discussion). Have fun!

LIFE ON A CHESSBOARD

Most of you are probably familiar with various versions of Conway’s famous “Game of Life”. This riddle pertains to a particularly simple version, played on an 8×8 grid of what are usually envisioned as light-up squares. The setup is as follows: initially, some subset of the squares are lit up (the “starting configuration”). At each stage, a square lights up if at least two of its immediate neighbors (horizontal or vertical) were “on” during the previous stage. Note that in this version of Life, squares do not ever turn from “on” to “off”.

It’s easy to see that for the starting configuration in which eight squares along a diagonal of the board are lit up, the entire board is eventually covered by “on” squares. Several other simple starting configurations with eight “on” squares also result in the entire board being covered. Is it possible for a starting configuration with fewer than eight squares to cover the entire board? (If yes, find it; if no, give a proof!)

THREE-WAY CAKE SUBDIVISION

A group of three (mutually distrustful) mathematicians are attempting to divide a cake between themselves. They have a knife, but no measuring utensils of any kind. The mathematicians need to agree on a procedure for subdividing the cake in which each mathematician has a role in the subdivision and assignment of cake pieces. This procedure must satisfy the following “fairness” condition: for each mathematician X, if X has “perfect play”, then X can guarantee him or herself at least one-third of the cake, regardless of the actions of the other two mathematicians.

In the two-person case, a solution is furnished by the following simple procedure: one person (either one) cuts the cake into two pieces. The other person then chooses a piece for him or herself, with the remaining piece going to the one who originally divided the cake. This procedure evidently satisfies the fairness condition (with one-third replaced by one-half); the question is then to devise a suitable procedure for three mathematicians (or any number of mathematicians, if you are feeling bold!).

Note that one is not allowed to assume anything about the other players, even rational self-interest or perfect play on their part. For example, one (flawed) procedure might be to have person A cut the cake into three pieces, and then have A, B, and C then choose their own pieces in some order with A going last (say B, C, and then A). Although one might argue that A has an incentive to divide the cake as equally as possible (since it seems likely that A would receive the smallest piece), we do not assume that A can or will do so. Thus A might (perhaps by accident) cut the cake lopsidedly into one large and two extremely small pieces, violating the fairness condition from the point of view of C.