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?
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?
Good catch but it's intentional. The engine behind the first simulator for 4-cards is adversarial and hence appears a bit deterministic.
- Adversarial engine: Will always respond with an answer to your query such that it maximizes the number of remaining permutations (used in the first simulator)
- Honest engine: This one will actually have one random hidden permutation that will be uncovered by your queries (this is used in the second simulator)
The reason why the adversarial engine is used up there is because if the user does not play optimally, they will be forced into 6 queries or more (and hence will appreciate the difficulty of the problem better). If you do self-play on the lower simulator (which has the 4,8,16 card variants) you will have the experience you expect.
This behavior also confused me. Perhaps I’m not the target audience for your post, but some text describing why the simulator behaves the way it does would have been quite helpful