Giải trí với toán học ^__^

Chia 13 viên bi tha?nh 3 nhóm:
Nhóm A: A1, A2, A3, A4, A 5
Nhóm B: B1, B2, B3, B4
Nhóm C: C1, C2, C3,C4
Va? 2 viên bi thật : D1 , D2
Cân lâ?n thứ I:
A1, A2, A3, A4 , A5 va? B1,B2,B3,B4,D1
Lâ?n lượt xét các trươ?ng hợp sau:
1 ) hai bên bă?ng nhau:
Suy ra trong các viên bi C1, C2, C3, C4 pha?i có viên bi gia?.Cân lâ?n II như sau : C1,C2,C3 va? A1, A2, A3
Lại xét tiếp các trươ?ng hợp sau;
1.1) hai bên bă?ng nhau:
Suy ra C4 la? viên gia?, lại đem C4 cân với A1 đê? xác định C4 nặng hay nhẹ hơn.
1.2) bên trái nặng hơn bên pha?i:
Suy ra trong các viên bi C1 , C2, C3 pha?i có viên gia? va? nặng hơn viên bi thật, lân cân thứ III ta sef chi? cân C1 va? C2 , nếu bă?ng nhau thi? C3 la? gia? va? nặng hơn bi thật co?n nếu cân không cân bă?ng thi? viên bi gia? la? viên bi nặng hơn trong lâ?n cân trên.
1.3) bên trái nhẹ hơn bên pha?i:
La?m tương tự như trên với lưu ý la? viên bi gia? nhẹ hơn viên bi thật.
2 ) bên trái nặng hơn bên pha?i:
Trươ?ng hợp na?y suy ra viên bi gia? la? một trong các viên nhóm A hay nhóm B.Cân lâ?n II như sau:
A 1, A 2, A3, B1,B2,B3 VA? C1,C2,C3,C4,D1,D2
Lưu ý la? C1,C2,C3,C4,D1,D2 tất ca? đê?u thật .
Ta lại tiếp tục xét tiếp các trươ?ng hợp sau:
2.1) hai bên bă?ng nhau:
Suy ra viên bi giả là một trong các viên bi A 4 , A 5, B4
Tiếp theo đặt A 4 và A 5 lên cân. Nếu như cân cân bằng thì B4 là viên bi giả và nhẹ hơn bi thật (do lần cân I).Nếu cân không cân bằng thì bi nào nặng hơn là bi giả.
2.2) bên trái nặng hơn bên phải:
Có nghĩa là bi giả nặng hơn bi thật và do đó bi giả là một trong các bi A 1, A 2,A 3. Đặt A 1 và A 2 lên cân, nếu cân cân bằng thì A 3 là bi giả và nặng hơn bi thật.
Còn nếu cân không cân bằng thì bi giả là viên bi nặng hơn bi kia .
2.3) bên trái nhẹ hơn bên phải:
Có nghĩa là bi giả nhẹ hơn bi thật và do đó bi giả là một trong các bi B1,B 2,B3. Đặt B1 và B2 lên cân, nếu cân cân bằng thì B3 là bi giả và nhẹ hơn bi thật.
Còn nếu cân không cân bằng thì bi giả là viên bi nhẹ hơn viên bi kia .
3 ) bên trái nhẹ hơn bên pha?i:
Trường hợn này cân y chang trường hợp 2.

