Anh chị em mình làm tí cho vui.

Anh chị em mình làm tí cho vui.

Dạo này, em làm ăn sa sút nên ko tham gia thường xuyên. Hôm nay em post bài này, cũng mong anh chị em mình tham gia nhiệt tình.

Đề bài như sau :

Giả sử có n ngôi nhà va 1 nhà máy điện. Hỏi có bao nhiêu cách mắc điện tới các ngôi nhà sao cho nhà nào cũng có điện.

PS: em cũng ko thik thể loại chính tắc này lám. Cơ dưng mà, mãi ko tìm được bài nào hay hơn.

có (n! - 1) + 2 cách gồm :
Cách 1 :có 1 đôi dây chung chạy qua truớc các nhà, từ mỗi nhà nguời ta lấy điện từ cặp dây chung đó
Cách 2 : từ nhà máy điện chạy từng cặp dây đến mỗi nhà.
Cách 3 gồm 1 số dùng cách 1 và 1 số dùng cách 2. Riêng cách 3 này có (n!-1) truờng hợp.

đề bài hơi không rõ ràng lắm. ko nói rõ có thể có những cách mắc thừa dây hay không (ví dụ 3 nhà A, B, C đều nối với nhau) hay chỉ cho phép những cách nối thực tế và ko cho phép thừa dây (ví dụ A chỉ nối với B, B chỉ nối với C, A ko cần nối với C). nếu là cách nối thứ nhất thì kết quả có lẽ là lớn hơn nhiều kết quả của bạn binh000
cũng là cách nối thứ nhất thì có thể là tương đương với bài này: Tính tổng số đồ thị liên thông của n + 1 đỉnh
nghe quen quen, hình như mình làm rồi chả nhớ nữa

Nếu các nhà là khác nhau thì có lẽ nhiều hơn!

Đầu bài cho như vậy có nghĩa là các nhà khác nhau. Chả lẽ có 2 nhà ông N giống hệt nhau đến mức không phân biệt được. Coi như các nhà khác nhau, theo tớ số cách mắc dây sẽ lớn hơn rất nhiều hơn số của bạn bing00 đưa ra, nhất là với n lớn.
Tớ chưa làm ra đáp số cuối cùng, nhưng phương hướng là như thế này:
1. Các nhà đấu điện với nhau theo một chuỗi từ 1 cho tới n+1, nhà máy điện cũng kể như một nhà số n+1. Khi đó số cách mắc sẽ là số giao hoán của n+1 phần tử chia cho 2 (vì luôn có hai trường hợp giống nhau) và bằng 1/2(n+1)!. Chỉ cần n cỡ 9, 10 thì đáp số đã lớn hơn ĐS của bạn binh rất nhiều rồi.
2. Các nhà đấu với nhau theo một chuỗi n nhà liên tiếp, trong đó có một nhà (tính cả nhà máy) làm mạch nhánh đơn. Khi đó tổng số cách lắp sẽ là (1/2)n!.(n-2). (Nhân với (n-2) bởi vì tồn tại 2 trường hợp mạch nhánh gắn ở đầu => trùng với trường hợp đầu).
Tương tự với 2 nhà làm mạch nhánh 3 nhà làm mạch nhánh ..cũng tính được số cách lắp.
Ngoài ra còn xảy ra trường hợp số nhà làm 1 mạch nhánh lớn hơn 1, như vậy còn phức tạp nữa vì bản thân mạch nhánh đã có thể giao hoán được rất nhiều trường hợp.
Phức tạp quá, để nghĩ tiếp. Bạn nào giải cách khác ngắn hơn đưa ra đi.

Ha ha, tớ tìm ra cách giải rồi !
Có n nhà và 1 nhà máy phát điện, ta có thể biện luận gồm n+1 điểm, các điểm được nối với nhau bằng các đoạn dây dẫn. Vì không tồn tại mạch vòng nên số đoạn dây phải là tổng số điểm trừ 1 hay bằng n.
..
Sau khi biện luận một hồi, đáp số ra như sau. Gọi số cách mắc là N, ta có:
N = A - B
A : Tổng số cách lắp tính cả tồn tại mạch vòng
B: Tổng số cách lắp tồn tại mạch vòng
A = (M!/(M-n)!)/n!
Với M = (n+1)!/(2.(n-1)!)
B=(n+1)!*(1/3.(n-2)! + 1/4(n-3)! +..+1) Tổng số n-2 số hạng
Thử lại:
Với n=1 : M =1; A =1, B =0, ==> N=1 đúng
n=2 : M = 3, A = 3, B=0, ==> N = 3 đúng
n=3: M = 6, A = 20, B = 4, ==> N = 16 đúng
n=4 : M = 10, A = 210, B= 15, ==> N = 195 : không thử được
n=5 : M = 15, A = 3003, B= 41, ==> N = 2962: không thử được.
.....
n=10; M = 55, A = 2925E7, B=39918780, ==> N = 29208730650
Chắc chắn không ai có thể ngồi đếm tổng số cách mắc chỉ với n =5

Được soundwork11 sửa chữa / chuyển vào 02:37 ngày 16/05/2007

Cảm ơn anh Thohry nhiều vì đã tham gia giải bài này.
Nhưng cách làm của anh là không đúng vì...( em mà nói ra là anh giải được luôn, nên anh cố gắng tự tìm hiểu nhé)
và tất yếu anh có kết quả sai với đáp án.
( em cũng đơn thuần là người dịch lại bài này thôi)
Vậy mong anh, và những anh chị em khác vẫn cố gắng tiếp tục tìm lời giải.
Chào thân ái và quyết thắng.

Cảm ơn anh Thohry nhiều vì đã tham gia giải bài này.
Nhưng cách làm của anh là không đúng vì...( em mà nói ra là anh giải được luôn, nên anh cố gắng tự tìm hiểu nhé)
và tất yếu anh có kết quả sai với đáp án.
( em cũng đơn thuần là người dịch lại bài này thôi)
Vậy mong anh, và những anh chị em khác vẫn cố gắng tiếp tục tìm lời giải.
Chào thân ái và quyết thắng.
[/quote]
Chào bạn VHT, kể ra cũng không vui khi giải sai bài toán. Tớ cũng đã nghĩ hết cách rồi, chắc chờ người khác giải hoặc bạn đưa đáp án ra thôi. Nhưng có một thắc mắc là với n thấp 1, 2, 3 mình đều thử ngồi đếm thì thấy chính xác với công thức. Như vậy có thể đó là một sự trùng lặp, cũng có thể mình hiểu đầu bài không đúng, có nghĩa là kể cả n thấp mình cũng đếm sai. Dù sao đây cũng là bài toán cơ bản để ôn lại một số kiến thức.
Thanks

Tớ nghĩ đã tìm ra chỗ sai. Trong công thức N=A-B, B là số khả năng có tồn tại mạch vòng. Nhưng lý luận của tớ là trong mạch chỉ toàn mạch vòng 3 hoặc toàn vòng 4 ... Thực tế có thể tồn tại cả vòng3, vòng4 hoặc nhiều nữa. Các số n=1 - 3 đếm đúng là bởi n nhỏ thì không tồn tại mạch có 2 vòng và không có vòng 4 nên B mới đúng. Hơn nữa, công thức tính B của tớ không rút gọn được nên mình cũng hơi nghi. Bây giờ thì khẳng định rồi: công thức B sai.