2 ms·
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 i
by mcphage 2mo ago
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 2mo agoYou 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 2mo ago…then why does the page keep saying it’s always possible in less than 5 questions, if it sometimes requires 5 questions?
- napping_penguin 2mo agoAh, sloppy language on my part. It should be 5 of fewer questions. I'll fix it, thank you!