Lời giải bài toán cực khó - Tìm đồng tiền giả trong 24 đồng tiền với 3 lần cân | Reup

Có bạn đã thắc mắc về bài toán tìm một đồng tiền giả trong 24 đồng tiền. Một bài toán cực kỳ thú vị và hôm nay AD xin chia sẻ lại. Đồng thời, AD sẽ để lại lời giải chi tiết ở phía cuối video để các bạn có thể tìm hiểu thêm. Và lần này là về 24 đồng tiền. Có 24 đồng tiền. Trong đó có một đồng tiền giả khác khối lượng với các đồng tiền thật không rõ nặng hay nhẹ hơn và một chiếc cân thăng bằng điện tử thể hiện được tỉ lệ khối lượng giữa hai bên. Cụ thể là nếu bên phải nặng hơn thì số cân hiển thị lớn hơn 1. Nếu bên trái nặng hơn thì cân hiển thị nhỏ hơn 1. Nếu hai bên đĩa cân bằng thì cân hiển thị 1. Bằng 3 lần cân tìm đồng tiền giả. Đầu tiên mình muốn giải thích với các bạn rõ hơn về chiếc cân này. Cụ thể ở đây mình ví dụ phía đĩa bên phải có 110g và đĩa bên trái có 100g thì cân sẽ hiển thị chỉ số là 1.1. Sau đó tráo khối lượng vừa rồi, tức là đĩa trái có 110g, nghĩa phải có 100g thì cân sẽ hiện số 0.90909. Các bạn đã hiểu rồi chứ? Bây giờ, các bạn hãy suy nghĩ và tìm cách giải bài toán này nhé. Đầu tiên, để giải được bài này mình sẽ đưa ra giả thiết và hai mệnh đề để làm cơ sở. Các bạn hãy lưu ý kỹ các mệnh đề này. Mình đưa ra mệnh đề để khi xảy ra các trường hợp tương tự trong quá trình thực hiện sẽ không cần nêu chi tiết mà dựa vào mệnh đề tổng quát để xử lý. Giả thiết là gọi khối lượng đồng su thật là x. Khi đó nếu đồng tiền giả nhẹ hơn thì khối lượng của nó sẽ là x-n, với không nhỏ hơn n nhỏ hơn x. Nếu đồng tiền giả nặng hơn thì khối lượng nó sẽ là x-m. Mình đặt n và m để dễ dàng đưa điều kiện khi đồng tiền nặng và nhẹ. Mình sẽ đi vào một trường hợp đó là, giả sử bên cân phải nặng hơn bên cân trái. Trường hợp còn lại là bên trái nặng hơn bên phải sẽ tương tự. Cùng đi vào mệnh đề 1. Ta gọi 1-l là độ lệch của cân khi cân 2 đồng tiền mỗi bên đĩa. Khi này sẽ có 2 trường hợp xảy ra. Trường hợp A, đồng giả nhẹ hơn nằm ở đĩa bên trái. Như vậy chỉ số trên cân khi này sẽ là 2x-2x-n-1-l. Ta cùng xử lý phương trình này. Sau biến đổi, ta sẽ được x-n-l-1-2-l. Khi với 3 đồng mỗi bên thì chỉ số cân sẽ là 3x-3x-n. Thay x ở trường hợp 2 đồng ta sẽ có được chỉ số cân sẽ là 1-2-l-3-l. Tương tự với các lần cân có 4, 5, 6, 7 đồng ở mỗi bên ta sẽ có số chỉ cụ thể trên cân. Trường hợp B, đồng giả nặng hơn và nằm ở bên phải. Khi đó chỉ số cân hiển thị sẽ là 2x-m-2x-1-l. Biến đổi suy ra được x-m-2l. Với 3 đồng ở mỗi bên thì chỉ số cân hiện sẽ là 3x-m-7x. Thay x ở trên ta được chỉ số cân là 1-2-l-3. Khác với trường hợp A khi cân 3 đồng. Tương tự khi ta cân với 4, 5, 6, 7 đồng mỗi bên ta sẽ có các chỉ số cân khác nhau. Mệnh đế 2, đảo chiều 2 bên đĩa cân khi cân. Vẫn trong trường hợp đang xét. Giả sử ở lần cân đầu tiên với 2 đồng mỗi bên. Khi đó chỉ số cân là 1-l. Lần cân thứ 2, ta đổi 1 đồng từ đĩa phải sang đĩa trái. 1 đồng từ đĩa trái sang đĩa phải và cho vào mỗi bên thêm 1 đồng không bị lỗi. Vậy là mỗi bên sẽ có 3 đồng. Và mình sẽ đề cập đến trường hợp phức tạp nhất là Cân bị đảo chiều, đĩa bên trái sẽ nặng hơn đĩa bên phải do khi cháo 2 đồng ở trên. Khi này có 2 trường hợp ta xét đến. Trường hợp C, đồng giả ban đầu nhẹ hơn ở bên trái. Như vậy ở lần cân thứ nhất với 2 đồng mỗi bên, chỉ số cân sẽ là 2x-2x-n-1-l. Nên x-n-l-1-2-l. Ở lần cân 2 sau khi đảo chiều và với 3 đồng, thì chỉ số cân sẽ là 3x-n-3x. Thay x ở trên sẽ được 1-2l-3l-1. Trường hợp D, đồng giả ban đầu nặng hơn và ở bên phải. Như vậy ở lần cân thứ nhất với 2 đồng mỗi bên cân sẽ chỉ số 2x-m-2x-1-l. Nên x-m-2l. Ở lần cân 2 đảo chiều và với 3 đồng, thì chỉ số là 3x-3x-m. Thay x vào ta được chỉ số là 1-2l-3-2l. Như vậy các bạn sẽ thấy với từng trường hợp. Nhưng chỉ số trên cân sẽ khác nhau và sẽ là những con số cụ thể như trường hợp C và D. Rất rắc rối nên các bạn hãy cố gắng tập trung nhé. Bắt đầu vào xử lý bài toán. Đầu tiên, ta đánh dấu các đồng lần lượt từ 1-24. Sau đó chia thành 3 nhóm. Nhóm A, gồm 9 đồng từ 1-9. Nhóm B, gồm 8 đồng từ 10-17. Nhóm C, gồm 7 đồng từ 18-24. Ta tiến hành lần cân 1 giữa nhóm A, bên phải và B bên trái. Khi này sẽ xảy ra 2 trường hợp. Trường hợp 1. Cân chỉ số 1-1-2-5, tức là các đồng tiền trong nhóm A và B có khối lượng bằng nhau. Như vậy 1 trong 7 đồng tiền còn lại ở nhóm C có đồng giả. Lúc này, ta tiếp tục che nhóm C thành 2 nhóm tiếp theo. Nhóm C1 gồm các đồng 18-19-20 và nhóm C2 gồm 21-22, với 1 là đồng số 1 và là đồng thật. Và còn lại 2 đồng 23 và 24. Cân lần 2, cân nhóm C1, bên phải và C2 bên trái. Ta lại có 2 trường hợp xảy ra. 1. Nếu cân hiện số 1, thì 2 đồng còn lại là 23 và 24 có đồng lỗi. Ta chỉ cần tiến hành cân 1 đồng 23 hoặc 24 với 1 đồng thật bất kỳ là có thể tìm ra đồng giả. 2. Nếu cân không chỉ số 1, mà là 1 số cụ thể khác thì tất nhiên 1 trong 5 đồng 18-19-20-21-22 là giả. Giả sử nhóm C1 nặng hơn nhóm C2. Trên cân sẽ hiển thị số mà ta tạm gọi là Lc1 lớn hơn 1. Tiếp theo ta tiếp tục sắp xếp lấy đồng 23-21 sang nhóm C1. Đồng 1-4-18 sang nhóm C2. 4 đồng 1-2-3-4 thật và đồng 20 để ra ngoài. Như vậy nhóm C1 bây giờ bao gồm các đồng 2-3-19-21. Nhóm C2 bao gồm các đồng 1-4-18-22. Tương tự khi nhóm C1 nhẹ hơn nhóm C2. Cân lần 3, ta cân nhóm C1 mới bên phải với nhóm C2 mới bên trái. Nếu cân chỉ số 1, thì đồng 20 giả. Nếu cân chỉ số lớn hơn 1, gọi là Lc2. Tức là nhóm C1 mới nặng hơn nhóm C2 mới. Lúc này, chắc chắn đồng 19 hoặc đồng 22 lỗi, do 2 đồng này không di chuyển và nhóm C1 vẫn nặng hơn C2. Nên ta dựa vào mệnh điều 1 đã nêu ban đầu, và 2 chỉ số cân Lc1, Lc2 sẽ tìm ra được đồng lỗi là đồng 19 nặng hơn hay đồng 22 nhẹ hơn. Nếu chỉ số cần nhỏ hơn 1, gọi là Lc3, tức là nhóm C1 mới nhẹ hơn nhóm C2 mới. Khi đó chắc chắn đồng 18 hoặc 21 lỗi, do 2 đồng di chuyển và làm cân đảo chiều. Ta dựa vào mệnh Đ2 và 2 chỉ số cân Lc1, Lc3 sẽ viết được đồng giả thuộc trường hợp C hay D của mệnh Đ2. Ta đến với trường hợp 2, nếu cân không chỉ số 1,125, thì 1 trong 17 đồng từ đồng số 1 đến đồng số 17 là giả. Giả sự cân chỉ số lớn hơn 1,125, gọi là Lab. Như vậy trong nhóm A sẽ có đồng nặng hơn hoặc trong nhóm B có đồng tiền nhẹ hơn. Ta tiến hành sắp xếp lại 2 nhóm. Ta bỏ đồng 7,8,9 của nhóm A và đồng 16,17 của nhóm B ra ngoài. Cho 3 đồng 1,2,3 sang nhóm B. Tiếp tục 3 đồng 10,11,12 sang nhóm A. Khi đó nhóm A lúc này còn lại là những đồng số 4,5,6,10,11,12. Nhóm B vào gồm các đồng 1,2,3,13,14,15. Tiến hành cân lần 2 giữa nhóm này, nhóm A cân bên phải nhóm B cân bên trái. Lúc này sẽ có các trường hợp như sau. 1. Cân hiện số 1, thì 1 trong 5 đồng 7,8,9,16,17 là lỗi. Ta bỏ đồng số 9 ra ngoài. Ta tiếp tục sắp xếp 2 nhóm A1 gồm đồng 7,8, nhóm B1 gồm đồng 16 và 17. Sau đó tráo đồng số 8 sang nhóm B1 và đồng số 16 sang nhóm A1. Vậy bây giờ A1 sẽ gồm đồng 7,16 và B1 gồm 8,17. Cân lần 3 giữa nhóm A1 bên phải và B1 bên trái. Nếu cân chỉ số 1, 9 là đồng giả. Nếu cân chỉ số lớn hơn 1, gọi là LA1, tức là nhóm A1 nặng hơn nhóm B1. Lúc này chắc chắn đồng 7 hoặc đồng 17 lỗi. Do 2 đồng không di chuyển và cân không đảo chiều. Ta dựa vào mệnh đề 1 và chỉ số cân LAB và LA1 để xác định đồng bị lỗi ở bên nào và là đồng nặng hơn hay nhẹ hơn. Nếu cân chỉ số nhỏ hơn 1, gọi chỉ số cân hiện lên là LA2, tức là cân đã bị đảo chiều. Bên trái nặng hơn bên phải thì chắc chắn đồng 8 hoặc đồng 16 lỗi. Khi đó áp dụng mệnh đề 2 khi cân bị đảo chiều kết hợp với các chỉ số LAB và LA2 để xác định đâu là đồng giả và là nặng hay nhẹ hơn. Quay lại khi ta cân nhóm A và B ở lần cân 2. Trường hợp thứ 2 xảy ra là chỉ số trên cân hiện thị khác 1. Giả sử ở đây mình lấy trường hợp cân hiện số lớn hơn 1, gọi là LB1. Thì dựa vào lần cân thứ nhất giữa A với B, và sau khi ta di chuyển các đồng tiền. Chắc chắn 1 trong 6 đồng tiền 4, 5, 6, 13, 14, 15 là giả. Dựa vào mệnh đề 1, chỉ số cân LAB và LB1 ta có thể xác định được nhóm các đồng 4, 5, 6 hay nhóm các đồng 13, 14, 15 bên nào chứa đồng nặng hơn hoặc nhẹ hơn. Khi đó, cuối cùng ta chỉ cần cân 2 đồng trong cùng một nhóm là xác định được đồng tiền giả. Nhưng nếu trường hợp 2 ở trên mà cân hiện thị số nhỏ hơn 1, gọi là LB2, tức là cân bị đảo chiều. Như vậy theo lần cân đầu tiên giữa A và B và việc ta di chuyển các đồng tiền, thì xác định được 1 trong 6 đồng 1, 2, 3 và 10, 11, 12 là giả. Tương tự lúc này, ta dựa vào mệnh đề 2 và các chỉ số LAB, LB1 để xác định nó thuộc trường hợp C hay D của mệnh đề trên, mà tìm được nhóm đồng tiền chứa đồng tiền giả là nhẹ hơn hay nặng hơn. Sau khi xác định được nhóm chứa đồng tiền nặng hơn hay nhẹ hơn, việc đơn giản của chúng ta còn lại chỉ là cân lần 3 với việc cân trực tiếp 2 đồng trong nhóm có đồng giả là xong. Như vậy mình đã đưa ra được một phần để xử lý bài toán này, còn các trường hợp còn lại sẽ làm tương tự theo cách mà mình đã nêu trên. Hẹn gặp lại các bạn trong những video tiếp theo.