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.

--
() ascii ribbon campaign -- against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 23/03/2021 03:26, Mike Terry wrote:

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!]

Hmm, the above works, but simpler is just to test A?B. If they balance,
C is heavy; otherwise the lighter of A,B must be light.

Mike.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Mike Terry:

ok, I thought this would be pretty easy, but in fact it
turned out to be quite hard! Definitely a good puzzle :)
[...]

A great solution, Mike. Mine was less disciplined.

--
() ascii ribbon campaign -- against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 27/03/2021 13:26, G wrote:

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

Yes, I'd wondered about that - it's plausible since the number of test
outcomes is still 27 even if all tests are given up front.

My first thought was to use the solution for the OP, but extend the
second and third weighings so that all the different cases are
incorporated into one single second and one third weighing. E.g. in my solution the third weighings (for ) typically have just one coin on each
side, but there's no harm in having more if the additional coins on each
side are known (for that scenario) to be good coins.

It seems this approach works, with minor adjustments - solution below
spoiler space...


..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..

For this to work, all three weighings must have 4 coins on each side.
(For reasons covered in my OP.)

In my solution to the original problem in another post, the first
weighing test was

ABCD?EFGH

which is OK, but in the case that the this balances, the problem becomes
IJKL (one of coins IJKL is bad, no other info) which forces a second
test such as I(X):JK. So in the second (and third, since test order
doesn't matter any more) tests, we must have exactly three of IJK in the balance. Turning this around, we must have exactly five of the original ABCDEFGH coins in each test. However, my solution had a second test of

ABEF?CG(XX)

which uses six coins - too many, so no good!

With a little more thought I see I could have used instead e.g.

ABE?CF(X) # just five coins taken from ABCDEFGH

which still works with adjustments when it comes to all the third level
tests - and this can be merged with the (only) other second level test
I(X):JK to give a single "universal" second test:

ABEI?CFJK

Then looking at the various outcomes and tests required for the third
weighing, it turns out there are just four essentially different
scenarios we can find ourselves in:
L # resolve with L?
I<JK # resolve with J?K
D<GH # resolve with G?H
AB<F # resolve with A?B
C<E # resolve with C?

The scenarios don't overlap, and there are only eight coins involved in
the resolving tests, so we can use a single universal test:

AGJL?BCHK

So that's a solution for the new problem:
1st weighing : ABCD?EFGH
2nd weighing : ABEI?CFJK
3rd weighing : AGJL?BCHK

I think that should work!

Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Carl Ginnow:

Classic "Easy to remember" spoiler is to use the ""Ma, Do Like Me To
Find Fake Coin." method...

I was *wondering* when someone was going to mention that!
--
Mark Brader "'... Fifty science-fiction magazines don't give
Toronto you half the naked women that a good issue of
msb@vex.net the Sunday Times does.'" --SPACE, James Michener

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 3/21/2021 7:57 AM, 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.

Classic "Easy to remember" spoiler is to use the ""Ma, Do Like Me To
Find Fake Coin." method below...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


Label each coin with a letter from the set (aCDeFikLMnoT). Weigh the
coins as follows:

Weighing 1: MaDo vs. Like
Weighing 2: MeTo vs. FinD
Weighing 3: Fake vs. Coin

The coin labels form the mnemonic: "Ma, Do Like Me To Find Fake Coin."
This results in an unique outcome for each of the 24 possible sets of
fake-coin and lightness/heaviness.

--
Carl G.

--
This email has been checked for viruses by AVG.
https://www.avg.com

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)