5
$\begingroup$

The 12 coins 12 coins problem but you can't understand the scale asks for is not the maximum possible, therefor this follow-up question:

You have a number of coins, one is fake but you don't know if it is lighter or heavier. You have a scale that gives you output but you don't understand it (let's say it is written in a foreign language that you don't understand).

For each possible answer (left, right, equal) there is only one output. Let's say you put 2 coins on the scale and the left is heavier, it A will be presented on the scale. But you see only A which you can't derive that it means that left is heavier because it is in some foreign language that you don't understand. But - A will be always if left is heavier, B for if right is heavier and C if it is equal, you'll just won't know it when you'll see the output.

Prove that using 4 weightings, the fake coin can be found in 14 but not in 15 coins.

$\endgroup$

1 Answer 1

4
$\begingroup$

If each coin is given by a different lower-case letter, you could use these tests:

Test 1: cefgjn vs bdhikm

Test 2: cehikl vs bdfgjn

Test 3: dfgikm vs bcehjl

Test 4: cdf vs gij

More coins can't be done because:

There are only 14 distinguishable results we can get from 4 weighings. In other words if A is the result of the first weighing, B is the result of the first weighing that isn't A (if any), and C is the result of the first weighing that isn't A or B (if any), then we can only receive AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC.

Comments:

To construct a non-adaptive strategy like I did, I just went through each possible 4-result string, and assigned it a coin. Then I decided which test result would mean equality. This tells which side of each test the coin goes on (if any) except we could possibly swap sides for the coin in every test. I was able to get this to work with minimal fiddling (just need to ensure every test is balanced). Note that we will know which test result means "equal" (but "left" and "right" are of course indistinguishable).

$\endgroup$
3
  • $\begingroup$ Nice proof of 14. But i don’t think your strategy distinguishes f and h. (LRLE can not be distinguished from RLRE) $\endgroup$ Aug 21, 2023 at 18:32
  • 1
    $\begingroup$ @KrisVanBael f should give ABAA and h should give ABAC (which is your LRLE or RLRE). f should never give C/"equal" since it appears in all four tests. $\endgroup$
    – tehtmi
    Aug 21, 2023 at 18:41
  • $\begingroup$ You are right. Nice answer! $\endgroup$ Aug 21, 2023 at 21:12

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.