10
$\begingroup$

I am trying to identify the branch of math that would help to solve the following problem:

A man has picked $10$ coins out of a bag and has laid them in a row. You cannot see them for yourself, and the heads/tails ratio is unknown. Your goal is to identify the correct heads/tails sequence of the coins by repeatedly picking $10$ coins of your own from the bag, with the man telling you how many match the position of his each time. You cannot decide whether the coins are heads or tails (for the sake of the problem assume they are the same on both sides) and your sequence depends on the order you remove them from the bag. Note that the man only selects his coins once and his never change.

For example, if the man has $HTTHHHHTTT$ and you propose $TTTHTHTHHT$ he will let you know that $5$ are a match, however he will not tell you which ones. If on your second try you pull out $THHTTTHTHT$ he will inform you that $3$ match. Without trying every possible combination $(2^{10})$, how would you go about learning the combination of coins the man has?

Comparing the two sample results I see that they share $3$ in common, but I'm not sure if or how that is useful information since I don't know which ones actually match.

I suspect it might require statistics/combinatorics, and I was told it could be solved with "either high school or college math". This isn't a homework problem so it's possible I'm just being trolled by the person. Any information you can provide for approaching this type of problem is much appreciated. Thank you.

$\endgroup$
15
  • 3
    $\begingroup$ "Without trying every possible combination" if that is all you are after, then you can be rather greedy and inefficient about it. First, guess all heads. He replies telling how many you got right so from this you know how many tails there are. Now, just guess all of the different ways you could have had that many tails. Now... the far more interesting question is what the most optimal approach is where here we can choose what we mean by optimal... most commonly that it takes the fewest number of guesses on average, or alternatively fewest guesses in worst case scenario. $\endgroup$ – JMoravitz Mar 16 at 14:11
  • 3
    $\begingroup$ I'm not convinced this would be considered a statistics problem because there isn't really any randomness or data analysis. Arguably it could be computer science, if the question is worded "what's the fastest algorithm for...". $\endgroup$ – 79037662 Mar 16 at 14:12
  • 3
    $\begingroup$ To clarify, you cannot decide whether the coins are heads or tails (for the sake of the problem assume they are the same on both sides) and your sequence depends on the order you remove them from the bag. $\endgroup$ – Isaac Newbton Mar 16 at 14:18
  • 2
    $\begingroup$ As hardmath said, it's a binary version of Mastermind or Bulls & Cows, except you don't get position info (black Mastermind pegs, or bulls). And your guesses are totally random. $\endgroup$ – PM 2Ring Mar 16 at 14:25
  • 3
    $\begingroup$ "You cannot decide..." So, it is possible, albeit unlikely, that we repeatedly pull nothing but heads over and over and over again and never any tails? If so, there is no upper bound on the number of trials it takes as it is possible to have not gained any new information beyond the first draw. In such a scenario then, it only makes sense to ask about average time until you have enough information and not worst case scenario. $\endgroup$ – JMoravitz Mar 16 at 14:26
4
$\begingroup$

The problem described in the Question, to determine exactly the opponent's fixed sequence of heads and tails, is not fully formulated because it needs some probability distribution for the sample sequences drawn by the player.

Given that probability distribution, one can ask the expected number of trials until the hidden sequence is determined. For some (trivial) distributions it will be impossible to make that determination, e.g. if all the drawn sequences are tails only, then all that can be known is what the split of the ten coins is between heads and tails.

Of a more combinatorial nature is how to extract information from the samples that are drawn. One way to think about it is in terms of the set of possibilities for the hidden sequence. In this connection having zero matches (or ten matches) would be ideal, because the exact sequence is uniquely determined.

In general getting $k$ matches will imply that there are $\binom{10}{k}$ possible solutions. Once the intersection of those subsets of possible solutions has a single common sequence, the problem is solved.

Let's consider how much information can be extracted from the example given in the Question. The first sample:

TTTHTHTHHT

gives five matches, and the second sample:

THHTTTHTHT

has only three matches.

Therefore in looking at the positions where there was a change:

T***T***HT

we know that two matches were lost (two that matched in the first sample but did not match in the second sample). So at least two of the five matches in the first sample are in those six "*" (changed) positions. Similarly at most three of the five matches in the first sample are in the four unchanged positions.

But more can be deduced from the net change of $-2$ matches from the first sample to the second sample. If the first sample has $k$ matches in the six changed positions, then the second sample would have $6-k$ matches there (since all have changed, and there are only heads or tails). So that would give us a net change of $-k + (6-k)$, and in order for this to be $-2$, we require $k=4$.

