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

Thanh Lam không phải học LHP à, tiếc quá.
Có lẽ bạn Thanh Lam đánh máy nhầm 1 chút. Đáp án của bài toán là U(n) = (3^n - 1) / 2 . Có nghĩa là với n lần cân chỉ có thể giải quyết được tối đa [(3^n - 1) / 2] viên bi.
Bởi vậy mệnh đề qui nạp mà bạn cần chứng minh phải là:
"Với n lần cân không giải được bài toán (3^n - 1)/2 + 1 (tức là {(3^n + 1) / 2} ) viên bi"
Thanh Lam chịu khó viết bài giải cụ thể hơn 1 chút được không, cho kimikamo và các bạn khác hiểu với . Nhất là cái đoạn gần cuối, "sau 2 lần cân có 3^k + 1 viên bi không đổi nhóm..."

Chắc hơi khó hiểu phải không KIMIKAMO, tôi viết không sai đâu.
Tôi dùng mệnh đề (bổ đề ) để chứng minh bài toán, bổ đề phát biểu là ::với 3^n+1 viên bi không thể giải được bằng n+1 lần cân, với điều kiện là ở lần cân đầu tiên, tất cả các viên bi phải được đặt lên cân. chỗ bôi đỏ là sự khác biệt mà bạn không hiểu đấy.Như bạn thấy đấy, khi chứng minh trường họp 14 tôi phải dùng bổ đề này với n=2(3^n+1=10).
còn bạn thắc mắc chỗ các viên bi không đổi nhóm à. Ta đã chứng minh trường hợp có ít hơn 2*3^k+1 được đặt lên bàn cân thì mệnh đề đúng, bây giờ giả sử có ít nhất 2*3^k+1 viên bi ( trong số 3^(k+1)+1) được đặt lên cân trong lần cân thứ hai.Thì có cách chọn bàn cân( bên trái nặng hơn, hay bên phải nặng hơn) sao cho tổng số viên bi không đổi nhóm >=3^k+1. Thật vậy giả sử khi bàn cân nghiêng về bên trái có ít hơn 3^k+1 không đổi nhóm, như vậy có ít nhất 3^k+1 viên bi thay đổi nhóm, khi ta chọn bàn cân nghiêng về bên phải thì 3^k+1 viên bi này lại trở thành những viên bi không đổi nhóm. Như vậy với cách chọn bàn cân nghiêng về bên trái hay bên phải ta sẽ tìm ra được ít nhất 3^k+1 viên bi không đổi nhóm, mục đích của việc làm này là để chứng minh rằng với 3^k+1 viên bi này, sau lần cân thứ nhất, và lần cân thứ hai, thông tin có ích chỉ được cung cấp ở lần cân thứ nhất, còn lần cân thứ hai xem như không có ích (nguyên nhân dẫn đến điều này là vì ở lần cân thứ nhất, tất cả các viên bi phải được đặt lên bàn cân).

Hi..hi.., đúng rồi, xin lỗi Thanh Lam nhé, kimikamo chưa hiểu hết ý của bạn. Như vậy là bây giờ Thanh Lam đã có được bổ đề sau:
"Không thể giải quyết bài toán 3^n + 1 viên bi với n+1 lần cân, nếu như đặt tất cả 3^n + 1 viên bi lên bàn cân ở lần cân thứ nhất"
Trường hợp 14 viên bi cũng đúng như bạn đã nói. Căn cứ theo bổ đề trên, nếu ở lần cân thứ 1, ta đặt 10 viên bi lên bàn cân thì sẽ không giải được bài toán với 3 lần cân(3^2 + 1 = 10). Còn nếu đặt ít hơn 9 viên thì số bi còn lại sẽ lớn hơn hay bằng 5 viên bi. Trong trường hợp cân thăng bằng, viên bi đặc biệt nằm trong 5 viên bi còn lại. Mà với 2 lần cân thì không giải được bài toán 5 viên bi. Lý do cũng tương tự như trên, nếu đặt 4 viên bi lên bàn cân ở lần cân thứ 1, thì sẽ không giải được(theo bổ đề, 3^1 + 1 = 4). Còn nếu đặt 3 viên bi thì còn lại 2 viên. Trong trường hợp cân thăng bằng, viên bi đặc biệt sẽ nằm trong 2 viên bi còn lại. Dễ thấy với 1 lần cân không thể giải quyết bài toán 2 viên bi.
Hi..hi.., Thanh Lam phải giải thích rành mạch như thế thì tui mới hiểu được.
Đến đây thì đã gần đến đích rồi, Thanh Lam dẫn ra trường hợp tổng quát luôn giùm cái. Bạn làm ơn nói cụ thể luôn cho kimikamo và mọi người hiểu, từ bổ đề đó làm sao suy ra được rằng với n lần cân không thể giải được bài toán (3^n + 1)/2 viên bi.
Tiễn Phật thì tiễn đến Tây Thiên luôn giùm, hê..hê..

(3^n+1)/2 không thể cân bằng n lần cân?Nếu ở lần cân thứ nhất có >=3^(n-1)+1 viên bi đặt lên bàn cân thì theo bổ đề với n lần cân không thể xác định viên bi giả trong n viên bi này.Còn nếu ngược lại thì số viên bi không được đặt lên cân ở lân cần thứ nhất ít nhất là (3^n+1)/2-3^(n-1)=(3^(n-1)+1)/2
Tới đây ta thấy ý tưởng qui nạp đã rõ ràng,(3^(n-1)+1)/2 không thể cân được bằng n-1 lần cân.
Thôi thế còn thắc mắc nữa không?Chắc là còn nhỉ, có chỗ vẫn còn khó hiểu phải không, nhưng KIMIKAM post cái lời giải của anh chuyên lý lên cho mọi người xem đi.

