# How many guesses does it take to identify through process of elimination?

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
average good
average medium
short good
short medium

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.

• (1) Your attempt at a solution assumes that the values for each attribute are orderable; i.e., tall > average > short and good > normal > bad. You may believe that this is obvious from your examples, but it is not true in general (in the real world), so, if it is true in the game, you should say so.  (2) I don't fully understand the game.  (2a) You call it a "single player game", but it seems like there must be a second person, or some kind of automated Oracle, that gives the player honest answers to their questions. Say so.  (2b) I don't understand how to win the game.  … (Cont’d) Apr 28 '21 at 12:15
• …  If I ask "is the height equal to tall?" and "is the height equal to average?", and get "No" as an answer each time, have I identified the height as being "short", or do I have to take a turn asking the question that gets me a "Yes" answer? (3) You can probably get some insight by solving the problem (by hand, brute force) for small values of $n$ and $m$. Hint: $m=1$ is trivial; the answer is either $0$ or $n$ (see point 2b). Think more carefully about $m=2$. I believe that this is almost as trivial as $m=1$; in particular, I expect that you'll find that you don't want to use $\log n$. Apr 28 '21 at 12:15
• Hey Scott, thanks for the response. I'll respond one by one. (1) No, that's not my intent, so e.g. if the question "is 'height' equal to 'average'" has the response "no", that doesn't imply "short", it just implies either "short" or "tall", since they're the only two other values. Instead of height we could put "favorite thing" with values "sports, ice cream, or trees" and the dynamic should be the same. (2) Yeah, sorry about that, let's say the player gets responses from the computer, and wins upon eliminating all options except for the valid one. (3) That's what I did under "attempt". May 4 '21 at 20:25
• Thanks for responding.  (1) I’m really confused whether your attribute values are ordered. If the attribute can be “favorite ice cream flavor” with $m=8$ (chocolate, vanilla, strawberry, cherry, pistachio, coffee, butter pecan, and mint—in no particular order), then your problem is nothing like binary search. Each wrong guess eliminates one possible value, not $\frac m2$. (2) Please answer question (2b), just so we can communicate clearly. (3) I urge you to try $m=2$ again. (4) You want the minimum and maximum number of guesses required. The minimum should be trivial—where are you stuck? May 5 '21 at 3:57

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$$.)
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$$.