8
$\begingroup$

Jennifer is playing a game. The Ace through King of spades are taken from a standard playing deck and laid out facedown on the table. At any time, Jennifer can select two cards and reveal them, and she will win points based on the product of the two cards, where Ace is 1, Jack/Queen/King are 0, and 2-10 are face value.

Before making her final selection, however, Jennifer can indicate two cards and will be told the absolute difference between them. She may do this as many times as she wants, but will have to pay 1 point each time she does so.

What is Jennifer's best strategy? What is her expected win from this game? What is her worst case scenario?

$\endgroup$
  • $\begingroup$ What's the absolute difference between (say) $10$ and Jack? Is it $1$ (as Jack$=11$) or $10$ (as Jack is $0$)? $\endgroup$ – WhatsUp Dec 6 '19 at 19:45
  • $\begingroup$ The latter! The absolute differences are using each of the card's "assigned" values. $\endgroup$ – Nahmid Dec 6 '19 at 19:48
  • $\begingroup$ Ok, this seems to make the problem slightly easier, as Jack, Queen, King are indifferent, reducing the size of the whole space by a factor of $6$, to about $10^9$. Also I guess computers are probably needed to solve the puzzle? $\endgroup$ – WhatsUp Dec 6 '19 at 19:55
  • $\begingroup$ I believe you can come up with the strategy without computers... finding the expected value might be a different story. $\endgroup$ – Nahmid Dec 6 '19 at 19:59
  • $\begingroup$ Are the points the multiplication result - 9X10=90? What you mean by final decision - isn't there one decision? $\endgroup$ – Moti Dec 7 '19 at 19:04
5
$\begingroup$

Since we are talking about multiplication (products grow really fast), and our data gathering is relatively cheap, it stands to reason that the best strategy is to

always find the 9 and the 10, using as many points to gather data as necessary (but not a single point more).

I had this idea yesterday, but it took me this long to get through the final annoying special case. However, I'm pretty convinced now that

There's a guaranteed strategy for 77 points, which is the worst-case score.

This is going to be a longish read because of the annoying special cases, so take a comfortable position if you intend to go through all of it.

To start,

we choose one card as a pivot, and measure it against the other cards.

Then, using this table,

we can easily identify the pivot:

       | # of cards at distance | ID at | solved in
       | 0 1 2 3 4 5 6 7 8 9 10 |       | 
 pivot +------------------------+-------+---------
 0     | 2 1 1 1 1 1 1 1 1 1 1  |  11   |  11
 1     |   4 1 1 1 1 1 1 1 1    |  11   |  11
 2     |   2 4 1 1 1 1 1 1      |  11   |  11
 3     |   2 2 4 1 1 1 1        |  11   |  11
 4     |   2 2 2 4 1 1          |  11   |  11
 5     |   2 2 2 2 4            |  10   |  13 (yes, really!)
 6     |   2 2 2 2 1 3          |  11   |  13
 7     |   2 2 2 1 1 1 3        |  11   |  13
 8     |   2 2 1 1 1 1 1 3      |  11   |  13
 9     |   2 1 1 1 1 1 1 1 3    |  11   |  12
 T     |   1 1 1 1 1 1 1 1 1 3  |  11   |  11

The second column from the right tells us that we can actually skimp, since we are guaranteed to identify

the pivot and all the other cards too even without measuring the final card. (Or even earlier than that, if the pivot was 5. This special feature of pivot 5 will prove important later on.) So we save the one point, and use only 11 points here.

Then, we still need to find the 9 and 10 to get the best possible score.

* If the pivot was 0-4, or a 10, we are already done.
* If the pivot was 6-8, we have identified the "zero" cards, which will help us figure out which cards are the 9 and 10. (There are only two possibilities for each.)
* The same applies to pivot 9, but of course we already know the nine, so we save a point.
* If the pivot was the 5, it seems we are out of luck. We need three more measurements in the worst case, and we would have used 14 points. THIS. JUST. WON'T. DO.

Getting rid of the final worst case is a lot more difficult than one would suspect. However, it is possible to set up an "early warning system" to shave off the final point loss:

