Bài toán Kiểm tra sản phẩm hay gặp

Bài toán kiểm tra sản phẩm

Giới thiêu:
Một số bài toán yêu cầu chỉ n lần cân kiểm tra M sản phẩm, làm sao tìm ra 1 sản phẩm không đạt chất lượng ( thường là trọng lượng/khối lượng-vì cho cách kiểm tra là “cân”).
Có thể các bạn đã găp bài “sản phẩm là 13 hòn bi” cách giải có nhiều; Tài liệu này nêu phương pháp sơ đồ hóa dễ hiểu hơn.

Bài toán
Bài 1:
Có 3 tổ sản xuất dép nhựa tại 1 Cty cùng “thử nghiệm” cho ra mỗi tổ 10 sản phẩm (SP); Giám đốc Cty biết rằng trong 3 tổ thì 1 tổ có SP không đạt trọng lượng.
Hỏi GD làm thế nào chỉ 1 lần cân đã phát hiên chính xác SP của tổ nào không đạt?
Giả sử các sản phẩm của cùng một tổ có trọng lượng như nhau (cùng khuôn đúc)

Giải :
GĐ dùng cân đĩa ( không cần quả cân ), chọn bất kỳ 2 trong 3 tổ, lấy mỗi tổ 1 SP đặt lên đĩa cân.
Nếu 2 SP bằng nhau thì (không cần cân nữa cũng biết SP của tổ thứ 3 không đạt;
Nếu 1 trong 2 SP lệch nhau thi đã tmf ra SP của tổ không đạt.
Bài toán dễ quá phải không ? Vì là bài mẫu mà ! Bây giờ thử giải bài tiếp sau:
Đề bài 2:
Có 13 hòn bi, trong đó có 01 hòn bi có trọng lượng khác với các hòn bi còn lại. Hãy xác định hòn bi đó chỉ trong 3 lần cân (cân hai đĩa). Lưu ý: Hòn bi này chưa biết nặng hay nhẹ hơn các hòn bi khác.
Cách giải
Lần cân thứ nhất: Đặt mỗi bên đĩa cân 4 hòn bi
*1- Nếu cân không thăng bằng:
- Gọi 4 hòn bi bên nặng là1,2,3,4. Gọi 4 hòn bi bên nhẹ là5,6,7,8.
- 5 hòn bi ở ngoài sẽ là những hòn bi chuẩn, gọi là 9, 10, 11, 12, 13
1.2- Đem cân lần 2: 1,2,3,5,6 cân với 4,9,10,11,12
1.2.1- Nếu 1+2+3+5+6<4+9+10+11+12 => Hòn bi cần tìm là1 trong số 3 hòn bi sau: hòn bi 4 (nặng hơn), hòn bi 5 (nhẹ hơn), hòn bi 6 (nhẹ hơn)
Không thể nằm trong các hòn bi 1,2,3 vì ở lần cân 1 chúng nằm ở bên nặng, lần cân 2 nằm ở bên nhẹ.
Đem cân lần 3: 5 cân với 6
1.2.1.1- 5=6 => Hòn bi cần tìm làhòn bi 4
1.2.1.2- 5<6 > Hòn bi cần tìm làhòn bi 5
1.2.1.3- 5>6 => Hòn bi cần tìm làhòn bi 6
1.2.2- Nếu cân thăng bằng 1+2+3+5+6 =4 +9+10+11+12
=> Hòn bi cần tìm là hòn bi nhẹ hơn vàl à1 trong số 2 hòn bi sau: hòn bi 7, hòn bi 8
Cân lần 3: 7 cân với 8, hòn bi nào nhẹ hơn làhòn bi cần tìm.
1.2.3- 1+2+3+5+6>4+9+10+11+12 => Hòn bi cần tìm làhòn bi nặng hơn trong số 3 hòn bi sau: hòn bi 1, hòn bi 2, hòn bi 3
Không thể là4 hoặc 5,6 vì trong 2 lần cân trên, một lần chúng ở bên nặng, một lần ở bên nhẹ.
Đem cân lần 3: 1 với 2
1.2.3.1- 1>2 => Hòn bi cần tìm làhòn bi 1
1.2.3.2- 1<2 > Hòn bi cần tìm làhòn bi 2
1.2.3.3- 1=2 => Hòn bi cần tìm làhòn bi 3
2- Nếu cân thăng bằng:
1+2+3+4=5+6+7+8 => hòn bi cần tìm nằm trong số 5 hòn bi 9,10,11,12,13
Đem cân lần 2: 1,2,3 cân với 9,10,11
2.1- Cân thăng bằng 1+2+3=9+10+11 => Hòn bi cần tìm làhòn bi 12 hoặc 13
Đem cân lần 3: 1 cân với 12
2.1.1- Cân không thăng bằng 1#12 => Hòn bi cần tìm làhòn bi 12
2.1.2- Cân thăng bằng 1=12 => Hòn bi cần tìm làhòn bi 13
2.2