OK, đồng ý với cách giải của Thanh Lam. Hi..hi.., nếu ngay từ đầu bạn ghi rõ ràng ra như thế thì kimikamo đâu có cần mỏi tay thắc mắc này nọ
Còn về bài giải của anh chàng chuyên Lý kia, về cơ bản cũng giống của Thanh Lam thôi.
Trước tiên anh ta chứng minh rằng với n lần cân sẽ giải quyết được bài toán (3^n - 1)/2 viên bi. Cách làm tương tự như của Thanh Lam.
Còn về việc chứng minh đó là nghiệm tối ưu, anh ta lý luận như sau:
Chúng ta quan tâm đến việc tìm ra viên bi đặc biệt, và chỉ ra nó nặng hay nhẹ hơn bình thường. Như vậy với K viên bi thì sẽ có có 2*K khả năng: bi 1 nặng hơn bình thường, bi 1 nhẹ hơn bình thường,..., bi K nặng hơn bình thường, bi K nhẹ hơn bình thường.
Mục đích của việc đem cân là loại bỏ các khả năng không thể xảy ra, dựa vào kết quả của phép cân. Dễ thấy sau mỗi lần cân, số khả năng chỉ có thể giảm đi TỐI ĐA 3 lần. Chứng minh điều này như sau:
Gọi tập hợp các khả năng trước khi cân là Q. Khi đem cân thì sẽ có 3 trường hợp: Cân thăng bằng, bên trái nhẹ hơn, hoặc bên trái nặng hơn. Gọi số tập hợp các khả năng còn lại sau khi cân, trong 3 trường hợp trên, lần lượt là q1, q2, q3. Dễ thấy q1 U q2 U q3 = Q (hợp của 3 tập q1, q2, q3 bằng tập Q). Mặt khác, 1 khả năng không thể xuất hiện trong nhiều hơn 1 trường hợp, cho nên 3 tập q1 , q2 , q3 không thể có phần tử chung.
Từ đó suy ra MAX{|q1|, |q2|, |q3|} >= Q/3 , nghĩa là số phần tử của tập con lớn nhất sẽ lớn hơn hoặc bằng 1/3 số phần tử của tập ban đầu.

Bài toán được coi là giải được, khi sau lần cân cuối cùng chỉ còn sót lại 1 khả năng. Cứ tưởng tượng sau mỗi lần cân số khả năng cứ giảm dần, giảm dần. Tới lúc chỉ còn 1 khả năng thì là bài toán đã được giải xong. Mà mỗi lần cân chỉ có thể giảm số khả năng đi tối đa 3 lân, cho nên dễ thấy điều kiện cần để n lần cân giải quyết được U(n) viên bi sẽ là 2U(n) <= 3^n , nghĩa là số khả năng ban đầu phải bé hơn hoặc bằng số khả năng tối đa có thể giải quyết được . 3^n là số lẻ, 2*U(n) là số chẵn, cho nên điều kiện trên có thể viết lại thành 2U(n) <= 3^n - 1 . Suy ra U(n) <= (3^n - 1)/2 .
Như vậy nghiệm U(n) = (3^n - 1)/2 là nghiệm tối ưu.

Hi..hi.., hôm nay vô post bài , tự nhiên thấy mình được ai đó vote cho 5 sao. Không biết là bạn nào, nhưng mà cũng xin cảm ơn nhiều nhé. Bạn gì đó thật là tốt bụng, chúc bạn luôn vui vẻ, và sẽ được...các bạn khác vote cho nhiều nhiều sao.

Lời giải trên cũng khá hay đấy, không ngờ bài toán này lại có thể giải quyết bằng sự phân hoạch. Đến đây chắc là đã kết thúc bài toán rồi KIMIKAMO nhỉ, lâu quá rồi tôi mới lại được giải toán hăng như thế này, từ khi lên DH không làm toán nữa nhưng vẫn rất yêu toán.Chúc KIMIKAMO tán được cô gái AMs đó, chắc bạn là anh chàng chuyên lý kia phải không.

Ha..ha.., cảm ơn Thanh Lam nhiều nhé. Không ngờ Thanh Lam ngoài việc giỏi Toán ra, còn giỏi cả...đoán mò nữa
Kimikamo cũng rất có cảm tình với cô bé trường Ams đó, nhưng mà không phải anh chàng cù lần kia đâu nhé. Cũng may lần ấy mình đứng ngoài tọa sơn quan hổ đấu, chứ không thì đâu có thể nói chuyện với em 1 cách tự nhiên như bây giờ.
Mỗi lần nói chuyện với cô ta mình cảm thấy rất vui, nhưng mà vẫn thấy hơi...sợ sợ thế nào. Em này nói chuyện cực kỳ dễ thương, cực kỳ lễ phép, đôi mắt trong sáng ngây thơ, nhưng mà ánh mắt thì sắc ơi là sắc, cứ như nhìn thấy hết tâm can người khác. Bởi vậy khi nói chuyện kimikamo không dám nhìn thẳng vào mắt cô ta, chỉ sợ cô nàng nhìn thấy hết mọi suy nghĩ của mình. Chỉ có thỉnh thoảng nhìn trộm 1 cái thôi, hê..hê..

Con trai giỏi toán với giỏi tán gái...chậc...

Nữa rồi, chỗ mấy anh đang nói chuyện, em Mon tự nhiên xen vô làm gì. Con gái LHP đâu có hay cạnh khoé như em này đâu nhỉ