This reduces the number of possible solutions accordingly. The first sample alone gives $\binom{10}{5} = 252$ solutions. The second sample alone gives $\binom{10}{3} = 120$ solutions. Combining them gives us just $\binom{6}{4} \cdot \binom{4}{1} = 60$ possible solutions (pick four of the six changed positions for matches in the first sample, and one of the four unchanged positions for the final fifth match in the first sample).

$\endgroup$
2
$\begingroup$

Here's a Python program that implements the algorithm mentioned by saulspatz in the question comments, and discussed in hardmath's answer. I assume that the probability of picking a heads is 0.5.

In each round of the game, we first create a pool containing all 1024 possible 10 bit strings. Next, the target bit string is generated. Then we enter the outer loop, where we generate a guess bit string, and count the number of "bulls" (positions where the target & guess bit strings match). We then loop over all the bit strings in the pool, retaining only the strings that have the same match count when tested against the current guess. We exit the outer loop when only one bit string remains in the pool, which must match the target.

""" Random binary string guessing game
    See https://math.stackexchange.com/q/4064108
    Written by PM 2Ring 2021-03-17
"""

from random import seed, getrandbits
seed(42)

def bits(n):
    " Convert int n to a bit string "
    return f"{n:010b}"

def mcount(a, b):
    " Count matches between sequences a & b "
    return sum(u==v for u,v in zip(a, b))

def test(verbose=True):
    " Play 1 round of the game "
    pool = [bits(u) for u in range(1<<10)]
    target = bits(getrandbits(10))
    if verbose:
        print("\n T", target)
    for i in range(1, 100):
        guess = bits(getrandbits(10))
        bulls = mcount(target, guess)
        pool = [u for u in pool if mcount(u, guess) == bulls]
        if verbose:
            print(f"{i:2}", guess, bulls, len(pool))
        if len(pool) == 1:
            break
    if verbose:
        print(" R", pool[0], pool[0] == target)
    return i

@interact
def main(runs=10, verbose=True, auto_update=False):
    k = 0
    for _ in range(runs):
        k += test(verbose)
    print("Mean:", float(k / runs))

Here's the output for 10 runs, using 42 as the randomizer seed.

In each run, the target bit string is printed, followed by a number of guesses. Each guess line consists of its index, the guess bit string, the number of bits that match the target, and the number of remaining bit strings in the pool that are consistent with this guess. Finally, the only string remaining in the pool is printed, and we verify that it's identical to the target.

At the end of all runs, we print the mean number of guesses required per run.

 T 1010001110
 1 0001110010 3 120
 2 0000011001 4 50
 3 1011110111 5 26
 4 0100011001 3 4
 5 0011111010 5 3
 6 0011100100 5 1
 R 1010001110 True

 T 0010001110
 1 1011110010 4 210
 2 0001101000 5 100
 3 1010110100 5 48
 4 1011110110 5 30
 5 1110010001 3 12
 6 1000101110 7 9
 7 0001011001 4 5
 8 1001011100 5 3
 9 0110110000 4 2
10 0000100000 5 1
 R 0010001110 True

 T 0000011110
 1 0001011111 8 45
 2 0011011111 7 36
 3 0011101110 6 18
 4 1000000101 5 10
 5 1001101000 4 5
 6 0000011011 8 2
 7 1000111110 8 2
 8 0011001011 5 2
 9 1011011101 5 2
