Re: puzzles, coin weighing, coding

[Dao thi Bich Hanh <dao@esil.univ-mrs.fr>]

Cha`o ca'c ba'c,

Tru+o+'c tie^n, xin lo^~i ca'c ba'c vi` message ho+i da`i. 

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

1.
Tru+o+'c he^'t, ta xe't tru+o+`ng ho+.p 8 coins vo+'i 2 la^`n ca^n\.
Chia 8 coins tha`nh 3 nho'm go^`m 3, 3 va` 2 coins. 

La^`n ca^n thu+' nha^'t :  So sa'nh (ca^n) hai nho'm 3,3 coins. 
 - Ne^'u hai nho'm na(.ng ba(`ng nhau, the fake coin na(`m trong 
nho'm go^`m 2 coins co`n la.i, 
   ne^'u kho^ng, ta xa'c ddi.nh ddu+o+.c nho'm 3 coins na`o chu+'a
the fake coin va` dda~ quye^'t ddi.nh ddu+o+.c la` no' na(.ng hay
nhe. ho+n
 
La^`n ca^n thu+' hai:
 - Ne^'u the fake coin na(`m trong nho'm 2 coins, ta ca^n 2 coins ddo'
va` xa'c ddi.nh ddu+o+.c the fake coin cu~ng nhu+ bie^'t ddu+o+.c la` 
no' na(.ng ho+n hay nhe. ho+n
 - Ne^'u the fake coin na(`m trong nho'm co' 3 coins, ta ca^n 2 coins
ba^'t ky` trong 3 coins ddo'. 
     - ne^'u 2 coins ddo' ba(`ng nhau ve^` kho^'i lu+o+.ng, thi`
coin thu+' ba se~ la` coin fake, va` tu+` la^`n ca^n tru+o+'c, ta dda~
bie^'t ddu+o+.c la` no' na(.ng hay nhe. ho+n
     - ne^'u kho^ng thi` trivialement ta xa'c ddi.nh ddu+o+.c coin fake

2.
Ba(`ng ca'ch tu+o+ng tu+., vo+'i 2 la^`n ca^n, ta co' the^? xa'c ddi.nh
ddu+o+.c the fake coin trong 3,4,5,6,7 coins. Ta co' the^? chia nho'm
nhu+ sau :
	3 coins : 1,1,1
	4	: 1,1,2
	5	: 2,2,1
	6	: 2,2,2
	7	: 3,3,1

3.
Xe't tru+o+`ng ho+.p 24 coins vo+'i 3 la^`n ca^n\. Chia 24 coins ddo'
tha`nh 3 nho'm mo^~i nho'm co' 8 coins.

La^`n ca^n thu+' nha^'t : ca^n giu+~a hai nho'm 8 coins. Hoa(.c hai
nho'm ddo' co' kho^'i lu+o+.ng ba(`ng nhau, khi ddo' the fake coin
na(`m trong nho'm thu+' ba. Ne^'u kho^ng, mo^.t trong hai nho'm ddo'
chu+'a the fake coin.

Ta xe't nho'm 8 coin co' chu+'a the fake coin. Ba(`ng hai la^`n ca^n
co`n la.i nhu+ tri`nh ba`y o+? mu.c 1, ta xa'c ddi.nh ddu+o+.c the
fake coin va` tu+o+ng quan kho^'i lu+o+.ng cu?a no'.

4.
Vo+'i ca'c tru+o+`ng ho+.p co' N coins, N <= 24, ta co' the^?
chia tha`nh ca'c nho'm nhu+ sau (chi? ca^`n co' hai nho'm co' so^' coins
ba(`ng nhau, mo^~i nho'm co' nhie^`u nha^'t 8 coins) :
	15 coins : 5,5,5 hay 4,4,7
	16 	 : 5,5,6 hay 6,6,4 hay 7,7,2
	...
	23	 : 8,8,7
	24 	 : 8,8,8


Regards
BHanh