Find number 8 with the least number of tries

Question

You and your friend plays a game. In this game, there are numbers written on the cards from 1 to 12 on one side (so 12 cards in total). The other side is blank. You can write anything on the blank part of the cards without seeing the number written on them and you give your cards to your friend.

After that, your friend shuffles the cards and put them on the table on the blank side (or edited side), of course. You choose any 4 or less cards and give it to your friend. Then, your friend puts them on the table from left to right with descending order written on the cards so you can only see the desceding order of cards. (not the actual values) This is one try. Then you give 4 or less cards again, and this goes like that.

Your task is to find the card with the number 8;

What is the least number of tries required to guarantee to find the card with 8?

Hint

You do not have to find the biggest card to find card 8.

Answer 1

I managed to find the 8 in

6 steps.

So we are trying to find the 5th largest card in a bunch of 12, by measuring them in batches of four. Here's my strategy:

Pick any four cards, and label them 1 (biggest) to 4 (smallest). Repeat twice with unlabeled cards, keeping the measured stacks separate. As the fourth step, choose the three cards labeled with two. Label the stacks with A (had the biggest "2"), B and C (had the smallest "2").

Now we have identified, for certain, a couple of cards we can exclude: A1 and A2 (both have at least 8 cards smaller than them), and B4, C2, C3 and C4 (all have at least 5 cards bigger than them). We also have some information on the ordering on the rest of the cards.

Here's a diagram to illustrate:

(If two cards are connected by a line, the leftmost (or the topmost) one is the bigger of those two.)

(In step 4, we could in theory have included one more card, but since we are looking for a guaranteed strategy, we would always hit the worst case scenario where the extra card is one of the cards that were already excluded by the reasoning.)

So we are left with 6 candidate cards, and we need to find the third largest.

This is pretty simple to do in 2 more steps. Step 5 is:

Choose A3, B1, C1 and one of the remaining candidates. (A4, B2 or B3. Doesn't matter which.)

Since the largest remaining cards of all the stacks were included, the biggest of the bunch is the largest remaining candidate (too big), and the smallest of the four is too small, since there were at least three cards larger than it.

Step 6: We have four candidate cards left, and we need to find the second largest among them. I don't think we need a spoiler block on how to do that :-)

And that's just about does it.

I did try to invent a better "step 5" to immediately identify the third largest card, but couldn't find anything useful.

Answer 2

I can do it in

7 steps. First select three disjoint groups of four, labeling each group as ABCD, EFGH, and IJKL. At this point, there are 240 possible orderings of the five largest numbers.

The fourth step is to compare the three largest values: A, E, & I. Without loss of generality, assume A > E > I. This identifies card A as 12, and leaves 40 possible orders for the five highest cards:

AEIXY With $XY \in \{BC,BF,BJ,FB,FG,FJ,JB,JF,JK\}$
ABEXY With $XY \in \{CF,CD,CI,FC,FG,FI,IC,IF,IJ\}$
AEBXY With $XY \in \{CF,CD,CI,FC,FG,FI,IC,IF,IJ\}$
AEFXY With $XY \in \{BC,BG,BI,GB,GH,GI,IB,IG,IH\}$
ABCXY With $XY \in \{DE,ED,EF,EI\}$

Note:

We are only comparing 3 cards on step four. We could add in a fourth, picking one of the cards that came in second. We'd have to select one at random, since we don't know which stack is which. If we got lucky and picked the card from the stack with the highest, we could get ABEI for this result, reducing the number of orderings to 4. But we could also get AEIJ, which would tell us nothing more than AEI would. So, we might as well throw in a fourth card, but in the worst case, that tells us nothing.

Continuing...

The fifth comparison should be B, C, E, & I. This can return 6 possible results:

BCEI: 4 options, ABCXY (any)
BECI: 5 options ABEXY (C>I)
BEIC: 5 options ABEXY (I>C)
EBCI: 9 options AEBXY (C>I) or AEFXY (C>I)
EBIC: 9 options AEBXY (I>C) or AEFXY (B>I>C)
EIBC: 14 options AEIXY (any) or AEFXY (I>B)

Assume the worst case. Any other results would obviously be easier to solve.

So the fifth comparison yielded EIBC. This limits the possible orderings to AEIXY or AEFXY. For the sixth step, compare: B, F, I, & J. This yields eight possible results:

FIBJ: 4 options AEFXY, XY $\in$ {GH, GI, IG, IB}
FIBJ: 4 options AEFXY, XY $\in$ {GH, GI, IG, IJ}
IBFJ: 2 options: AEIXY, XY $\in$ {BC,BF}
IBJF: 2 options: AEIXY, XY $\in$ {BC,BJ}
IFBJ: 2 options: AEIXY, XY $\in$ {FG,FB}
IFJB: 2 options: AEIXY, XY $\in$ {FG,FJ}
IJBF: 2 options: AEIXY, XY $\in$ {JB,JK}
IJFB: 2 options: AEIXY, XY $\in$ {JF,JK}

For any of these options:

after step 6, we have identified cards 12, 11, & 10, and there are at most four cards vying for numbers 9 and 8. Compare those cards: the highest is 9, the next highest is 8.

Thus, we have completed the process and identified card 8 in at most

7 steps.

Note, that as a side-effect of identifying card 8, we also identified cards 12, 11, 10, & 9. There might be a more efficient option to identify card 8 without necessarily identifying the higher cards, and this may be possible in fewer steps, but I doubt it. Given the number of possible orderings, I do not believe a more efficient algorithm is possible to identify and sort the five highest-numbered cards.

Answer 3

I can do it in:

8. Ask for three piles of 4 to be ranked. Then take the highest from each pile, rank them - the highest is 12, and replace the other cards. The same procedure next finds 11. This way you find 12,11,10,9,8.