10 1010011001 5 2
11 1011001110 6 1
 R 0000011110 True

 T 1000101110
 1 0110101101 5 252
 2 0011100001 3 60
 3 0111001011 3 18
 4 1001011011 5 10
 5 0100011100 5 3
 6 1100111100 7 3
 7 1101111010 6 3
 8 0000000110 7 1
 R 1000101110 True

 T 1100001001
 1 1100111001 8 45
 2 0010100011 4 24
 3 1011001010 5 12
 4 0110110000 4 6
 5 0101011100 5 6
 6 0100011100 6 3
 7 0010011111 4 1
 R 1100001001 True

 T 0011011100
 1 1111010100 7 120
 2 1100001101 4 50
 3 0101011000 7 15
 4 0001101000 6 9
 5 0001011110 8 2
 6 0110000101 5 2
 7 0001100011 3 1
 R 0011011100 True

 T 0101101111
 1 1101100011 7 120
 2 0101100000 6 63
 3 1001101010 6 30
 4 0100001110 7 6
 5 1100111010 5 3
 6 0000101100 6 1
 R 0101101111 True

 T 1011101011
 1 0111010110 3 120
 2 1000100101 5 56
 3 0001111111 6 24
 4 1111100100 5 9
 5 1110110000 4 6
 6 0110000011 5 4
 7 0001010000 3 2
 8 1000110101 4 2
 9 0100101100 3 1
 R 1011101011 True

 T 1101010001
 1 1010000011 5 252
 2 1001111001 7 60
 3 1110001010 4 30
 4 1101110010 7 8
 5 0101110010 6 8
 6 1001001111 5 4
 7 0011000100 4 2
 8 1011010001 8 1
 R 1101010001 True

 T 0001000111
 1 0000101110 6 210
 2 1010100101 5 100
 3 0011101001 5 46
 4 1100010111 6 18
 5 0100101000 3 5
 6 1111110000 2 3
 7 0001010001 7 1
 R 0001000111 True
Mean: 7.9

It appears that the mean number of guesses required is a little over 7.

Here is a live version of the program, running on the SageMathCell server. If you set the runs parameter to 10000, it will take about one minute in non-verbose mode. I haven't tested higher numbers, but if a computation takes too long the server will abort the job.

$\endgroup$
6
  • 1
    $\begingroup$ I think it might be possible to compute the exact expected number of guesses by formulating a clever Markov chain. $\endgroup$ – hardmath Mar 16 at 22:38
  • 1
    $\begingroup$ @hardmath I doubt this will be easy: for example the probability of finding the target after one random draw is $\frac1{512}$ but the probability of finding the target after exactly two random draws is the slightly smaller $\frac{511}{512^2}$. Anyway, my own simulation confirms a mean near $7.3$ $\endgroup$ – Henry Mar 17 at 0:30
  • $\begingroup$ my simulation with $10^8$ runs also gives a mean of about $7.322$ $\endgroup$ – hgmath Mar 17 at 18:25
  • 3
    $\begingroup$ @hardmath regarding the exact expected number: I tried to compute them "brute force" for smaller numbers of coins $n$, and the results I got for $n=2,3,4,5,6,7$ are: $$2,3,\frac{136}{35},\frac{423}{91},\frac{14334317}{2699697},\frac{24531101921}{4164089787}$$ These appear to match the simulation. unfortunately I can't really figure out a pattern there :( $\endgroup$ – hgmath Mar 17 at 18:29
  • $\begingroup$ @hgmath: I'm thinking about a dynamic programming approach, perhaps an illusory thought. But it seems to me that something is going on that reduces "$k$ matches in $n$ coins" to smaller counts of matches in parts of $n$ (similar to the information extracted in my Answer). $\endgroup$ – hardmath Mar 17 at 20:43
0
$\begingroup$

My attempt is to visualize, simplify and extract maths from all the statements

\*lets assume that for every instant i begin to pick, the bag would contain exactly $10$ coins of which $5$ are heads and $5$ tails, also we'll assume the coins are distinguishable, so that they have same face on both sides and also i'll assume my coins display were not hidden from me, and my attempt was infinte plus that i made note of every of my attempt and it's information *\

$$\begin{matrix} \cdot &1&2&3&4&5&6&7&8&9&10\\ 1&H&H&H&H&H&H&H&H&H&H\\ 2&T&T&T&T&T&T&T&T&T&T\\ \end{matrix}$$ this is the row of the coins, in all possibility $2^{10}$ $$\text{the man coins} \rightarrow \{ x_{1} , x_{2} , x_{3} ,x_{4} ,x_{5} ,x_{6} ,x_{7} ,x_{8} ,x_{9} ,x_{10} \}$$ the set $X$ is the man's pick, and $x_{n}$ is either $H$ or $T$ depending on how it appeared but our goal is to find the ratio $\frac{\text{Heads}}{\text{Tails}}$ for his pick, say ratio of $\text{Heads}$ to $\text{Tails}$ is a function $P()$, where $P(X) = k$ $$ \{ H \rightarrow 10, (H \rightarrow 9, T \rightarrow 1), (H \rightarrow 8, T \rightarrow 2), (H \rightarrow 7, T \rightarrow 3), (H \rightarrow 6, T \rightarrow 4),(H \rightarrow 5, T \rightarrow 5) , (H \rightarrow 4, T \rightarrow 6), (H \rightarrow 3, T \rightarrow 7), (H \rightarrow 2, T \rightarrow 8), (H \rightarrow 1, T \rightarrow 9), T \rightarrow 10 \} $$