Tuyệt vời! Thanh Lam không những hát hay mà còn giỏi toán nữa. Có thế chứ. Con trai LHP làm sao chịu thua 1 cô nhóc trường Ams được, cho dù cô ta có học chuyên Toán chăng nữa
Thật tình rất khâm phục bạn Thanh Lam. Bài 13 viên bi này tồn tại ở đây mấy tháng nay rồi. Không có bạn xuất hiện thì không biết nó còn tồn đọng đến bao giờ
Vote cho bạn Thanh Lam 5 sao, xin cảm ơn rất nhiều.
Như đã hứa với mọi người kimikamo xin được kể 1 câu chuyện có liên quan đến mấy bài toán đố vừa rồi.
Kimikamo lần đầu tiên gặp bài toán 12 viên bi khi nó xuất hiện trên 1 mail list của 1 nhóm sinh viên VN. Có 1 chị thuộc dạng "nghịch" nhất trong mail list, 1 hôm bỗng gửi bài toán 12 viên bi lên, và thách các anh giải thử.
Có lẽ lúc đó gần đến mùa thi hay sao, mà mấy ngày trôi qua vẫn chẳng thấy ai đá động gì đến mail của chị kia cả. Chắc là rỗi hơi không có việc gì làm, chị ta liền gửi tiếp 1 mail khác có nội dung rất ư là...khiêu khích.
Đúng là bản tính hay sĩ diện của đàn ông thì không bao giờ thay đổi. Ngay trong ngày hôm đó đã có 4 mail gửi bài giải lên, tất cả đều chính xác. Các anh bắt đầu quay sang...tự khen lẫn nhau, rất chi là hể hả.
Thế rồi ngày hôm sau, bỗng nhiên có 1 bé vừa mới chân ướt chân ráo sang, rụt rè gửi lên mạng 1 cái mail, đại khái có nội dung như sau:
"Em chào các anh các chị, em tên là...Rất hân hạnh...Em vừa mới gia nhập mail list, có gì xin các anh chị giúp đỡ, vâng vâng và vâng vâng...
Thấy các anh ở đây vui quá, em xin mạn phép mở rộng bài toán trên cho trường hợp 13 viên bi. Nhưng em xin phép được mượn thêm từ bên ngoài 1 viên bi bình thường. Bài giải như sau:... "
Cũng cần nói thêm là em này xuất thân từ chuyên Toán trường Ams. Nhỏ nhắn xinh xắn, nói chuyện cực kỳ lễ phép và dễ thương. Mặc dù mới sang nhưng đã có rất nhiều anh đang "tăm tia" em này
Các bậc "tiền bối" nãy giờ đang phét lác, bỗng nhiên cảm thấy...sượng làm sao
Cũng may sau đó, 1 anh cao ráo đẹp trai (có điều mắt kiếng dày cộm ), xuất thân từ Chuyên Lý LHP, ráng vớt vát danh dự cho các đàn anh bằng cách...tiếp tục mở rộng bài toán trên. (Cụ thể bài giải của em trường Ams và bài toán mở rộng của anh Chuyên Lý LHP như thế nào mình sẽ post tiếp theo sau đây.)
Từ hôm đó trở đi "chiến sự" xung quanh cô bé dễ thương kia gia tăng mức độ 1 cách đáng kể. Anh chàng Chuyên Lý LHP, mặc dù đã có nội gián giúp đỡ tận tình, vẫn chịu thất bại thảm hại. Ai cũng thấy tội nghiệp, nhưng mà đều thòng thêm 1 câu, "Thua là...đáng lắm"

Bên này làm toán mà có kể chuyện nữa, xôm tụ ghê !

Về bài giải của em trường Ams thì về cơ bản cũng gần giống như của bạn Thanh Lam. Em chỉ mượn thêm 1 viên bi bình thường từ bên ngoài vào. Cho nên có 1 điểm khác biệt giữa 2 bài giải như sau:
1) Trong trường hợp cân lần đầu:
A1 A2 A3 A4 A5 <--> B1 B2 B3 B4 D1
Khi bên trái nặng hơn bên phải, ta rút ra kết luận sau:
_Các viên bi C1 C2 C3 C4 là bình thường
_Trong 5 viên bi A1-A5 có 1 viên bi nặng hơn bình thường, hoặc trong 4 viên bi B1-B4 có 1 viên nhẹ hơn bình thường.
2) Ở lần cân thứ 2 ta sẽ cân như sau:
A1 A2 B1 B2 <--> A3 B3 C1 C2
2.1) Trong trường hợp bằng nhau, ta đi đến kết luận:
_Các bi A1-A3, B1-B3 là bình thường
_Như vậy chỉ còn các khả năng sau: trong 2 viên bi A4, A5 có 1 viên nặng hơn bình thường, hoặc bi B4 nhẹ hơn bình thường.
Ở lần cân thứ 3 ta sẽ cân A4 <--> A5. Nếu bằng nhau thì B4 nhẹ hơn bình thường, còn không bằng thì bên nào nặng hơn sẽ là bi đặc biệt
2.2) Trong trường hợp bên trái nặng hơn, A1 A2 B1 B2 > A3 B3 C1 C2, ta đi đến kết luận:
_Trong 2 viên bi A1, A2 có 1 viên nặng hơn bình thường, hoăc bi B3 nhẹ hơn bình thường.
Ở lần cân thứ 3 ta đem cân A1 <-> A2, nếu bằng nhau thì B3 là bi nhẹ hơn bình thường, còn không bằng thì bên nào nặng hơn sẽ là bi đặc biệt.
2.3)Trường hợp bên trái nhẹ hơn, A1 A2 B1 B2 < A3 B3 C1 C2, ta đi đến kết luận:
_Trong 2 bi B1, B2 có 1 bi nhẹ hơn bình thường, hoặc bi A3 nặng hơn bình thường.
Ở lần cân thứ 3 ta đem cân B1 <-> B2. Nếu bằng nhau thì bi A3 là bi nặng hơn bình thương, còn không bằng thì bên nào nhẹ hơn là bi đặc biệt.
Các trường hợp khác thì tương tự như bài giải của bạn Thanh Lam

