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.
Best Answer
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:
gives five matches, and the second sample:
has only three matches.
Therefore in looking at the positions where there was a change:
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).