[mcphage]

I'm not sure I understand. In the 4 card case, there are 4! or 24 different arrangements. So a total of ~4.5 bits. Each question gives you at most 1 bit of information. So it would seem like it takes up to 5 questions, but the page repeatedly says "you can always find which card is which in under 5 questions". Is there a technique I am missing?

[napping_penguin]

You are right, your argument establishes the lower bound: D(4) >= 5 (you will need at least 5 questions in the worst case).

The interesting bit is to come up with a strategy to make 5 adaptive queries that will guarantee you know all the 4 cards no matter what the response you got to the queries.

As a simple example: Suppose I do the following (static) set of 5 questions:

- Is the first card Red?

- Is the first card King?

- Is the second card Red?

- Is the second card King?

- Is the third card Red?

You can see that there might be a situation where these 5 questions are not enough to uniquely determine the arrangement (for instance, in case you got answers Yes, Yes, Yes, No, No respectively).

More succinctly, 5 is the information theoretic lower bound but that does not mean it is achievable and that is precisely what the post is about. Is the information theoretic lower bound achievable?

[mcphage]

…then why does the page keep saying it’s always possible in less than 5 questions, if it sometimes requires 5 questions?

[napping_penguin]

Ah, sloppy language on my part. It should be 5 of fewer questions. I'll fix it, thank you!