Re: puzzles, coin weighing, coding

[Dung Trong Nguyen <nguyen@jaist.ac.jp>]

Dao thi Bich Hanh <dao@esil.univ-mrs.fr> wrote:

> Xin tro+? la.i ba`i toa'n coin weighing. To^i nghi~ la` ne^'u ta co'
> 24 coins trong ddo' co' 1 coin na(.ng ho+n hay nhe. ho+n, thi` vo+'i
> 3 la^`n ca^n, ta va^~n co' the^? xa'c ddi.nh ddu+o+.c coin na`o la`
> coin na(.ng (nhe.) ho+n\.

Dung Trong Nguyen <nguyen@jaist.ac.jp> wrote:

> Consider the problem of n coins numbered. We will write down the
> results of the three weightings as a triple like this:

>	<?, ?, ?>

> Where each slot can be either e(qual), l(ighter), or h(eavier). The
> number of all possible triples is 3x3x3 = 27.

> If from a triple we can state a coin is the fake, then we also can
> state that the fake is lighter or heavier than a genuine if the
> triple isn't <e, e, e>.  Because it is only information one based
> on, a triple can lead to at most one statement (which coin is the
> fake and about its weight if possible). One can see that for n coins
> problem there are either 2n or 2(n - 1) + 1 different possible
> statements, depend on the triple <e, e, e> in use or not.  In either
> case we have:

> 	2n - 1 <= 27

> or

>	n <= 14

> We can repeat this argument to show that 14 coins problem is
> unsolvable by a similar scheme of resolution [VQH]. It seems
> actually unsolvable but a subtler proof may be required.

> Needless to say no man can solve 15 coins problem.

Hi folks,

Let's complete the proof for the case of 14.  On the first weighting,
we need at least divide the coins into 2 groups to weigh.  If we just
divide them into 2 groups, then the result would be only either h or
l.  We have totally 18 possible triples of <h, ?, ?> and <l, ?, ?>,
surely not enough for 14 coins problem who needs 27 triples at least
to identify the fake.

Hence we should divide our coins into 3 groups. Furthermore the 2
groups those will be weighed should have the same number of coins as
we can't interpret meaningfully the outcome of the weighting
otherwise.  Let m be this number, the numbers of coins of groups will
be: m, m and 14 - 2m.

Suppose we have e on the first weighting, then the fake hides itself
in the 3rd group.  We have 9 triples of <e, ?, ?> to identify the it
(the fake) among 3rd group.  As the consequence the 3rd group can be 5
coins at most.  Hence we have

	14 - 2m <= 5

or

	9 <= 2m

If the outcome is not e on the first weighting, we would have 18
triples of <h, ?, ?> and <l, ?, ?> to identify the fake among 2 groups
1 and 2.  Because <e, e, e> is not among the triples, we know that we
can deal with 9 coins at most, or

	2m <= 9

With the previous equality, it comes to

	2m = 9

It seems that we don't have the permission of cutting a coin in half,
or the problem of 14 coins can't be solved.

Now we can say: no man can solve the problem of more than 13 coins.
Consequently, no woman can do it neither.

Cheers, d~