Enjoy this puzzle if you have not solved it already:
Given are twelve coins of idential appearance, among which
one forged and has a sligntly different weight. Using a
precision balance, your task is to find the forged coin and
determine whether it be lighter or heavier than the
authentic ones, in but three weightings.
On 21/03/2021 14:57, Anton Shepelev wrote:
Enjoy this puzzle if you have not solved it already:
Given are twelve coins of idential appearance, among which
one forged and has a sligntly different weight. Using a
precision balance, your task is to find the forged coin and
determine whether it be lighter or heavier than the
authentic ones, in but three weightings.
ok, I thought this would be pretty easy, but in fact it turned out to be quite hard! Definitely a good puzzle :)
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
Rather than just explaining an answer, I'll try to explain how I might
have found the answer quite easily. (The truth is it came to me mostly
by experimenting and eliminating things which didn't work, and coming to realise that certain simpler puzzles could be solved with one or two weighings... Only when I looked back on it I saw simplifications that
could have saved me some time, and came up with a concise notation that helps!)
So to start with we have three weighings, and each has 3 possible
results (left<right, left=right, left>right), which give a maximum of 3x3x3=27 outcomes. There are 12x2=24 configurations to distinguish (the
fake coin is one of 12, and could be light or heavy) and 24 < 27, so a solution is plausible, but needs to be quite tight - each test outcome
has to reduce the remaining states to be distinguished by roughly 1/3,
with only a little leeway.
For example weighing 6 coins on each side as the first measurement is a non-starter, because there are only 2 outcomes we can get, reducing
total testing outcomes (for all 3 tests) to 2x3x3=18 which is less than
the number of starting states we need to distinguish. (So this can
never work!)
In fact, a similar argument shows that to give a solution, the first
weighing must be 4 coins on each side. If we weigh 3 or less on each
side, they may balance, and then the fake coin is one of at least 6 and that's all we know - so there would be (at least) 12 states to
distinguish and just 2 weighings left, which can give only 9 outcomes: failure! And if we weigh 5 or more, and they contain the fake coin,
there will be at least 10 states left to distinguish (10 coins, any of
which might be the fake coin). Again we only have two tests left, so 9 outcomes : failure again.
So Weighing #1 MUST take 4 coins on each side, leaving 4 unweighed. This makes sense in terms of states to be distinguished/remaining test
outcomes, e.g. if left=right (scale balances) the fake coin must be one
of the 4 unweighed coins, giving 8 states left to distinguish in 2
weighings (possible 9 outcomes, so this is ok). If left<right, the fake
coin is one of the eight weighed (8 states left to distinguish in 2
weighings (9 possible outcomes, so this is plausible too).
Once we've seen how to quickly eliminate tests that can't work, the
whole puzzle becomes tractable, we just need to build a tree of tests to
make given previous test results, tracking what we have deduced at each stage. Also it helped when I realised that with *one* test, if we have
3 states left to distinguish we can easily solve this for the case where [either coins A or B are light or C is heavy]. I'll use *notation* AB<C
to describe this mini-problem from now on, e.g. in the weighing tree
below. To solve AB<C (note: 3 states to distinguish, 3 possible test outcomes) we compare coins A and C with X and Y where X,Y are each one
of the "known good" coins, which are all equivalent for our purposes).
I'll use *notation* AC?XX to descibe such a test from now on - note both
good coins on the right both are shown as X, since we don't care which
good coin is used.
Here's a mini-test-tree for the mini-problem in my notation:
AB<C # starting knowledge : either A or B is light, or C heavy
AC?XX # test to perform, weigh A and C on left, against 2 good coins
=: # test result: scales balance, giving new knowledge AC=
# [A and C are good] which combines with AB<C to give:
ANSWER: B< [B is light!]
<: # test result: left side < right, so new knowledge: AC<
# which combines with AB<C to give C=, and so..
ANSWER: A< [A is light!]
>: # test result: left side > right, so new knowledge: <AC
# which combines with AB<C to give A=, and so..
ANSWER: <C [C is heavy!]
Interestingly, we can't solve ABC< in one weighing, even though there
are only 3 possible states to distinguish and 3 test outcomes. (Try it!)
So here is my solution tree for the full problem. Most tests at each
stage would obviously fail due to leaving too many states to distinguish
in remaining test outcomes (as illustrated many times above) so I just
chose tests look like they will (for each of 3 outcomes) reduce the
possible remaining states to distinguish by enough, i.e. roughly by a
factor of 3. If all the branches in the tree lead to a successful
outcome we have solved the puzzle!! :)
To shorten the tree and make it easier to follow, I've generally stopped
at the 2nd level of branching, because the 3rd test is obvious and
clearly works. If I completed the tree formally, it would mean adding 6
more lines saying the same obvious thing! In many cases I claim success
on the basis that we have reduced the problem to A<BC problem considered above, and there's no point in repeating that over and over...
ABCDEFGHIJKL # start: 12 coins, no knowledge of which is light/heavy ABCD?EFGH # first test..
=: # now know ABCDEFGH=, i.e. new problem is:
IJKL # (this is EASY to solve in 2 weighings!)
IJ?KX # 2nd test
=:
L # Success - just compare L?X to decide heavy/light
<:
IJ<K # Success - see mini-problem
>:
K<IJ # Success - see mini-problem
<: # now know IJKL=, i.e. new problem is:
ABCD<EFGH # new problem (not so easy, but
# inspired by IJKL problem...)
ABEF?CGXX # 2nd weighing
=:
D<H # Success - just compare DH?XX (or D?X etc.)
<:
AB<G # Success - see mini-problem
>:
C<EF # Success - see mini-problem
>: # now know IJKL=, i.e. new problem is:
EFGH<ABCD # This branch just mirrors the <: branch above
# with obvious changes of letters, so..
# Success!
Er, that's it.
Mike.
ok, I thought this would be pretty easy, but in fact it
turned out to be quite hard! Definitely a good puzzle :)
[...]
Enjoy this puzzle if you have not solved it already:
Given are twelve coins of idential appearance, among which
one forged and has a sligntly different weight. Using a
precision balance, your task is to find the forged coin and
determine whether it be lighter or heavier than the
authentic ones, in but three weightings.
Anton Shepelev <anton.txt@gmail.com> wrote:
Enjoy this puzzle if you have not solved it already:
Given are twelve coins of idential appearance, among which
one forged and has a sligntly different weight. Using a
precision balance, your task is to find the forged coin and
determine whether it be lighter or heavier than the
authentic ones, in but three weightings.
The already given solutions are fine, but there is a variant af this puzzle that is a little more complex:
Same stuff as above but you have to tell me in advance the three weighings without knowing any result.
G
Classic "Easy to remember" spoiler is to use the ""Ma, Do Like Me To
Find Fake Coin." method...
Enjoy this puzzle if you have not solved it already:
Given are twelve coins of idential appearance, among which
one forged and has a sligntly different weight. Using a
precision balance, your task is to find the forged coin and
determine whether it be lighter or heavier than the
authentic ones, in but three weightings.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 322 |
Nodes: | 16 (0 / 16) |
Uptime: | 149:33:41 |
Calls: | 7,072 |
Calls today: | 1 |
Files: | 12,494 |
Messages: | 5,499,420 |