Steve Mildenhall contributed this puzzle.
The nerdier regulars at the Bon Pint pub enjoy a peculiar number game. 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. For example, 9 = 23 + 1 = 2(21+1) + 1. They then make a new number by replacing each 2 with 3 and subtracting 1 from the result, carrying terms (like grade school math subtraction, see example below) to ensure all the coefficients in the base 3 representation are positive. Next, they replace 3 with 4 and subtract 1, and so on. They keep going until the pub closes or the sequence stops, whichever comes first.
How often do the sequences stop? If they stop, how long do the players play?
To get you started, here’s the game for n = 2, n = 3, and the initial terms for n = 4.
- When n = 2, the game stops after 3 steps: 21 → 31 – 1 = 2 → 1 → 0.
- When n = 3, it stops after 5 steps: 21 + 1 → 31 + 1 – 1 = 31 → 41 – 1 = 3 → 2 → 1 → 0.
- When n = 4, the game starts: 22 → 33 – 1 = 2 × 32 = 2 × 3 + 2 = 26, which illustrates carrying (twice) to ensure all coefficients are positive. The sequence continues, 26 → 2 × 42 + 2 × 4 + 1 = 41 → 60 → 83 → 109 → … .
First, decide the outcome for n = 4. Then try to generalize. Show your work for partial credit.
Follow-ups on solutions to previous puzzles
Proof of Crypto Mining Work
This puzzle was to find a number (a “nonce”) that when appended to “Casualty Actuarial Society” results in a SHA-256 hash with at least 20 leading binary 0s (same as at least 5 leading 0s in hexadecimal representation), or equivalently smaller than 2236. Two solutions that should have been mentioned are below:
Dave Schofield should have been mentioned as also submitting the strongest nonce at previous publication time, 7180096807, which results in 9 leading hex 0s and 37 leading binary 0s in the hash value of: 0000000004e11d3163164d3485ad2588f56eda9630c71405acf23f004c9060f9.
More recently, Mike Convey submitted the nonce 1ff8640245, which results in 10 leading hex 0s and 42 leading binary 0s in the hash value of: 00000000026aa1c8ce977957f4dbf2e4b9951b61300eb996a555c0df47e8e2e.
Soon, a follow-up column is anticipated dealing with the ongoing search for a stronger (more leading binary 0s) Casualty Actuarial Society nonce.
Questionable Odds
Jeff Subeck pointed out a subtle logical deficiency in the wording of the original puzzle, something most readers would assume but should have been explicitly stated. This assumption should have been explicitly stated — something like the following: “The question must have a fixed answer for any given individual, independent of whether or not that individual is the randomly chosen person.”
Without the clarification above, a trivial solution for part of the puzzle could be as follows:
“A question to ask to maximally improve your expected probability of correctly guessing is whether this person is in the set of persons such that, if it is guessed that they are the person who was randomly selected, the guess would be correct. The list of people having an answer of yes will be a list of the one selected person. This trivially results in 100% probability of correctly guessing this person.”
A Game of Coins
Solutions were sent in by Shyam Bihari Agarwal, John Berglund, Olivier Guillot-Lafrance, Dave Oakden and Andrew Yuhasz. Stay tuned for the solution in an upcoming AR!
