| 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? |