15
$\begingroup$

On the table there are $20$ coins that carry the letters $A,B,C,\ldots,T$. The values of these coins are $1,2,3,\ldots,20$ Euro (but the assignment of values to letters is secret). Fredo knows the value of every single coin, while Cosmo does not know.

In every round of the game, Cosmo must point at three different coins on the table (which we call the first, second, third coin). Fredo pockets the first coin, and then tells Cosmo truthfully which of the other two coins has higher value. The game then goes on with the remaining coins.

Cosmo may end the game after any round, by pointing at two coins still on the table and announcing that their total value is at least $28$ Euro. Cosmo wins the game if and only if his announcement is correct.

Question: How can Cosmo enforce a win?

Improve this question
$\endgroup$
1
  • $\begingroup$ Are the three coins selected removed from the table, or the two compared returned to the table? You use the term "remaining", so after first move - 17 remain on the table. After 6 moves 2. Are you looking for a strategy to leave the two? $\endgroup$
    – Moti
    Dec 24, 2015 at 6:35

3 Answers 3

Reset to default
12
$\begingroup$

Divide the coins into 3 groups.
Take 3 from the first group.
Of the remaining two, select the smaller one first, the bigger one second, then a new coin 3rd.
Repeat with the rest of the coins in the group.
Repeat with the other group.

At the end, we'll have 3 groups, with minimum values 5, 11, 17 and an extra coin in each group. Use two of the smaller coins to pick the two largest values (11 and 17), minimum 28.

We know the groups have those minimum values by checking the worst case scenarios.
We could bump off 18-20 with our first guess in each group, leaving the max at 17. The 17 could be in a group with 20, 17, 16, 15, 14, 13, 12, leaving the next highest number at 11. Repeat leaving the smallest group at 5.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If there's a chance you lose, you're not enforcing a win. $\endgroup$
    – DrunkWolf
    Dec 23, 2015 at 18:04
  • $\begingroup$ @DrunkWolf Well, I thought the small chance was good enough, but I've revised it to 3 groups. $\endgroup$
    – JonTheMon
    Dec 23, 2015 at 19:10
  • $\begingroup$ +1 I like this solution. It's probably simpler to see that my solution (hence the +1). I guess it takes 16 weighings vs 15, which might be a way to differentiate them (obviously one I'd go for!), but very elegant logic. In general throw away the top $n$, divide the remaining $20-n$ into $n$ groups and make a group of $n$ out of the max of those groups. Take the top two of this final group. $n=2$ gives 18+9=27. $n=3$ gives 17+11=28. $n=4$ gives 16+12=28. $n=5$ gives 15+12=27. Mine works slightly differently from this method, but yours is a nice simple algorithm that's easily generalised. $\endgroup$
    – Dr Xorile
    Dec 23, 2015 at 20:11
6
$\begingroup$

Label the coins 1 through 20.
Your first five moves are:
- Give up 16, and weigh 1 vs 2
- Give up 17, and weigh 3 vs 4 - ...
- Give up 20, and weigh 9 vs 10
(The worst case here is that we've given up coins valued 16 to 20.)
Assume without loss of generality that $2>1, 4>3,\ldots, 10>9$.
Your next five moves are:
- Give up 1, and weigh 2 vs 11
- Give up 3, and weigh 4 vs 12
- Give up 5, and weigh 6 vs 13
- Give up 7, and weigh 8 vs 14
- Give up 9, and weigh 10 vs 15
Assume wlog that $11>2,12>4,\ldots,15>10$
The worst case here is that we've given up one of 13 or 14. Which means we now have 5 coins ($11,12,\ldots,15$) the top two of which weigh at least 28 (either 15+14 or 15+13).
We also have five weighings left, by giving up 2,4,6,8, and 10.
Last five weighings to determine the top two of the group:
- 11 vs 12
- 13 vs 14
Assume wlog $12>11$ and $14>13$.
- 12 vs 14
Assume wlog $14>12$
- 15 vs 12 (controversial, but it's the only way it works)
Case 1: 15>12:
This eliminates 11 from the top two ($15>12>11$) and 12 from the top two ($15>12$ and $14>12$). The top three can therefore be $15>14>13$, $14>15>13$, or $14>13>15$. So weigh 15 vs 13 and eliminate the smaller of the two.
Case 2: 15<12:
In this case, $14>13$, $14>12>15$, and $14>12>11$. This eliminates 11 and 15, and leaves either $14>13>12$ or $14>12>13$. So weigh 12 vs 13 and eliminate the smaller of the two.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What do you mean by weigh? Namely coins have values not weights and Cosmo does not know the values of any coin. $\endgroup$
    – fibonatic
    Dec 24, 2015 at 14:03
  • $\begingroup$ @fibonatic Weight, value, it ends up being a very similar comparison. And while Cosmo doesn't know the absolute values, he knows the relative values. $\endgroup$
    – JonTheMon
    Dec 24, 2015 at 15:05
6
$\begingroup$

Edited 29 December based on Tyler Seacrests's very insightful comments (so if it is correct it is a joint Derek/Tyler solution). Of course if it's incorrect the fault is mine.

Two important insights:

The very first coin will be sacrificed blind. Worst-case it is value_20. We can be sure to retain value_19 by only sacrificing the lower of a comparison thereafter.
To achieve 28 we must therefore guarantee finding value_9 or above. A group of 10 (or more) coins (A...J or K...T) is guaranteed to contain this, allowing for the initial sacrifice.

Proceed as follows:

1. Offer Fredo A, B and C (in that order). A is sacrificed and we classify B and C as lower and higher
2. Offer Fredo lower, then higher, then D. The old lower is sacrificed and we now know the highest of B-C-D.
3...8. Sacrifice the lower of the previous comparison to compare the higher with E...J
9. Put the current higher aside, sacrifice lower against K. The coin set aside is at least value_9 (it may be as high as value_20). But the coin we now sacrifice is worth less.
10...16. Continue sacrificing lower against L...T
17. Point to the higher of the last comparison and the coin set aside in step 9

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think worst case is 19, 1, 2, ..., 9 in the first group, and 20, 10, 11, ..., 18 in the second. I think you can fix it though .... $\endgroup$
    – Tyler Seacrest
    Dec 27, 2015 at 22:52
  • $\begingroup$ After you're done with the first group, you actually have a high and low leftover. Use this last low from the first group as the first sacrifice for the second group. $\endgroup$
    – Tyler Seacrest
    Dec 27, 2015 at 22:54
  • $\begingroup$ Yes @Tyler you are right about the worst case, and I think your insight about the leftover is correct. I'll try to work it out later today. $\endgroup$
    – NL_Derek
    Dec 28, 2015 at 11:31
  • $\begingroup$ This sounds like my initial answer, which had that same 9-18 problem. $\endgroup$
    – JonTheMon
    Dec 28, 2015 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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