Còn về bài toán mở rộng của anh chàng Chuyên Lý tội nghiệp kia, kimikamo cũng post lên để mọi người thử sức

Chứng minh rằng bài toán không giải được trong trường hợp 14 viên bi(với 3 lần cân), và tìm ra công thức tổng quát giữa số viên bi và số lần cân tối thiểu để tìm ra viên bi đặc biệt.

Wow, đến đây thì không còn thuộc phạm vi đố vui nữa rồi, hê..hê... Có điều cũng không khó lắm đâu. Bạn nào đã "quán triệt" được tư tưởng trong lời giải bài toán 12 viên bi và 13 viên bi thì sẽ cảm thấy khá là đơn giản.
Kimikamo sẽ vote 5 sao cho bạn nào có lời giải chính xác.

Tôi đã chứng minh là U(2)=4 viên bi với 2 lần cân,U(4)= 40 viên bi với 4 lần cân,... có thể tìm ra được viên bi giả và xác định nó nặng hay nhẹ hơn. Công thức tổng quát có thể là: U(n+1)=3*U(n) + 1 (40=13*3+1,13=4*3+1), với Un là số bi có thể cân bằng n lần để tìm ra viên bi giả(n>=2). Chứng minh điều này cũng đơn giản, chắc Kimikamo cũng có thể hiểu được các dòng lí giải sau đây:
Ý tưởng chính là pp qui nạp. Đối với U(n+1) viên bi thì ta nhóm thành U(n) nhóm, mỗi nhóm 3 bi và còn dư một viên không thuốc nhóm nào cả.Ta đã biết cách cân cho U(n) viên bi bằng n lần cân để tìm được viên bi giả, bây giờ ta áp dụng n lần cân này cho U(n) nhóm trên(mỗi nhóm xem như một viên bi vậy), ta có 2 trường hợp xảy ra:
+n lân cân trên đầu đạt kết quả cân bằng, suy ra viên bi còn sót lại là viên bi giả, với một lần cân còn lại hoàn toàn có thể xác định nó nặng hay nhẹ hơn bi thật(cái này bạn đọc phải suy nghĩ thêm một chút).
+tìm ra được một nhóm chứa bi giả và biết nó nặng hay nhẹ hơn bình thường.Trường hợp này nhanh chóng giải quyết bằng lần cân cuối cùng, đặt 2 bất kỳ trong 3 viên này lên cân.
Đây mới chỉ là tìm Được U(n) nhưng đã tối ưu chưa thì tôi chưa chứng minh được. Tôi đoán là U(n)+1 sẽ không cân được bằng n lần cân. Cái này hơi hóc búa, để tui suy nghĩ thêm đã.Tui sắp về VN rồi không biết có tì giờ nghĩ tiếp không nữa., chúc mọi người vui vẻ.