$ P() \in \{ 0,\frac{1}{9} ,\frac{2}{8} ,\frac{3}{7} ,\frac{4}{6},1 ,\frac{6}{4} ,\frac{7}{3} ,\frac{8}{2} ,\frac{9}{1} , \text{nil} \}$, so we are attempting to find the value $k$

$$\text{all my attempts} = \{ y_{1}, y_{2}, y_{3}, y_{4}, \dots \dots\}$$

say $\text{compare()}$ is a function, that produces the number of match between the set of coins when comparing them, now in the example you gave if i compare the man's pick with my first attempt

$$\begin{matrix} H&T&T&H&H&H&H&T&T&T\\ T&T&T&H&T&H&T&H&H&T\\ &\cdot&\cdot&\cdot&&\cdot&&&&\cdot&\\ \end{matrix}$$ there are $5$ match, also notice here that both contain same $\frac{\text{Heads}}{\text{Tails}}$ ,now in the second case you gave, there is $3$ match here $$\begin{matrix} H&T&T&H&H&H&H&T&T&T\\ T&H&H&T&T&T&H&T&H&T\\ &&&&&&\cdot & \cdot && \cdot\\ \end{matrix}$$ when i compare the cases of my first two attempt, remember i don't know the man's pick but only the number of match my attempt makes, they'll also make matches then...... i can compare all my attempts in order to know the correct position of the man's pick $$\begin{matrix} T&T&T&H&T&H&T&H&H&T\\ T&H&H&T&T&T&H&T&H&T\\ \cdot &&&& \cdot &&&&&\cdot \\ \end{matrix}$$ from here i can see that the true value is actually just one, so $\text{compare(y_{1}, y_{2} ) } = y_{1} \bigcap y_{2} $ therefore you can get the man's pick in a possible chance or even before that,know the position of some of the man's coin if not even all,by simply comparing all your attempts and noting the number of matches

$$\text{all my attempts} = \{ y_{1}, y_{2}, y_{3}, y_{4}, \dots \dots\}$$ my attempts can be grouped in $11$ sections based on the value for the $P()$ function $ P() \in \{ 0,\frac{1}{9} ,\frac{2}{8} ,\frac{3}{7} ,\frac{4}{6},1 ,\frac{6}{4} ,\frac{7}{3} ,\frac{8}{2} ,\frac{9}{1} , \text{nil} \}$

so we would take all the particular case when $P() = 0$ of my attempts and compare with the man's pick $\text{compare(X,y_{1})} = \dots \dots$, $\text{compare(X,y_{2})} = \dots \dots$, $\text{compare(X,y_{3})} = \dots \dots$, $\text{compare(X,y_{4})} = \dots \dots$, $\text{compare(X,y_{5})} = \dots \dots$, $\dots \dots \dots \dots $ and then compare all the matches of my attempt in twos $\text{compare(y_{1},y_{2})} = \dots \dots$, $\text{compare(y_{1},y_{3})} = \dots \dots$, $\text{compare(y_{1},y_{4})} = \dots \dots$, $\dots $ , $\text{compare(y_{2},y_{3})} = \dots \dots$, $\dots \dots \dots \dots$

and then also take all the particular case when $P() = \frac{1}{9}$ of my attempts and compare with the man's pick and when we compare all the matches in twos $\text{compare(X,y_{1})} = \dots \dots$, $\text{compare(X,y_{2})} = \dots \dots$, $\text{compare(X,y_{3})} = \dots \dots$, $\text{compare(X,y_{4})} = \dots \dots$, $\text{compare(X,y_{5})} = \dots \dots$, $\dots \dots \dots \dots $ and when we compare all the matches of my attempt in twos $\text{compare(y_{1},y_{2})} = \dots \dots$, $\text{compare(y_{1},y_{3})} = \dots \dots$, $\text{compare(y_{1},y_{4})} = \dots \dots$, $\dots $ , $\text{compare(y_{2},y_{3})} = \dots \dots$, $\dots \dots \dots \dots $

so this process is repeated, infinitly until scenarios appear where $\text{compare()}$ has a higher value w.r.t the man's pick and my attempts , also when $\text{compare()}$ has a low value, $1$ if i'm comparing two of my attempt w.r.t man's pick

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.