38 views

Skip to first unread message

Mar 21, 2021, 10:57:07 AM3/21/21

to

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]

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]

Mar 22, 2021, 11:26:57 PM3/22/21

to

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
> 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.

>

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.

Mar 23, 2021, 2:02:48 PM3/23/21

to

C is heavy; otherwise the lighter of A,B must be light.

Mike.

Mar 27, 2021, 6:47:05 AM3/27/21

to

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.

> 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.

Mar 27, 2021, 9:26:14 AM3/27/21

to

Anton Shepelev <anto...@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
> 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.

>

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

Mar 28, 2021, 12:34:28 PM3/28/21

to

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 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.

Mar 28, 2021, 4:50:56 PM3/28/21

to

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
> 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.

>

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

Mar 28, 2021, 5:13:42 PM3/28/21

to

Carl Ginnow:

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

m...@vex.net the Sunday Times does.'" --SPACE, James Michener

> 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

m...@vex.net the Sunday Times does.'" --SPACE, James Michener

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu