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

Đề bài có cấm mắc vòng đâu nhi?
Cách giải của tớ theo phương pháp truy hồi: giả sử đã biết số cách mắc cho n-1 ngôi nhà, ta thêm vào ngôi nhà thứ n. Có tất cả 2^n -1 cách mắc điện ngôi nhà thứ n này với mạng hiện có, như vậy tổng số cách mắc sẽ bằng số cách mắc cho n - 1 ngôi nhà nhân với 2^n - 1.

Bài này hình như vẫn chưa loại những trường hợp n-1 đầu dây mắc vào bất kỳ trong (n+1) điểm sẽ có khả năng 2 đầu dây cùng mắc vào 1 điểm .

Thực ra cách giải bài này xuất phát từ việc lập ma trận điểm - cạnh của một mạng lưới . Rõ ràng là trong một ma trận như vậy không thể tồn tại trạng thái của một cạnh là cùng vào và ra tại môt điểm. Do vậy không cần xét tới trường hợp 2 nửa đoạn dây đi ra và vào tại cùng một nhà .

Bây giờ em mới đọc tới cái lý luận này của bác .
Tại sao lại không có mạch vòng trong mạng là bởi vì đầu bài cho đấu điện từ nhà máy tới các hộ tiêu thụ . Như vậy đấu mạch vòng sẽ sử dụng dây lãng phí vì trong một vòng kín ta có thể cất bớt đi một đoạn dây bất kỳ mà vẫn không làm ảnh hưởng tới sự cấp điện của hệ. Tất nhiên ở đây không đề cập tới vấn đề chịu tải của dây dẫn vì cứ chập 2 dây làm một thì dây lại tải được gấp đôi .

Nếu tính cả mạch vòng thì đáp án chính là A trong bài giải thứ nhất.

Chưa chắc cách mắc không có vòng là luôn luôn không tốn dây đâu. Ở đây chỉ hỏi số cách mắc, còn có tốn dây hay không thì trở về cái bài tớ cho trên kia: chỉ cần tìm 1 cách mắc sao cho tổng chiều dài dây ngắn nhất .

Nếu lý luận như bác thì em cũng có thể lý luận thế này: Giả sử đáp số tồn tại N cách mắc, ta luôn luôn có thêm một cách mắc thứ N+1 bằng cách nối một điểm với một điểm bất kỳ khác bằng một đoạn dây (xem hình vẽ, trường hợp III). Như vậy bài toán sẽ tồn tại vô số nghiệm.
Cũng trong hình vẽ trên, với n=3, ở trường hợp II , 2 đoạn dây ở phía trên hoàn toàn có thể bỏ đi mà không làm ảnh hưởng tới việc truyền điện tới từng hộ. Trong một cách lắp mà ta có thể bỏ đi một dây vẫn không làm ảnh hưởng tới sự truyền điện thì có thể coi như không tính cách đó.
Nếu bài toán tính tới có thể tạo vòng như trường hợp II thì đáp số chính là A, còn nếu tính tới cả trường hợp III (vòng tạo bởi 2 nút) thì bài toán vô số nghiệm.