New Year's Countdown Day 29: Card Chase

Computer Science Level 2

I have a shuffled deck of cards containing 28 two of clubs and one ace of spades. I place all of the cards face down in a straight, horizontal line on a table. Then, I challenge you to find which of these cards is the ace of spades, given the following rules:

On each turn, you may ask exactly one question about the cards. You may only ask yes or no questions - no other question types are accepted.

You may point to a card as a reference to your question if needed.

Once you have asked a question, I will answer it truthfully with either "yes" or "no." After this happens, one turn has passed.

What is the fewest number of turns you need in order to determine with absolute certainty which card is the ace of spades?

This problem is part of the set New Year's Countdown 2017 .

The answer is 5.

2 solutions

Kunal Gupta
Jan 2, 2018

We may use Binary Search to find out the location of the ace of spade. Select the middle card and ask " Does the right group has the spade?" Depending upon the answer you can shift the groups. As there are 29 cards, fewest number of moves are determined by: $\lfloor \log_{2} (29) \rfloor = 4$

Shouldn't it be $\lceil \log_{2} (29) \rceil$ instead?

Agnishom Chattopadhyay - 3 years, 5 months ago

The final comparison/question isn't counted since the problem only asks you to "determine" which card is the ace of spades.

Steven Yuan - 3 years, 5 months ago

I don't agree it should be 5. Base 2 Log of 29 is 5 rounded up.

Daniel Hernandez - 3 years, 4 months ago

We are not rounding here, we are taking the floor function value of the resulting real number. $\log_{2}(29) = 4.85798099513$ $\lfloor { 4.85798099513 }\rfloor = 4$

Kunal Gupta - 3 years, 4 months ago

I know you are taking the floor function, what I mean is that it should be the ceiling.

Daniel Hernandez - 3 years, 4 months ago

@Daniel Hernandez – Read Steven Yuan's reply below.

Kunal Gupta - 3 years, 4 months ago

Will van Noordt
Jan 2, 2018

I am not sure that I agree, but I am not a computer scientist, so let me know if I am wrong.

There are 29 possible positions for the ace of spades, but there are $2\cdot 2\cdot 2 \cdot 2 = 16$ possible combinations of answers to the 4 questions. By the pigeonhole principle, only 3 of the 16 combinations of yes/no answers uniquely identify a single card, while the remaining 13 describe exactly 2 positions.

So, I would phrase my answer as:

"5 turns are guaranteed to locate the ace, but one can locate the ace in as few as 4 turns."

True, but one can locate the card in just one turn depending on the strategy we are following (of course it would be a worse strategy). So I think the answer should be five unless we are restricted to only use binary search, then, wording the question a little bit different (as it is it sounds like the minimum by any given case) the answer could be 4.

Daniel Hernandez - 3 years, 4 months ago

New Year's Countdown Day 29: Card Chase

This problem is part of the set New Year's Countdown 2017 .

The answer is 5.

2 solutions

0 pending reports