Tôi đã chứng minh là U(2)=4 viên bi với 2 lần cân,U(4)= 40 viên bi với 4 lần cân,... có thể tìm ra được viên bi giả và xác định nó nặng hay nhẹ hơn. Công thức tổng quát có thể là: U(n+1)=3*U(n) + 1 (40=13*3+1,13=4*3+1), với Un là số bi có thể cân bằng n lần để tìm ra viên bi giả(n>=2). Chứng minh điều này cũng đơn giản, chắc Kimikamo cũng có thể hiểu được các dòng lí giải sau đây:
Ý tưởng chính là pp qui nạp. Đối với U(n+1) viên bi thì ta nhóm thành U(n) nhóm, mỗi nhóm 3 bi và còn dư một viên không thuốc nhóm nào cả.Ta đã biết cách cân cho U(n) viên bi bằng n lần cân để tìm được viên bi giả, bây giờ ta áp dụng n lần cân này cho U(n) nhóm trên(mỗi nhóm xem như một viên bi vậy), ta có 2 trường hợp xảy ra:
+n lân cân trên đầu đạt kết quả cân bằng, suy ra viên bi còn sót lại là viên bi giả, với một lần cân còn lại hoàn toàn có thể xác định nó nặng hay nhẹ hơn bi thật(cái này bạn đọc phải suy nghĩ thêm một chút).
+tìm ra được một nhóm chứa bi giả và biết nó nặng hay nhẹ hơn bình thường.Trường hợp này nhanh chóng giải quyết bằng lần cân cuối cùng, đặt 2 bất kỳ trong 3 viên này lên cân.
Đây mới chỉ là tìm Được U(n) nhưng đã tối ưu chưa thì tôi chưa chứng minh được. Tôi đoán là U(n)+1 sẽ không cân được bằng n lần cân. Cái này hơi hóc búa, để tui suy nghĩ thêm đã.Tui sắp về VN rồi không biết có thì giờ nghĩ tiếp không nữa., chúc mọi người vui vẻ.

Má ơi, ghê quá, nghe sao lùng bùng lỗ tai giống trong tiết Toán mấy năm trước nên tui ngủ luôn...... Bực cái là hồi đó cha thầy nói chuyện lớn quá làm ngủ không ngon giấc!

Kha..kha.., Tuyệt lắm! Quả là không hổ danh con trai LHP nhỉ. Từ lúc có bạn Thanh Lam xuất hiện topic này vui hẳn lên. Cụng ly cái
Cách giải của Thanh Lam rất hay. Kết quả của bạn đưa ra là chính xác.
Tui xin mạn phép chú giải cách làm của Thanh Lam rõ hơn 1 chút, để các bạn khác tiện theo dõi:
Gọi n là số lần cân, U(n) là số viên bi có thể giải quyết được với n lần cân. Theo cách làm của Thanh Lam thì ta đã đi đến kết luận:
U(n+1) = 3*U(n) + 1
Ngoài ra ta nhận thấy U(1) = 1
Từ đó có thể suy ra công thức tổng quát U(n) = (3^n - 1) / 2 . Thao tác biến đổi để cho ra công thức trên không khó, và nó cũng không phải là điểm chính của bài toán này nên cho phép mình lược bỏ.
Vấn đề là chứng minh công thức trên là tối ưu, có nghĩa là:
U(n) <= (3^n - 1) / 2 , với mọi n .
Cái này bạn Thanh Lam và các bạn chắc chắn sẽ nghĩ ra được thôi. Xin mời các bạn.
Trước hết các bạn có thể bắt đầu từ trường hợp cụ thể, chứng minh với 3 lần cân không thể giải quyết được 14 viên bi. Sau đó sẽ mở rộng ra cho trường hợp tổng quát.
Tiếc là tui không thể vote cho bạn Thanh Lam 2 lần được. Hình như mỗi người chỉ được vote 1 lần thôi thì phải. Có điều bạn này xứng đáng được vote lắm, có ai rảnh làm hộ mình cái, kimikamo sẽ vote lại cho bạn đó 5 sao

