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

Mắc dây đơn hay dây đôi?

Chế thành bài khác nè:
Cho n ngôi nhà và 1 nhà máy điện đã biết tọa độ trong mặt phẳng xOy. Tìm cách nối dây điện đôi sao cho cả n ngôi nhà có điện và tổng chiều dài dây điện cần dùng là ngắn nhất?

Tớ vừa nghĩ ra cách giải khác bài toán của bạn Vuhongthai. Đáp số có vẻ ngắn gọn hơn nhiều:
N=(n+1)^(n-1).
Thử lại:
với n=1 , N=1
n=2 , N=3
n=3, N=16, đúng như đếm tay.
n=4 , N=125.
Hy vọng đúng, không dám chắc 100%

Làm đệ quy cho khỏe, nếu là dây đôi thì số cách mắc là:
[2^n - 1][2^(n-1) - 1][2^(n-2) - 1]...........[2^1 - 1]

Hình phải thoả mãn:
-Dây nối phải là dây đơn.
-Là một vòng kín duy nhất đi qua tất cả các điểm .
-Dây nối giữa các điểm phải thẳng.
-Moi diem chi co duy nhat 2 doan thang di qua.

Mắc nối tiếp thế này thì chả nhà nào xài điện được cả bạn ơi.

hoá ra o phải là lí tưởng , thế thì làm sao xác định là ngắn nhất được vậy hả bác.

Trong N cách mắc đã liệt kê ở bài trên, chắc chắn sẽ có cách mắc cho ra tổng chiều dài dây ngắn nhất.

Sao anh thohry và werty không cho 1 lời giải đầy đủ .
Mình làm để mọi người học hỏi tham khảo mà, mấy anh viết vậy đâu phải ai cũng hiểu, ví dụ là em đây.
Mong 2 anh chịu khó đưa lời giải đầy đủ nhé .

Tớ chưa chắc chắn lắm nên mới chỉ đưa đáp số . Thực ra cách làm khá đơn giản .
Trước tiên lý luận như phần trên, nhà máy điện và n hộ tiêu thụ coi như n+1 điểm khác nhau . Nguyên tắc lắp điện là phải không được tạo mạch vòng (vì phí dây không cần thiết), như vậy tổng số đoạn dây nối giữa 2 điểm bất kỳ sẽ là n. Một yêu cầu nữa là điểm nào cũng phải có ít nhất một đầu dây để đảm bảo nhà nào cũng có điện .
Như vậy sẽ có tổng số 2n đầu dây, trong đó có (n+1) đầu dây đã chia hết cho các hộ, do đó còn lại (n-1) đầu dây sẽ phải phân phối bất kỳ cho tổng số (n+1) điểm. Số cách phân phối chính là đáp số . Đó chính là chỉnh hợp lặp chập (n-1) của (n+1) phần tử và đáp số như các bác đã thấy khá đơn giản : N=(n+1)^(n-1).
Nếu chia đều cứ 1 điểm một đầu dây thì luôn thiếu 2 đầu dây, đó là cách nối mạng liên tiếp (trong hóa hữu cơ gọi là mạch thẳng), 2 điểm bị thiếu chính là vị trí ở 2 đầu chót mạng .
Nếu chia tất số đầu dây cho một điểm nào đó thì ta có cách đấu hình sao với điểm được chia đó chính là trung tâm, các điểm còn lại đóng vai trò vệ tinh.
Bài giải trước của tớ làm hoàn toàn theo một hướng khác, và bị sai ở khâu tính B : tổng số mạch vòng có thể tồn tại trong một mạng n dây và n+1 điểm. Cái này đã giải thích ở trên.