Cân xu

NQH | 04/08/2010 |

Bạn Huân hỏi về một bài toán đố cổ điển: bài toán cân xu tìm xu giả. Phiên bản thường nghe là như thế này: cho 12 đồng xu trong đó có 1 đồng xu giả (không biết nặng hay nhẹ hơn các đồng khác) và một cái cân thăng bằng, cân 3 lần tìm đồng xu giả.

Có rất nhiều biến thể (tổng quát) của bài toán này. Xem bài báo này chẳng hạn. Cho $n$ đồng xu, $b$ cái cân, $k$ đồng xu giả, có thể biết hoặc không biết trước là nặng hay nhẹ hơn các đồng thật; phép thiết kế chiến lược cân có được “adaptive” hay không, vân vân. Thật ra câu này hỏi bác Văn là thích hợp nhất. Bác Văn có mấy bài báo rất thú vị về các biến thể tổng quát của bài toán cân xu.

Trong khuôn khổ bài viết này, ta chỉ xét một biến thể cổ điển sau:

(Một phiên bản của bài toán tìm xu giả) Cho $n$ đồng xu, $1$ đồng giả không biết nặng hay nhẹ hơn các đồng thật thế nào, và một cái cân. Tìm số lần cân $w$ ít nhất để chỉ ra đồng giả (nếu có) và chỉ ra luôn là nó nặng hay nhẹ hơn các đồng thật.

Câu hỏi này thật ra có hai phần: phần 1 là tìm một chiến lược chỉ ra đồng giả dùng $w$ lần cân, và phần 2 là chứng minh rằng $w-1$ lần cân thì không đủ để chỉ ra đồng giả. Ta sẽ tìm liên hệ giữa $w$ và $n$ . Phần 2 thú vị hơn phần 1, nhưng về cơ bản cũng là chặn thông tin. Do việc tìm chặn thông tin là kỹ thuật rất phổ biến trong thuật toán và lý thuyết tính toán, chúng ta sẽ duyệt qua cả hai phần.

1. Chiến lược cân

Chiến lược này chỉ là phép “chia-để-trị” (divide-and-conquer). Có lẽ là ai nghĩ một lúc rồi thì cũng ra. Bắt đầu từ trường hợp $n$ nhỏ, từ $3$ đến khoảng $12$ là thấy rõ chiến lược ngay. Đại khái, chiến lược cũng giống như trong lời giải cho $n=12$ : chia xu làm ba nhóm gần đều nhau, nếu cân cân bằng thì qui nạp cho nhóm nằm ngoài. Nếu cân không cân bằng thì nhóm nằm ngoài chứa toàn xu tốt, và ta có thể dùng chúng để so sánh với các xu ở trong. Bằng cách hoán đổi một số xu ở trong với nhau, ta lại có thể áp dụng qui nạp lần nữa. Thử với các giá trị $n$ nhỏ, ta dễ dàng “conjecture” định lý sau đây:

Định lý: với $w$ lần cân thì ta có thể chỉ ra xu giả (nếu có) trong $n$ xu nếu

$n \leq \frac{3^w-1}{2}-1$

Ngoài ra, ta cũng biết luôn là xu giả nhẹ hay nặng hơn các xu thật.

Chứng minh. Có thể giả sử $n\geq 3$ , và $\frac{3^{w-1}-1}{2} \leq n \leq \frac{3^w-3}{2}$ . Tại vì nếu $n \leq \frac{3^{w-1}-1}{2}-1$ thì giả thiết qui nạp cho ta biết $w-1$ lần cân là xong. Ta chia đống xu thành ba nhóm. Hai nhóm đặt lên hai đĩa cân mỗi nhóm có kích thước bằng $a = \left\lceil \frac 1 2 \left(n - \frac{3^{w-1}-1}{2} \right) \right\rceil$ . (Nếu $n = \frac{3^{w-1}-1}{2}$ thì định nghĩa $a=1$ .) Con số $a$ này được chọn để cho chúng ta có thể áp dụng giả thiết qui nạp trên mỗi nhóm. Nhóm nằm ngoài cân có $n-2a$ xu. Dễ thấy rằng

$1 \leq a \leq \frac{3^{w-1}-1}{2}$ và $1 \leq n - 2a \leq \frac{3^{w-1}-1}{2}$ .

Nếu cân thăng bằng thì ta áp dụng giả thiết qui nạp cho nhóm nằm ngoài. Xong!

Nếu cân không thăng bằng thì bây giờ ta có hai nhóm xu: nhóm đen là nhóm bên nặng hơn có $n_1=a$ xu, nhóm trắng là nhóm bên nhẹ hơn có $n_2 = a$ xu. Nhớ rằng $n_1+n_2 \leq 3^{w-1}-1$ . Ngoài ra, chúng ta còn có ít nhất một đồng xu thật ở ngoài để làm “neo”. Ta chứng minh kết quả tổng quát hơn sau đây, và bổ đề này sẽ hoàn tất chứng minh định lý trên.

Bổ đề. Giả sử ta có hai nhóm xu, nhóm thứ nhất gọi là “nhóm đen” có $n_1\geq 0$ xu và có thể bao gồm một xu giả nặng hơn xu thật. Nhóm thứ hai gọi là “nhóm trắng” có $n_2$ xu và có thể bao gồm một đồng xu giả nhẹ hơn xu thật. Ngoài ra ta còn có một xu thật làm “neo” ở ngoài hai nhóm. Ta biết rằng chỉ có một xu giả trong cả hai nhóm, và $n_1+n_2 \leq 3^k$ . Ta có thể cân $k$ lần để chỉ ra xu giả.

Chứng minh. Lại qui nạp. Thứ nhất, nếu $n_1=0$ hoặc $n_2=0$ thì chứng minh bài toán không khó gì. Đây là trường hợp đặc biệt của bài toán tìm xu giả khi mà ta biết là xu giả nặng hơn hoặc nhẹ hơn xu thật. (Bài tập.) Do đó có thể giả sử $n_1,n_2\geq 1$ . Các trường hợp $n_1+n_2\leq 3$ cũng tầm thường, nên ta giả sử $k\geq 2$ .

Nếu $n_1+n_2\leq 3^{k-1}$ thì ta áp dụng giả thiết qui nạp.

Xét $3^{k-1}+1 \leq n_1+n_2 \leq 3^k$ . Đặt $a = \left\lceil \frac 1 2 \left(n_1+n_2 - 3^{k-1} \right) \right\rceil$ . Khi đó ta có

$1 \leq a \leq 3^{k-1}$ và $2 \leq 3^{k-1}-1 \leq n_1+n_2 - 2a \leq 3^{k-1}$ .

Đặt lên hai đĩa, mỗi đia $a$ xu, sao cho số xu đen trên hai đĩa bằng nhau và số xu trắng trên hai đĩa bằng nhau. (Bài tập tại sao luôn làm được điều này?)

Nếu cân thăng bằng thi áp dụng giả thiết qui nạp cho đám xu nằm ngoài cân.

Giả sử bên trái nhẹ hơn thì xu giả nằm trong đám xu trắng bên trái hoặc trong đám xu đen bên phải. Áp dụng qui nạp. Xong!

2. Chặn thông tin

Ta chứng minh rằng, nếu $w$ lần cân là đủ thì $n \leq \frac{3^w-1}{2}-1$ . Mỗi một lần cân cho ra một trong ba kết quả: đĩa trái nặng hơn, đĩa phải nặng hơn, hoặc nặng bằng nhau. Có tất cả $w$ lần cân; vì thế, tổng số kết quả có thể có là $3^w$ . Tổng số chọn lựa trạng thái mà ta cần xác định là $2n+1$ (mỗi xu đều có thể giả, và nặng hoặc nhẹ hơn xu thật, hoặc không có xu giả nào). Do đó, $2n +1\leq 3^w$ . Cái chặn này còn yếu một xíu, nhưng nó cho ta thấy ý tưởng chính.

Bây giờ giả sử lần cân thứ nhất có $a$ xu trên mỗi đĩa cân. Nếu cân thăng bằng thì trong $w-1$ lần cân còn lại ta cần phân biệt $2(n-2a)+1$ trạng thái. Do đó $2(n-2a)+1 \leq 3^{w-1}$ . Nếu cân không thăng bằng thì nhóm ngoài là nhóm xu thật, ta cần phân biệt $2a$ trạng thái vì nhóm trong có xu giả. Do đó $2a \leq 3^{w-1}$ . Nhưng $2a$ là chẵn nên $2a \leq 3^{w-1}-1$ . Ta kết luận rằng

$n \leq (3^{w-1}-1)/2 + 2a \leq (3^{w-1}-1)/2 + 3^{w-1}-1 = (3^w-1)/2 - 1.$

Chủ đề : Combinatorics, Thuật Toán and tagged cân xu, Combinatorics, Thử nhóm. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

6 Comments

Nguyễn Văn Huân

Posted 05/08/2010 at 10:11 am | Permalink

Cảm ơn anh đã để ý đến câu hỏi của em, em rất thích bài viết này!
Hiện tại em đang tìm hiểu về nhận dạng, em không chắc là anh Hưng có nghiên cứu về lĩnh vực này hay không, em muốn tham khảo một vài bài viết và cũng có nhiều vấn đề chưa hiểu thấu. Nếu anh Hưng có biết ai làm về nhận dạng thì giới thiệu giúp em với! Bài toán hiện tại của em là “Nhận dạng đối tượng chuyển động.” Vì đang là sinh viên năm thứ 3 nên em cũng chỉ dừng lại ở mức của sinh viên thôi, tuy nhiên ngang đó em đã thấy đủ thứ để làm!