Tui giải nốt để kết thúc topic luôn nhé
Trước hết ta chứng minh qui nạp mệnh đề sau:
"bài toán 3^n+1(n>=1) viên bi không giải được bằng n+1 lần cân với điền kiện lần cân đầu tiên tất cả 3^n+1 viên bi này phải được đặt lên cân."
Chứng minh:
n=1, cái này mọi người chứng minh hộ nhé, không khó đâu(KIMIKAMO)
giả sử n=k đúng, chứng minh n=k+1 đúng.Thật vậy, ta xét lần cân đầu tiên, nếu chỉ có ít hơn 2*3^k+1 viên bi trong số các viên bi này được đặt lên bàn cân thì số viên bi không đuợc đặt lên bàn cân nhiều hơn 3^k+1 giả sử sau lần cân thứ nhất cân cân bằng, suy ra viên bi giả nằm trong số các viên bi còn lại. Nhưng theo giải thuyết qui nạp, với k +1 lần cân tiếp theo ta không thể xác định được viên bi giả trrong ít nhất 3^k+1 viên bi còn lại, vì vậy mệnh đề sẽ đúng với n=k+1 trong trường hợp này.
Trưồng hợp có ít nhất 2*3^k+1 được đặt lên cân, hơi khó hiểu một chút mọi người phải tập trung nhé.
Giả sử ngược lại tồn tại một lời giải cho n=k+1, khi đó sau lần cân đầu tiên ta biết được thông tin là :"Hoặc là trong m viên bi có một viên bi giả và nhẹ hơn viên bi thật(nhóm m viên bi này gọi là nhóm I, tức là nhóm nhẹ hơn), hoặc là trong p viên bi có một viên bi giả và nặng hơn viên bi thật(nhóm p viên bi này gọi là nhóm II, tức là nhóm nặng hơn).(m,p>=0,m+p>=2*3^k+1)"(Thông tin kiểu này gọi là thông tin có ích).
Bây giờ xét lần cân thứ hai:ta có quyền chọn cán cân,(có hai cách chọn) sao cho thoã mãn điều kiện : tổng số viên bi không thay đổi nhóm( ban đầu ở nhóm nào thì khi cân lần hai nó cũng vẫn ở nhóm ấy) ít nhất là 3^k+1 viên bi.
Giải thích một chút tại sao lại tồn tại ít nhất 3^k+1 viên bi, cái này nếu ai hiểu một chút nguyên lý Dirichlet sẽ thấy ngay.
Giải thích thêm là tại sao ta có quyền chọn cán cân cho lần cân thứ hai. Vì là ta giả sử có một cách giải cho n=k+1 nên cách giải này phải giải được trong mọi trường hợp xảy ra của cán cân.
Sau hai giải thích trên ta đã sáng tỏ là sau hai lần cân đầu tiên đồi với 3^k+1 viên bi không thay đổi nhóm này, thông tin có ích chỉ là ở lần cân thứ nhất, còn lần cân thứ hai không có ích. theo giả thiết qui nạp với k lần cân còn lại không thể giải quyết được bài toán, suy ra mâu thuẫn.
Vậy mệnh đề được chứng minh. Bây giờ giải quyết nốt bài toán bằng mệnh đề.
2 4 10 28 ....
5 14 40 ....
Để dễ theo dõi chứng minh với 14 viên bi thôi nhé, tổng quát thì cũng tương tự thôi.
Trước tiên dễ thấy bài toán 2 viên bi không giả được bằng 1 lần cân.
Bây giờ ta chứng minh bài toán 5 viên bi không giải được bằng
2 lần cân. Thật vậy,giả sử trong lần cân đầu tiên, có ít nhất 2 viên bi không đưọc đặt lên bàn cân, và trong trong trường hợp cân cân bằng, ta phải xác định viên bi giả trong 2 viên bi bằng 1 lần cân,điều này không thể được. Vậy phải có ít nhất 4 viên bi được đặt lên bàn cân trong lần cân đầu, nếu giả sử cân không cân bằng thì theo mệnh đề(n=1) tà không thể cân bằng hai lần cân được. Suy ra ta chứng minh xong. Trờng hợp 14 cũng tưng tự(4 +10=14).
Chúc mọi người vui vẻ.
tui không phải HS LHP đâu KIMIKAMA ạ, gần LHP thôi.
SU 541 moscow->hanoi