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.

Irving is a fourth-year graduate student studying topology and geometry at Princeton University. His mathematical interests include gauge theory and related Floer homologies. In his spare time he plays the violin (occasionally, and usually badly). He is fond of cats.
This entry was posted in Math, Math Games. Bookmark the permalink.

6 Responses to Math Puzzles/Riddles, Part II

1. Shashi kant Pandey says:

I think it is not possible accurately because 2^k is not divisible by 3 for any natural number k.

• idai says:

Hi! Well, it isn’t specified that (for example) each player has to subdivide the cake in half, so I’m not sure where the 2^k is coming from. (Perhaps you are claiming that other kinds of subdivisions will never be accurate?)

In any case, the problem is not actually to divide the cake into three exactly equal pieces – the point is to provide a method of division that is “fair” in the sense of the two-person problem.

• Shashi kant pandey says:

Hello, i am taking the case of possible way to cut this symmetric cake in n number of equal pices such that n is divisible by 3.And always i lands on the problem that divisibility of 2^k by 3 for any natural no k.
Now i am getting from your reply that you want a way/Algorithm to equal division of cake in three person.

2. Nobody in Particular says:

Pretty sure any two adjacent squares suffice if they are (1) adjacent (horizontal/vertical/diagonal), (2) with one space between (horizontal/vertical/diagonal), or (3) a knight’s move away. And clearly one square doesn’t. But do any other two-square configurations suffice? I haven’t found any but haven’t proven otherwise.

• idai says:

Sorry if the phrasing is unclear – diagonal squares are not considered “adjacent” for the purposes of counting the number of lit-up neighbors. (So most squares have four neighbors, corner squares have two neighbors, and so on.) So for example, case (3) (among other cases) that you have described doesn’t actually result in the generation of any new lit-up squares.

3. riddlewot.com says:

As a riddle site creator and lover of riddles, thank you for posting these 🙂