Chung minh rằng : , ta gọi x là số lần cân ( cân thằng bằng) , x là số tự nhiên ≥ 3 , , ta luôn tìm 1 đồng bị lỗi qua số qua số lân cân là x và số đồng tối đa là:
2.(3^x-2+ 3^x-3+3^x-4...+3^x-x) +(3^x-2+ 3^x-3^x-4...+3^x-x)+ 4-x
trong đó luôn tìm được 1 đồng tiền bị lỗi .
bài toán có 13 đồng tiền trong đó có 1 đồng bị lỗi không biết nặng hơn hay nhẹ hơn đồng tiền còn lại qua 3 lần cân thăng bằng tìm gia đồng bị lỗi. Lời giải:
Ta đánh đấu từng đồng bằng các số từ 1 đến 13 , ta chia thành 3 nhóm nhóm A là nhóm có số đồng từ số 1 đến số 4 , nhóm B có số đồng từ 5 đến 8 , nhóm C có số đồng từ 9 đến 13 , lần cân thứ nhất: ta cho nhóm A cân với nhóm B nếu cân thằng bằng thì nhóm C sẽ có 1 đồng bị lỗi , ta cho đồng 12 , 13 gia ngoài, cho thêm đồng số 1 vào cùng với đồng số 9 cho lên cân vơi đồng số 11 và đồng số 10 nếu cân thăng bằng thì đồng số 1 2 và đồng số 13 có 1 đồng bị lỗi . Ta cân 1 trong 2 đồng trên vơi bất kể đồng còn lại nào thì có thể tìm gia được đồng bị lỗi, nếu cân lệnh ta gi nhớ xem nhóm nào nặng hơn , vậy là trong 3 đồng 9, 10, 11 có 1 đồng bị lỗi , lần cân thứ 3 ta cho đồng số 10 cân với đồng số 11 nếu cân thăng bằng thì đồng số 9 bị lỗi còn cân lệch thì đồng số 11 và 10 có 1 đồng bị lỗi ta lấy 2 đồng cân vơi nhau và để ý xem đồng nào cùng nặng hoặc cùng nhẹ như nhóm này ở lần cân số 2 là đồng bị lỗi.
Quay chở lại trường hợp cân nhóm A với Nhóm B nếu cân không thăng bằng ta gi nhớ xem nhóm nào nặng hơn. Ta bỏ đồng số 4 của nhóm A và đồng số 7,8 của nhóm B gia ngoài. Cho đồng số 3 sang nhóm B đồng số 6 sang nhóm A . Vậy nhóm A có đồng 1 ,2 ,6 nhóm B có đồng 3 ,5 và đồng số 9 cho thêm vào không bị lỗi. Nếu cân thăng bằng thì 3 đồng 4 ,7,8 có đồng lỗi, ta lấy đồng 7 cân với đồng 8 cũng suy luận như nhóm C là tìm đc đồng bị lỗi. Nếu cân đảo chiều thì đồng 3 hoặc đồng 6 bị lỗi, còn lần cân còn lại tìm gia được đồng nào bị lỗi. Nếu cân vẫn lệch như lần cân số 1 thì 3 đồng 1,2,5 có đồng bị lỗi ta cũng cân đồng số 1 với đồng số 2 như cách cân ở nhóm C có thể tìm gia đồng bị lỗi.
từ dữ niệu bài toán ta có :
Với 3 lần cân ta cân được tối đa 13 đồng tiền ,
Với 4 lần cân ta cân được tối đa là 39 đồng tiền ( 1 tuần trc mình nhầm to cái này) vì đơn giản là 39 đông chia thành 13 cân vơi13 , nếu thăng bằng thì 13 đồng còn lại bị lỗi và với 3 lần cân còn lại tìm đc đồng bị lỗi trong 13 đồng như là làm, còn cân lệch thì chia thành 3 nhóm 9,9,8 lấy ghép mỗi bên bên này 4 thì bên kia 5 có 3 khả năng xẩy ra ứng với 3 nhóm có số đồng là 9 hoặc 9, hoặc 8 bị lỗi , nếu 9 đồng bị lỗi thì lại chị làm 3,3,3 khác với bài toán 13 đông xu ta chia đc 3,3,2 do khi cân 2 nhóm số đồng xu cộng lại không thể lẻ đc nhầm tổng quát ở chỗ này
Với 5 lần cân thì ta được số đồng tối đa là 119 , lấy 40 đồng cân với 40 đông , cân thằng bằng thì 39 đông còn lại bị lỗi với 4 lần cân còn lại tìm đc 1 đồng bị lỗi như trên
Với 6 lần cân ta đc số đồng tối đa là 361 đồng lấy 121 cân với 121 đồng nếu cân thằng bằng thì 119 đồng còn lại bị lỗi còn cân lệch thì 242 đồng bị lỗi cho thêm 1 đồng không bị lỗi vào ta chia thành 3 nhóm mỗi nhóm có 81 đồng sắp xếp sao cho mỗi bên có 40 hoặc 41 đồng của của lần lượt 2 nhóm trên .
Với 7 lần ta có số đồng tối đa xác định đc là 364+364+361 tổng số là 1089
với 8 lần cân ta có số đồng tối đa xác định được 1 đồng bị lỗi là : 1093+1093+1089=3275
với 9 lần cân ta luôn được số đồng xu tối đa để tìm được 1 đồng xu bị lỗi là : 3280+3280+3275=9835
Tổng hợp lại bài toán với x là số lần cân x là số tự nhiên x≥ 3ta luôn có số đồng tiền tối đa xác định đc qua x lần cân là: . Thì tìm đc 1 đồng tiền bị lỗi. 2.(3^x-2+ 3^x-3+3^x-4...+3^x-x) +(3^x-2+ 3^x-3^x-4...+3^x-x)+ 4-x
Đáp án B
*Xếp 12 khách vào 3 toa tàu (có thể có toa không có khách): Có 3 12 cách.
* Trừ đi các trường hợp có KHÔNG QUÁ 2 toa có khách: − C 3 2 .2 12
(Chọn ra hai toa có C 3 2 cách. Sau đó xếp tùy ý 12 khách vào 2 toa đã chọn ra này, tức là có thể có một trong hai toa không có khách).
Nhưng như vậy ta đã trừ đi các trường hợp chỉ có 1 toa có khách đến 2 lần nên phải cộng lại số này: + C 3 1 .1 12
* Vậy cách xếp thỏa mãn yêu cầu bài toán là 3 12 − C 3 2 .2 12 + C 3 1 .1 12 = 519156 cách.
Do đó chọn đáp án B.
Bài toán tổng quát: Có bao nhiêu cahcs xếp q hành khách vào n toa tàu khác nhau sao cho toa tàu nào cũng có khách? (hay chính là bài toán chia quà: Có bao nhiêu cách chia q món quà khác nhau cho n bạn sao cho bạn nào cũng có quà?)
Ở bài toán trên, ta có:
3 12 − C 3 2 .2 12 + C 3 1 .1 12 = C 3 0 3 − 0 12 − C 3 1 3 − 1 12 + C 3 2 3 − 2 12 − C 3 3 3 − 3 12
Lập luận tương tự như bài toán trên ta có số cách xếp (cách chia) là:
C n 0 n − 0 q − C n 1 n − 1 q + C n 2 n − 2 q − C n 3 n − 3 q + ... = ∑ k = 0 n − 1 k C n k n − k q
Bài toán này khác với bài toán chia kẹo Euler: Có bao nhiêu cách chia q chiếc kẹo giống nhau cho n em bé sao cho em nào cũng có kẹo?