Reply
pandarbear

Posted 06/08/2010 at 1:20 am | Permalink

Định lý giới hạn số lần cân so với số quả cân chưa chính xác.

Ví dụ với w = 2; Theo định lý thì số quả cân là n<= 3
Nhưng với 4 đồng xu có thể chỉ ra xu giả trong 2 lần cân, cụ thể

Cân 2 đồng trước
Nếu bằng nhau: Hai đồng trên cân là thật lấy một đồng ra và cân với một trong hai đồng chưa cân còn lại
Nếu bằng: đồng chưa cân là giả
Không bằng: đồng đem lên cân là giả
Lệch nhau: Một trong hai đồng đem cân là giả, 2 đồng chưa cân là thật, đem một đồng thật lên cân với một trong hai đồng ban đầu ta định được đồng giả

Reply
a bc

Posted 06/08/2010 at 2:15 am | Permalink

@pandar: nhung nhu the ta khong co biet xu gia nang hay nhe. Nhu vay, cai theorem do van dung.

Reply
Nguyễn Văn Huân

Posted 06/08/2010 at 5:52 am | Permalink

Nếu $n_1=0$ hoặc $n_2=0$ , gọi số xu là $n$ giả sử $n>2*3^{w-1}$ (nếu nhỏ hơn hoặc bằng thì càng dễ), chia xu làm 3 phần, trong đó 2 phần bằng $3^{w-1}$ xu, đặt 2 phần này lên cân. Nếu cân thăng bằng thì xu giả nằm bên ngoài, số lượng xu bên ngoài nhỏ hơn hoặc bằng $3^{w-1}$ , nếu cân không thăng bằng, ta còn lại $3^{w-1}$ xu vì đã biết xu giả nặng hơn hay nhẹ hơn xu thật.
Lặp lại bước trên, sau mỗi bước từ chỗ $n \leq 3^{w}$ sẽ giảm xuống $n \leq 3^{w-1}$ và không quá $w$ bước ta sẽ tìm ra xu thật!

Theo như phương pháp mà anh Hưng chỉ ra thì với phiên bản 12 xu em sẽ giải như thế này:
Chia 12 đồng xu thành 3 phần 4 – 4 – 4.

1. Lần cân đầu tiên đưa 2 phần lên cân với nhau,

* Trường hợp cân thăng bằng ta xác định được 8 đồng xu thật, còn 4 đồng xu chưa rõ có thể dễ dàng xác định bằng 2 lần cân còn lại.

* Trường hợp cân bị lệch, gọi $D_1, D_2, D_3, D_4$ là 4 đồng xu bên nặng, $T_1,T_2,T_3,T_4$ là 4 đồng xu bên nhẹ sau đó đặt các xu $D_1, D_2, T_1$ cân với $D_3, D_4, T_2$ . Nếu cân thăng bằng ta có 1 trong 2 xu $T_3$ và $T_4$ là giả, tiến hành lần cuối cùng ta tìm ra được xu giả. Trường hợp cân bị lệch, nếu $D_1, D_2, T_1 > D_3, D_4, T_2$ như vậy đồng xu giả sẽ nằm trong $D_1, D_2$ hoặc $T_2$ . Tại sao? vì $D_3, D_4$ thuộc phần nặng trong lần cân đầu tiên, bây giờ lại thuộc phần nhẹ cho nên không thể là xu giả, xu $T_1$ cũng tương tự như vậy. Như vậy, với 1 lần cân còn lại có thể dễ dàng xác định $D_1, D_2$ hay $T_2$ là xu giả. Lập luận tương tự với trường hợp $D_1, D_2, T_1 > D_3, D_4, T_2$ . Ở đây $a=3$ và số xu trắng trên mỗi đĩa là bằng 1 hoặc 2, thế nào cũng được!

Reply
Xuân

Posted 11/08/2010 at 3:56 pm | Permalink

Không biết anh Hưng đã đọc tin này chưa ạ:
http://www.newscientist.com/article/dn19287-p–np-its-bad-news-for-the-power-of-computing.html
Em có trích và post câu hỏi cả trên Phdvn:
http://phdvn.org/computer-science/1604-p-np-its-bad-news-power-computing.html#post15224

Reply
Ngô Quang Hưng

Posted 11/08/2010 at 4:01 pm | Permalink

Chào Xuân, chứng minh của Deolalikar 99 phần trăm là sai. Bạn xem các phát triển về chủ đề này ở đây.

Reply