Có $4m$ đồng xu, nhưng chỉ có $2m$ đồng là thật, khối lượng đồng xu thật nặng hơn đồng xu giả. Chứng minh rằng chỉ với một cái cân đĩa và không kèm theo các dụng cụ khác, sau không quá $3m$ phép cân đĩa ta có thể xác định được tất cả các đồng xu thật và giả.
sau không quá $3m$ phép cân đĩa ta có thể xác định được tất cả các đồng xu thật và giả.
#1
Đã gửi 24-09-2015 - 17:34
“Hầu hết mọi người đều chấp nhận thua cuộc ngay khi họ sắp thành công. Họ dừng lại
ngay trước vạch đích, cách chiến thắng chỉ một bàn chân” -H. Ross Perot
“Tránh xa những kẻ coi nhẹ tham vọng của bạn. Những kẻ nhỏ nhen luôn như thế, còn
những người thực sự vĩ đại sẽ khiến bạn cảm thấy rằng bạn cũng có thể trở nên vĩ đại”
-Mark Twain
Huỳnh Tiến Phát ETP
$WELCOME$ $TO$ $MY$ $FACEBOOK$: https://www.facebook.com/phat.huynhtien.39
#2
Đã gửi 03-11-2015 - 08:06
Có $4m$ đồng xu, nhưng chỉ có $2m$ đồng là thật, khối lượng đồng xu thật nặng hơn đồng xu giả. Chứng minh rằng chỉ với một cái cân đĩa và không kèm theo các dụng cụ khác, sau không quá $3m$ phép cân đĩa ta có thể xác định được tất cả các đồng xu thật và giả.
Gọi A là tập hợp các đồng xu thật
B là tập hợp các đồng xu giả
Chia các đồng xu ra làm m nhóm, mỗi nhóm 4 đồng xu. Thực hiện phép cân cho mỗi nhóm như sau
- Đặt trên mỗi đĩa cân 2 đồng xu có hai trường hợp
1) Nếu cân lệch, lấy 2 đồng xu trên đĩa cân nhẹ đặt trên mỗi đĩa căn 1 đồng xu, có hai trường hợp xảy ra
a)Cân lệch-->trong nhóm có 1 đồng xu giả ở đĩa cân nhẹ
b)Cân cân bằng--> trong nhóm có 2 đồng xu giả (là 2 đồng xu cân cuối cùng)
2)Nếu cân cân bằng,lấy 2 đồng xu trên cùng môt đĩa cân đặt trên mỗi đĩa căn 1 đồng xu, có hai trường hợp xảy ra
a)Cân lệch==>xu giả,thực hiện tương tự với 2 đồng xu còn lại-->đồng xu giả còn lại
b)Cân cân bằng. Chứng tỏ 4 đồng xu cùng tính chất
Nói chung với tối đa 3 lần cân ta có thể xác định tất cả các đồng xu thật và giả của một nhóm, với hai lần cân ta có thể có thể xác định một nhóm cùng tính chất
Giả sử có k nhóm đã xác định được số tiền thật và giả, số lần cân không quá 3k
Còn lại m-k nhóm có cùng tính chất, đã cân 2(m-k) lần
1)k khác 0. Tức là có đồng xu thật mẫu
Lấy 1 đồng xu của mỗi nhóm cân với đồng xu thật mẫu.Sau m-k lần sẽ phân biệt được tất cả các đồng xu thật và giả. Tổng không quá 3m lần cân
2)k=0. Tức là m nhóm đều có các phần tử cùng tính chất.Lúc này m chẳn và số nhóm chứa tiền thật và số nhóm chứa tiền giả cùng bằng m/2,Số lần đã cân là 2m
Lấy một nhóm bất kỳ làm mẫu cân với các nhóm còn lại.Dễ thấy sau không quá m lần sẽ xác định được các đồng xu thật và các đồng xu giả.Và tổng số lần cân không quá 3m
Vậy sau tất cả các trường hợp đã liệt kê đã CM được sau không quá 3m phép cân đĩa sẽ xác định được các đồng xu thật và giả
Bài viết đã được chỉnh sửa nội dung bởi QDV: 03-11-2015 - 10:09
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh