I'm trying to solve the following problem:
A single player guessing game involves a series cards, each representing a person with a unique combination of attributes. Each card lists n attributes, each of which is paired with one of m possible values, such that there are m^n unique cards.
For example, the attributes might be "height" and "mood", with possible values "tall, average, short" and "good, normal, bad" respectively, in which case there would be nine unique cards, each specifying e.g. "height: tall, mood: bad".
At the beginning of each round, a random card is chosen, and the player wins by identifying it. During each turn, the player may ask one question formed "is the [attribute] equal to [value]?" E.g. "is the height equal to tall?"
What are the minimum and maximum number of guesses required given n attributes and m possible values per attribute?
Attempt
I had a hard time getting started, but it struck me as at least kind of analogous to binary search for the special case where each attribute can be either true or false, i.e. the cases where m=2.
Each guess discards half of the candidates, so the number of guesses required is: $$\log_{2}{n}$$
So generalizing slightly, if each guess discards 1/x of the remaining candidates, the number of guesses required is: $$\log_{\frac{1}{1-\frac{1}{x}}}{n}$$
Getting stuck
This is where I got stuck. I can generalize to situations where each guess discards some fraction of the candidates, but that no longer maps onto how the game works.
Imagine there are 2 attributes with 3 possible values (9 candidates):
| height | mood |
|---|---|
| tall | good |
| tall | medium |
| tall | bad |
| average | good |
| average | medium |
| average | bad |
| short | good |
| short | medium |
| short | bad |
The first guess might discard 3 values (e.g. "Is the height 'tall'? No." discards the first three) or it might discard 6 values (e.g. if the height is tall, all non-tall values are discarded).
So that's either 1/3 or 2/3 of the candidates in the first guess. In the former case, the second guess will discard 1/2 of the remaining candidates iff it concerns the same attribute, otherwise it once again might either discard 1/3 or 2/3 of the candidates.
So in the best case, the number of candidates remaining proceeds in this sequence:
$$\{9, 3, 1\}$$
I'm not sure how to build an expression that represents the length of this sequence.
Attempt
So what is the relationship between the length of this sequence l and the m and n values?
Supposing 4 attributes instead of 2 (i.e. with m = 3 and n = 4), in the best case of getting a "yes" answer each time, the sequence would proceed: $$\{81, 27, 9, 3, 1\}$$
Since the sequence contains descending powers of three, it feels like the answer should have to do
with the cubed root. If there are N = m^n total candidates, the first number of the sequence is N. I think that means that this relationship holds:
$$\sqrt[l-1]{N} = n$$
E.g. the sequence starting with 81 has a length of 5, and 81^1/(5-1) is equal to 3.
So substituting
$$\sqrt[l-1]{m^n} = n$$
$$(m^n)^\frac{1}{l-1} = n$$
$$m^\frac{n}{l-1} = n$$
$$l=\frac{n}{\log_{m}{n}} + 1$$
But plugging back in m = 3 and n = 4, I get 4.169, which is … close, but I clearly did something wrong.
Best Answer
In the best case each question gets a "yes" answer. Then $n$ questions (one for each attribute) identifies the card.
I the worst case it takes $m-1$ questions to nail down the value of an attribute - all "no" until there's just one possibility left. Then you need $(m-1)n$ questions. (If you actually have to ask the last question for each attribute even though you know its value for sure then the number of questions is $mn$.)
There's no finding fractions of the cards (no halving, or thirding) since the attribute values are not ordered.
Think about the single attribute game with $m$ values. Then there are just $m$ cards and you guess "is it this one" until you are right.
With no correlation within or among attributes the average length of a string of guesses will be $(m-1)n/2$.