The worst case always has one distance 5, and seven smaller distances (three pairs, one single) as the first 8 differences, for example 1-1-2-2-3-3-4-5. This is our "early warning". It could be a false alarm: we could still have a 6 as the pivot, for example. If that turns out to be the case, we are happy and follow the original plan.

If the next difference is a 5, it's time to sound the klaxons: we are on our way into the trap, and we need a special procedure to survive. Our pivot is now certainly 5, but if we continue to measure the pivot against the tenth card, we might run into another five. This would be a disaster, leaving us in a situation with ten points used already, but no guaranteed way to figure out the ten and nine in fewer than 4 measurements, at least when the unpaired difference was a 4.

So instead, we have to be Really Clever:

We have used 9 measurements, and the results have come up as 1-1-2-2-3-3-4-5-5 (single four) or 1-2-2-3-3-4-4-5-5. (single-some-other-number-than-four.) Because of the double distance-5s, we know our pivot is the 5, so we also know the remaining 3 unmeasured cards will have distances 5, 5 and unpaired distance from above. Now we have to deviate from the original plan:

Measurement 10: compare the two known distance-5s.

* If the difference is 0, they are both zeroes, and we can use either of them to find the 10 in the remaining three cards (takes two moves), and we still have one measurement left for finding the 9, so we are home free with 13 points used.

* If the difference is 10, there are two zeroes in the unmeasured cards. Comparing any pair of the unmeasured cards will always find at least one guaranteed zero among them, which we can leverage to find the 10 and 9 in only one more move each, and again, we have managed with only 13 points used.

The case where the unpaired distance was 4 (1-1-2-2-3-3-4-5-5) and measurement 10 gave difference 10 is particularly neat, since in addition to finding the much needed zero, measurement 11 also tells us EITHER
a) which unmeasured card is the distance-4 (if the difference was 0), OR
b) which number the previously unmeasured distance-4 actually has (if the difference was 4 or 9).

Either bit of information is just barely enough to let us identify the 9 in only one more measurement.

Backtracking a bit,

If the 9th measurement completes the unpaired difference, so that we have differences 1-1-2-2-3-3-4-4-5, we are happy: either the next difference is a 6, telling us that the alarm was false (our pivot is 6 in that case), or it's a 5, and we are in the "silver lining" scenario, where we do have a 5 as the pivot, and we have already used 10 points, but the good news is that we now know that both the remaining unmeasured cards are also at distance 5, so we can save a point in the identification step, and three more measurements are enough to find the 9 and 10.

So yeah, that should do it for the worst case score. The expected score is too difficult for me though; there seem to be quite many moving parts, in particular if we luck out and happen to find an early zero.


EDIT: Since the best case scenario might also be interesting, it is reachable with this strategy, so we could get all the way up to

87 points

without gambling anything, but there are only two very lucky situations where that could happen:

if the first three differences we measure are 0, 9, and 10 (in any order), we know the pivot is 0 and the 9 and 10 are obvious, or

if the first three differences are 1, 10, and 10 (again, in any order), we know the pivot is the 10, and the 9 is the card at distance one.

It's impossible to get a score better than that (without guessing and risking all the points), because in addition to luckily picking the two biggest cards, we'll also have to hit two zeroes, because that is the only way we can ever distinguish a 0 from a 10.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It is saying "if your pivot is X, here are how many of each distance Y you would see if you did all the comparisons." (So for pivot 2, if you check it against all the other cards, you will not see any that are 9 away). $\endgroup$ – hdsdv Dec 8 '19 at 1:13
  • $\begingroup$ Cool solution! +1 $\endgroup$ – justhalf Dec 9 '19 at 0:07
  • $\begingroup$ always find the 9 and the 10, using as many points to gather data as necessary This was also my feeling, but I wonder how can it be turned into a rigorous argument. Also, the question asks for best strategy and expected win, so I think the best strategy should be understood as the strategy which maximizes the expected win. To me it's really surprising that the OP claims that one can find the best strategy without computer. Perhaps there's a deeper trick. $\endgroup$ – WhatsUp Dec 9 '19 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.