Alys+

🖙Heads and Tails Math

❁ written by alys on Friday, April 4, 2025

Sometimes I read "And now it's all this," a blog where the author, Dr. Drang, posts about his random scripting and automation workflows, as well as various math and physics puzzles. Earlier this month, he revisited a math problem: if eight people are sitting around a table, and they all flip coins, what are the odds no two adjacent people have flipped heads?

I had a few solutions of my own. Here's one:

TOTAL_PEOPLE = 8

exhaustive_start = time.perf_counter()

possibilities = itertools.product('HT', repeat=TOTAL_PEOPLE)

total_possibilities = 0
adjacent_heads_possibilities = 0

for possibility in possibilities:
    total_possibilities += 1

    for position, person in enumerate(possibility):
        if person == 'T':
            continue
        left_neighbor_position = (position - 1) % len(possibility)
        right_neighbor_position = (position - 1) % len(possibility)

        left_neighbor = possibility[left_neighbor_position]
        right_neighbor = possibility[right_neighbor_position]

        if left_neighbor == 'H' or right_neighbor == 'H':
            adjacent_heads_possibilities += 1
            break
exhaustive_end = time.perf_counter()

This solution is actually pretty similar to his, although I didn't realize there are a couple of tricks that make it much shorter:

1. Since the first and eighth person are actually next to each other, you can actually just tack on the first person at the end of the list. Instead I wrote a bunch of code to loop around
2. since we're looking for adjacent heads, you can make the list of heads and tails a string and use in to search for "HH".

For eight people, there are 2^8 possibilities, so checking every possibility is totally doable by a computer. (Honestly, a human could do it in an hour or two, I bet.)

As a personal challenge (and because I needed something to distract myself from being sick and in bed in early February), I came up with another solution using Monte Carlo, i.e., running a bunch of simulations. This is, surprisingly, slower and less accurate for eight people. However, it does scale up relatively well. Since the number of possibilities doubles every single time you add a person, the exhaustive approach grows exponentially. Checking all the possibilities for, say, 100 people flipping coins on a single computer, even if extremely optimized, would take longer than the universe has been existed¹. In contrast, the Monte Carlo approach grows linearly, since you have to do more coin flips as the number of people increases.

Lastly, I realized his original post provided an even faster way. Fibonacci numbers have a cousin, Lucas numbers, and one of his readers shared that it turns out, these exactly correspond to the number of combinations that don't result in. So the Lucas number 8 is 47. 256 - 47 = 209, which is exactly equal to the numbers we got before. It's easy enough to calculate Lucas numbers iteratively, and this is much faster than the Monte Carlo approach or the exhaustive approach.

However, you may realize that this suggests an even faster way: using a closed-form solution to the Lucas numbers. Using the golden ratio, we can calculate this easily, although I had to round it to give 47 and not a number a tiny bit less than 47. Calculating closed-form solutions to Lucas and Fibonacci numbers are a bit weird as a result of the fact we're taking the square root that doesn't result in an integer number (and is irrational, I'm pretty sure) . I'm sure you could use a computer algebra system (or a library). I imagine there may be some way to rearrange the formula to minimize the error from doing square roots on floating point numbers, but I haven't tried it yet. The decimal library might also help.

Because exponentiation isn't a constant-time operation on computers, I don't think the algorithm is strictly constant time. The closed form is still faster in Python, although the gap would probably be smaller if Python had less overhead in various operations. I thought exponentiation would be log2 N but no less a source than Raymond Hettinger says it's "nearly constant time." My quick tests indicate exponents run in about 8 nanoseconds up until they exceed the threshold of what fits in a long ( 2^64-1), and then it takes hundreds of nanoseconds and starts to increase sublinearly. Other tests I ran resulted in different numbers, so I wouldn't bet on those exact number, but it definitely seems to be in the nanosecond range, and thus not that much slower than other operations.

Iteratively finding a Lucas number is linear, but with a much smaller coefficient than Monte Carlo approach.

If you want, you can review my entire source file.

In summary:

• The exhaustive approach grows exponentially.
• The Monte Carlo approach grows linearly. In practice there is a significant (but not prohibitive) coefficient.
• Using Lucas numbers by finding them iteratively is linear with a pretty small coefficient.
• Using Lucas numbers using a closed form is briefly constant time, then sublinear with a pretty small coefficient.

You can also find Lucas numbers recursively, which has its own opportunities for optimization. Maybe I'll do a follow-up and discuss those options.

This is all kind of irrelevant (I mean, besides the fact that it's a puzzle). Other than the exhaustive approach, these are all plenty fast up to pretty big numbers. And the odds increase very rapidly, so that the adjacent people somewhere in your increasingly large ring of people both flipping heads becomes ever closer to 100%.

• #math
• #probability
• #python