Re: puzzles, coin weighing, coding

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

Hi forks, 

Life is so bored here as everywhere ha' :(

Vu~ Quo^'c Hu`ng wrote:

> Sorry ca'c ba'c, ho^m qua tui ngoi la^u tren truong ne^n me^.t va`
> viet nha^`m 15 coins tha`nh 13 coins. De^~ hieu la` khi puzzle of 12
> coins co' lo+`i giai thi` 13 coins cu~ng co'.

> Khi bo.n to^i ddo^' nhau ba`i 112 coins, to^i co' anh ba.n chi? ra
> ca'ch so sa'nh 5-5 o+? ngay la^`n dda^`u, neu le^.ch ca^n ha('n
> va^~n ti`m ra lo+`i gia?i !?, => bai` to'an co' lo+`i gia?i cho ca? 
> truong ho+.p 15 coins !! Nhu+ng to^i k0 nho+' ha('n ca^n nhu+ the^'
> na`o vi` qua' la^u roi.

> Ba'c na`o co' y' gi` hay khi so sa'nh 5-5 ?

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.