Thuật toán "Chia ba" cân vàng, bi, bóng

Thuật toán chia ba: Cân bi - cân Vàng

I.- Giới thiệu:

Trong một số đề thi HSG, thi tin hoc có những bài toán yêu cầu dùng cân phát hiện 1 trong số “viên bi”, “bóng” , “nhẫn” ...không đủ trọng lượng nằm trong tổng thể n “sản phẩm”. Đó không phải là toán “Mẹo”, mà phải dùng thuật toán và suy luận để sao cho chỉ cần tối thiểu m lần cân , đủ để phát hiện. Các đề đó cũng chưa nằm trong kiến thức xác suất, mà chỉ trong các phép cộng trừ nhân chia đơn giản.
Tài liệu này giới thiệu vài bài mẫu áp dụng thuật toán “chia ba” lắt léo nhưng thú vị.

II,- Bài mẫu:
Đề 1:
Có 8 quả bóng hoàn toàn giống nhau về hình thể, màu sắc, kích thước; nhưng 1 quả nhẹ cân không đảm bảo cho cuộc thi đấu quan trọng. Làm sao chỉ 2 lần cân đã phát hiện, loại bỏ quả bóng đó ?
Giải:
*Nếu không khống chế số lần cân thì cứ chía đôi 8/2 =4, rồi 4/2 =2 và 2/2=1 lần lượt sẽ ra, nhưng phải 3 lần cân.
* Dùng thuật toán “chia ba” như sau: 8 quả bóng chia làm 3 phần ( 2 phần đặt lên 2 đĩa cân, mỗi phần 3 quả, phần còn lại 2 quả để ngoài
-Tình huống 1a : 2 đĩa cân thăng bằng, nghĩa là quả thiếu cân nằm trng 2 quả để ngoài. Vậy chỉ việc cân 2 quả ngoài đã phat hiện quả thiếu cân.
-Tình huống 1b: Một đĩa 3 quả nhẹ cân thì đêm 3 quả này chia 3 1 quả đặt ngoài, 2 quả kia lên đĩa cân. Chắc chắn sẽ phát hiện quả thiếu cân.
Vậy tình huống nào cũng chỉ cần cân 2 lần ( Đáp án )



Đề 2 :
“Có 80 cái nhẫn.trong đó 1 cái nhe hon 79 cái kia. Làm sao chi cân 4 lần mà lấy được chiếc nhẫn nhe hơn khỏi 79 chiếc kia”. .
Giải:
Cân theo sơ đồ sau:
* Lần I Mỗi đĩa 27 cái ( 27 x2 = 54; cái còn để ngoài 26 *). Nếu 2 đĩa thăng bằng thi cân số 26 để ngoài theo sơ đồ *****. Nêu 1 đĩa 27 cái nhẹ hơn thì cân lấn II
** Lần II: Mỗi đĩa 9 cái; để ngoài 9 cái. Nếu phát hiện một trong số lô 9 cái nhẹ thi cân lần III.
*** Lần III: Mỗi đĩa cân đặt 3 cái, Để ngoài 3 cái .Nếu phát hiện một trong số lô 3 cái nhẹ thi cân lần IV.
**** Lần IV: Dễ dàng phát hiên đúng cái nhẹ hơn khi đặt mỗi cái / 1 đĩa.

***** Lần II (cho trường hợp rơi vào 26 cái để ngoài lần I) Đặt mỗi đĩa 9 cái ; 8 để ngoài. Nếu phát hiên lô 9 cái thì cân tiếp theo sơ đô ***. Nếu rơi vào lô 8 ngoài thì cân lần III
****** Lần III ( cho lô 8 cái ): Đật mỗi đĩa 3 cái, để ngoài 2. Nếu rơi vào lô 3 cái thì cân tiêp theo sơ đồ ****(lần IV) . Còn nếu phát hiện lô 2 cái thì cân lần IV.
Đến đây thì quá dễ để tìm cái nhẫn thiếu cân. (xem sơ đồ minh họa)


Vậy tình huống nào cũng chỉ cần cân 4 lần ( đúng Đáp án )
III.- Nhân xét chung:

*Cả 2 bài mẫu trên các lần cân đều chia ba tổng số “sản phẩm” để cuối cùng chỉ còn 2 mới chia đôi (tất nhiên vì hết cách chia ba ). Cũng vì thế gọi thuật toán này là “thuật toán chia ba”.
* Dựa theo thuật toán này người ta có thể thay đổi dữ kiện n ( số sản phẩm) và m ( số lần cân cho phép) để ra đề. với n > m, trong đó m phụ thuộc n như sau



Thường đề ít khi cho n là một số chia hết cho 3 mà hay cho số chẵn, sấp xỉ; thí dụ đáng lẽ cho n = 9, 27, 81... thi lấy n = 8, 24 , 80...Để đánh bẫy người cứ quen chia đôi.
* Sơ đồ trên , số m là số lần cân ít nhất tương ứng với n sản phẩm; Nếu đề cho ít hơn các mốc trên thì bài toán không giải được. Việc chứng minh phức tạp xin miễn trình bày..
* Một tình tiết nữa là thường Đề chỉ ra điều kiên số lần cân, không ra điều kiên dùng cân loại gì. Mặc dù thuật toán này chỉ ứng dụng cho lọai Cân 2 đĩa, không cần dùng quả cân, Bài toán cổ mà !

IV.- Bài thực hành:

Đề : Có 16 viên bi giống nhau về hình thể, màu sắc, kích thước