Problem

There are 10 coins sitting on a table “heads” up. Among them, 9 are fair coins while 1 of them has a Head on the two sides. You are allowed to 10 flips: can you find a strategy that finds the two-headed coins more than ~36% of the time? #maths #probability #riddle

https://twitter.com/thienan496/status/1385111543193296897?s=20

Solution

This seems to work ~60%.

1) Pick the first coin and keep tossing it until it shows tails; if it does, move on to the next coin.
2) hen we run out of tosses, if we've tossed a coin that never showed us tails, make that our guess.
3) Otherwise, guess at random from all the untested coins.

from dataclasses import dataclass

import numpy as np
import pandas as pd

class Coin:
    def __init__(self, is_fair=True):

        if is_fair:
            self.sides = ["H", "T"]
        else:
            self.sides = ["H", "H"]

    def toss(self):
        return np.random.choice(self.sides)

    @property
    def is_fair(self):
        return self.sides[0] != self.sides[1]

    @property
    def is_fake(self):
        return not self.is_fair

    def __repr__(self):
        return str(self.sides)

c1 = Coin(is_fair=True)
c1, c1.is_fair

(['H', 'T'], True)

# check that our `flip` method leads to fair outcomes
observations = [c1.toss() for _ in range(100_000)]
results = pd.Series(observations).value_counts(normalize=True)
assert np.allclose(results["T"], results["H"], rtol=0.05)

def generate_bag_of_coins():
    # Let us create a bag with 9 fair coins and 1 fake
    bag = [Coin(is_fair=True) for _ in range(9)]
    bag.append(Coin(is_fair=False))

    # now shuffle the coins, so we don't know which one if fake
    np.random.shuffle(bag)

    # enumerate our bag
    bag = {i: c for i, c in enumerate(bag)}

    return bag

# verify that we have 9 fair and 1 fake
# pd.value_counts([c.is_fair for c in bag])

from typing import Dict

def make_a_guess(bag: Dict[int, Coin], verbose=False):
    from collections import defaultdict

    observations = defaultdict(list)
    COIN_TOSSES = 10

    current_coin_index = 0
    if verbose:
        print(0, bag[0])
    while COIN_TOSSES:
        coin = bag[current_coin_index]
        result = coin.toss()
        observations[current_coin_index].append(result)
        COIN_TOSSES -= 1

        if verbose:
            print("Tossing...", result)
        if result == "T":
            bag.pop(current_coin_index)

            current_coin_index += 1
            if verbose:
                print(current_coin_index, bag[current_coin_index])

    # if we've tossed a coin that never showed us tails, make that our guess.
    guess = None

    for coin_index, toss_results in observations.items():
        if set(toss_results) == {"H"}:
            return coin_index

    # Otherwise, guess at random from all the untested coins
    return np.random.choice(list(bag.keys()))

Now let’s run our experiment 10 000 times and see how often we guess correctly:

def run_experiment(verbose=False):
    bag = generate_bag_of_coins()
    guess = make_a_guess(bag, verbose=verbose)
    return bag[guess].is_fake

from tqdm.notebook import trange

experiments = pd.Series([run_experiment() for _ in trange(10_000)])
experiments.value_counts(normalize=True).to_frame()

	0
True	0.6036
False	0.3964

Huzzaa! The algo gets it right about 60% of the time, which is 2x improvement on original conditions