Introduction

This bit puzzle is easy to describe and awkward to brute-force: you start with n zeroes, place one initial 1, then repeatedly place the next 1 in a legal position that is farthest from the existing ones, with the extra rule that no two 1 bits can be adjacent. The challenge is to choose the first placement so the final number of 1 bits is as large as possible.

Why Naive Simulation Is Slow

A direct simulation tries every possible starting position and then follows every tie-breaking choice later in the game. That grows quickly because different openings split the remaining zeroes into different subsegments, and many of those subsegments behave like smaller copies of the same puzzle.

The fast approach is to stop thinking in terms of full board states and start thinking in terms of segment lengths.

Define an Anchored Subproblem

A useful helper is an anchored function f(n). Let f(n) mean the number of 1 bits that eventually appear in a segment of length n when both ends of that segment are already considered occupied by 1 bits.

That framing matters because once the puzzle places a new 1, the legal cells to its left and right become independent anchored segments. The full problem therefore decomposes naturally into smaller anchored problems.

Small values are easy to check by hand:

• 'f(1) = 1'
• 'f(2) = 1'
• 'f(3) = 2'
• 'f(4) = 2'
• 'f(5) = 3'

The Recurrence

When the endpoints are fixed, the farthest legal next position is the midpoint. That split gives the recurrence.

For odd length 2m + 1:

f(2m + 1) = 2 * f(m + 1) - 1

For even length 2m:

f(2m) = f(m) + f(m + 1) - 1

The subtraction by 1 avoids double counting the middle placement that conceptually belongs to both recursive sides.

Once f is available, the score for opening at position i in a row of length n is:

g(n, i) = f(i) + f(n + 1 - i) - 1

The best answer is simply the maximum of g(n, i) over all legal starting positions.

Python Implementation

1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def anchored_score(n: int) -> int:
5    if n <= 0:
6        return 0
7    if n == 1 or n == 2:
8        return 1
9    if n == 3 or n == 4:
10        return 2
11
12    if n % 2 == 1:
13        return 2 * anchored_score((n + 1) // 2) - 1
14
15    m = n // 2
16    return anchored_score(m) + anchored_score(m + 1) - 1
17
18
19def best_opening(n: int) -> tuple[int, int]:
20    best_position = 1
21    best_score = 0
22
23    for i in range(1, n + 1):
24        score = anchored_score(i) + anchored_score(n + 1 - i) - 1
25        if score > best_score:
26            best_position = i
27            best_score = score
28
29    return best_position, best_score
30
31
32for n in range(1, 11):
33    print(n, best_opening(n))

Memoization makes this practical because the same segment lengths appear again and again.

Why the Split Works

The key insight is independence. Once you place a 1, positions on the left of that bit no longer interact with positions on the right except through the already-occupied boundary. That means the total number of future placements is the sum of two smaller answers.

This is exactly the kind of structure dynamic programming wants: repeated subproblems indexed by a small state, in this case the segment length.

Example

Take n = 7. If you always start in the exact middle, that feels intuitive, but it is not always optimal. Some openings create better left-right splits than others.

With the recurrence, you do not need to manually simulate every branch. You just evaluate the opening score for each i:

1n = 7
2for i in range(1, n + 1):
3    score = anchored_score(i) + anchored_score(n + 1 - i) - 1
4    print(i, score)

That tells you which opening positions achieve the best final count.

Common Pitfalls

• Brute-forcing every future tie-breaking sequence is much slower than solving the length-based subproblem once.
• Forgetting that f(n) is an anchored helper, not the final answer for the original board, leads to wrong totals.
• Getting the small base cases wrong breaks every larger result built from them.
• Assuming the center is always the best first move is not safe; the best opening depends on how the split behaves recursively.
• Recomputing the same segment scores without memoization wastes most of the runtime.

Summary

• The fast solution comes from reducing the puzzle to repeated segment-length subproblems.
• Define an anchored helper f(n) for segments whose ends are already occupied.
• Use the even and odd recurrences to compute f(n) efficiently.
• Evaluate each opening with g(n, i) = f(i) + f(n + 1 - i) - 1.
• Memoization or bottom-up dynamic programming makes large values of n practical.