3
$\begingroup$

This is inspired by the following question over at Computer Science Stack Exchange: Information-theoretic limits for a weighing puzzle

You are given 11 coins with labels 1, 2, 3, ... up to 11. You know these coins have weights 1, 2, 3, ... 11 but you do not know which coin has which weight (in particular, you do not know if the coins are correctly labelled by weight). Your goal is to come up with a procedure to determine whether the labels are correct using a balance scale. The scale tells you which side is heavier or that both sides are equally heavy.

The procedures are scored on the number of times the scale has to be used (fewer is better). Ties are broken by the total number of coins put on the scales over the whole procedure (counting repetitions when a coin is used multiple times), in favour of the smaller number.

One trivial procedure is to check if 1 < 2 and 2 < 3 and so on until 10 < 11. This requires using the scale 10 times and putting 20 coins in total on the scale. You can check out the linked question above for the optimal solutions for the case of 6 coins (in spoilers).

$\endgroup$
0

1 Answer 1

6
$\begingroup$

UPDATE: Shaved three off the number of coins weighed.

It can be done in

3 with a total number of 16 coins weighed.

Namely,

11 vs. 1+2+3+4
10+4 vs. 5+6+1+2
9+4 vs. 7+5+1
All labels are correct if the first weighing tips left and the other two are balanced.

Explainer:

A single coin can only outweigh four others if the single coin takes the maximal value 11 and the four others the minimal values 1..4. The first weighing therefore confirms as correct coin 11 and groups 1..4 and 5..10.
Similarly, comparing one from each group to two of each group equal totals are only possible if the two single coins take their maximal values 4 and 10 nad the two pairs take their minimal values 1,2 and 5,6. The second weighing therefore confirms as correct coins 3,4 and 10 and groups 1..2,5..6 and 7..9 The last weighing resolves the three groups since 13 is the minimum sum when taking one from each group and the maximum when adding 4 to one coin from the last group.

Optimality:

Note that this is optimal wrt the number of weighings and within two coins of a lower bound of total number of coins required.

To see this observe that a single weighing creates three groups according to whether each coin is placed on either arm of the balance or left out. Two weighings therefore create 9 groups some of which by pidgeon hole principle must contain multiple coins. There is obviously no way of telling which of these coins is which and we concluded that at least three weighings are required.
For the total number of coins first observe that there can be no more than one that is never placed on the scales. Each of the remaining 10 has to be placed on one of two arms in at least one of three trials. But if two or more are on the same arm in the same trial then to resolve this group requires to reweigh all but one in this group. As we have four coins more than trials$\times$arms we can conclude that at least $14$ coins must be placed.

Previous solution, same number of weighings but three more coins weighed:

10+11 vs. 6+5+4+3+2+1
10+7+1+2 vs. 5+6+9
9 vs. 1+3+5
If these three are balanced, the labels are all correct.

Explainer:

First weighing if balanced reveals groups 1..6,7..9,10..11 because 21 is the maximum weight of any 2 and the minimum weight of any 6
Similarly, the minimum weight when taking 2 from group 1 and one from each other is 20 which is also the maximimum when taking 2 from group 1 and one from group 2. If the second weighing was balanced we therefore know that 7 and up are all correct as are the groups 1..2,3..4,5..6
The last weighing resolves these three groups because 9 is the minimum sum when taking one from each group.

$\endgroup$
5
  • $\begingroup$ Good job :) I reckon this is optimal with respect to the number of times the scale is used. Do you think it is optimal overall? (taking into account the number of coins weighed) $\endgroup$
    – Tassle
    Commented Nov 4, 2020 at 14:04
  • $\begingroup$ @Tassle I genuinely don't know. Maybe somone smarter than me can find a way to check with a computer? $\endgroup$ Commented Nov 4, 2020 at 17:06
  • 1
    $\begingroup$ @Tassle I mangaged to reduce the number of coins weighed by three. $\endgroup$ Commented Nov 5, 2020 at 3:21
  • $\begingroup$ Cool :) How does it work with accepting answers to optimisations questions? Do I accept this answer as long as there are no better ones? Btw, I picked 11 because that's when it started to become non-trivial to check with a computer ^^ (probably still feasible, but surely requires some care and cleverness) $\endgroup$
    – Tassle
    Commented Nov 5, 2020 at 10:50
  • $\begingroup$ @Tassle since it's not clear whether this is optimal I'd wait a few more days before accepting. $\endgroup$ Commented Nov 5, 2020 at 11:17

Your Answer

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

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