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.
