Moronocles has just inherited a huge fortune. He plans to dedicate his life to charitable outreach, splitting his time between needy communities in Amsterdam, Las Vegas and Bangkok. He has carefully selected a group of candidates for the job of managing his finances while he is busy with his altruism: Delilah, Eve, Gomer, Ilse, Irma, Jezebel, Leni, Medea, Salome and Squeaky.
Although Moronocles believes they are all completely trustworthy, he hires Deckard, a professional investigator, to make the final selection. In Deckard’s experience, candidates for this sort of job either always tell the truth or lie about everything. Deckard’s interviews reveal the following:
- Irma says Squeaky is truthful.
- Excluding Delilah, over half of the other candidates are truthful.
- Excluding Leni, fewer than half of the other candidates are truthful.
- Either Medea, Salome and Squeaky are all truthful or they are all liars.
Whom do you think Deckard picks for the job?
Know the answer? Send your solution to ar@casact.org.
A Numerical Bar Game
Steve Mildenhall contributed this puzzle and the solution, which makes use of Goodstein sequences.
As you recall from this May-June Puzzle, the nerdier regulars at the Bon Pint pub enjoy a peculiar number game, where they start with an integer n and expand it in powers of 2. Then they expand all the exponents in powers of 2, and so on, until n is written with just 1s and 2s, e.g., 9 = 23 + 1 = 2(21+1) + 1. The puzzle asks how often the sequences stop and if they stop, how long the players play.
The game for n = 2, n = 3, and the initial terms for n = 4 are online. First, decide the outcome for n = 4. Then try to generalize.
The sequence terminates for all initial n, but it can take a very long time. If you approached the problem empirically by building a spreadsheet, that might be a surprising result since it seems to increase forever (in terms of normal-sized numbers).
Let’s work out the case n = 4. Following the instructions, write n in base 2, n = 22. Now, introduce the character ◻, and replace 2 with ◻: n = ◻◻. Think of ◻ as a special kind of fuel cell. It starts with 2 units of fuel. While it is unopened, its capacity increases by 1 each iteration. But as soon as it is opened, it stops growing and gets used up one unit at a time.
The Goodstein iteration is f(◻) → f(◻) – 1, where f is a function involving sums, products and exponentials, with the understanding that the right-hand side is rewritten with no negative coefficients in the same way you “borrow” when learning subtraction in grade school. When you borrow, a new cell is “opened” to create a finite number of new fuel units that are used to rewrite the right-hand side as a sum of terms with positive coefficients.
For n = 4, this conversion happens at the first iteration when each ◻ contains three fuel units. To write ◻◻ – 1 with positive coefficients, we “open” one tank and get 2 ◻2 + 2 ◻ + 2. Iterations two and three take us to 2 ◻2 + 2 ◻ . Iteration four yields 2 ◻2 + 2 c – 1 and each ◻ contains 6 units. To avoid minuses, we need to crack open another cell, obtaining 2 ◻2 + ◻ + 5. The new cell covers the next five iterations.
At iteration 10, we open a new cell that contains 11 units and arrive at 2 ◻2 + 11. And so on. We start with finitely many cells, and each cell, once opened, has a finite capacity. Thus, eventually, we’ll use up all the fuel.
We’re adding ◻ as a new number greater than any finite number. Expressions involving c are ordered by comparing like terms, and so each Goodstein iteration makes them smaller. Since they are all ≥ 0, eventually, the iteration must terminate. It can be shown that you cannot prove the Goodstein sequence terminates without introducing a new “number” like ◻.
How many iterations are required? The answer has more digits than we can print in AR. In exponential notation, it is
3 • 23+3•23+3•23•23•23 – 3 = 2402,653,211 – 3 ≈ 10121,210,694.
This is the result of an iterative formula. It is described in Wikipedia and the references therein. That article quotes numbers in the chain, whereas we quote iteration steps, so the answer above is one less than shown.
Shyam Bihari Agarwal provided a detailed solution. John Jansen also supplied the answer.
