Chủ đề này có 6 trả lời

[supernatural1]

Cho n đoạn dây mỗi đoạn dây dài 1m. Nối mỗi đầu dây với một đầu dây khác( Có thể của cùng một dây) một cách hoàn toàn ngẫu nhiên cho đến khi tất cả các đầu dây được nối( Như vậy có tổng cộng n nút). Hỏi ta kỳ vọng bao nhiêu vòng dây được tạo thành? Ví dụ với n=1 ta luôn có 1 vòng dây; Với n=2, ta có thể có 2 vòng dây mỗi vòng dài 1m với xác suất 1/3( bằng xác suất 1 đầu dây thứ nhất được nối với chính nó), hoặc có 1 vòng dây dài 2m với xác suất 2/3, như vậy kỳ vọng số vòng dây là $ \frac{1}{3}.2+\frac{2}{3}.1=\frac{4}{3} $

[supernatural1]

Ai giải giúp với

[leep]

Bài này ở đâu đó?

[leep]

Mk giải rồi đó, bạn muốn sao?

[master1405]

Vậy bài này làm như thế nào vậy bạn?

[nhattan2308]

Cho n đoạn dây mỗi đoạn dây dài 1m. Nối mỗi đầu dây với một đầu dây khác( Có thể của cùng một dây) một cách hoàn toàn ngẫu nhiên cho đến khi tất cả các đầu dây được nối( Như vậy có tổng cộng n nút). Hỏi ta kỳ vọng bao nhiêu vòng dây được tạo thành? Ví dụ với n=1 ta luôn có 1 vòng dây; Với n=2, ta có thể có 2 vòng dây mỗi vòng dài 1m với xác suất 1/3( bằng xác suất 1 đầu dây thứ nhất được nối với chính nó), hoặc có 1 vòng dây dài 2m với xác suất 2/3, như vậy kỳ vọng số vòng dây là $ \frac{1}{3}.2+\frac{2}{3}.1=\frac{4}{3} $

Đây là một bài toán khá hay, và cái phần ví dụ n = 1, n = 2 nó giống như là đánh lạc hướng, mình nghĩ phần ví dụ đó không cần thiết phải đưa vào bài toán. 

 

Lời giải:

$\textit{Key ideal}$: <đưa bài toán về dạng hồi quy>.  

 

Bắt đầu nào: Có n đoạn dây, vậy chúng ta sẽ có $2*n$ đầu dây (điểm đầu và cuối của mỗi đoạn dây). Hãy tưởng tượng chúng ta sẽ hành động "ngây thơ" chọn bất kỳ 2 đầu dây. Sẽ có 2 trường hợp xảy ra: 

 

1. Chọn  được 2 đầu dây của cùng một đoạn dây.

 

Như vậy thì đã tạo nên 1 vòng dây. Xác suất để chọn được 2 đầu dây của cùng 1 đoạn dây trong $n$ đoạn dây là như sau:

$P = \frac{n}{C^{2}_{2n}} = \frac{n}{\frac{2n!}{2(2n-2)!}} = \frac{1}{2n-1}$.

Sau hành động này chúng ta sẽ còn lại $n-1$ đoạn dây và đã có 1 vòng dây với xác suất như trên. 

2. Chọn được 2 đầu dây từ 2 đoạn dây khác nhau. Sau hành động này chúng ta có được $n-1$ đoạn dây trong đó 1 đoạn dây dài  hơn các đoạn dây còn lại. 

 

Tới đây chắc lời giải đã trở nên rõ ràng, sau cả 2 trường hợp có thể xảy ra cho hành động đầu tiên, chúng ta đều có được $n-1$ đoạn dây. Hơn nữa kỳ vọng số vòng dây có được sau hành đậu đầu tiên là: $\frac{1}{2n-1}$ (bởi vì chỉ có 1 vòng dây được tạo thành với xác suất từ trường hợp 1.)

 

Làm tiếp hành động này cho tới khi không còn đầu dây chưa nối nào chúng ta sẽ có kỳ vọng như sau: 

 

$E = \frac{1}{2n-1} + \frac{1}{2n-3} + ... + \frac{1}{3} + 1 = \sum_{k=0}^{n-1}\frac{1}{2(n-k)-1}  $

Bài viết đã được chỉnh sửa nội dung bởi nhattan2308: 02-04-2018 - 16:45

[leep]

Có n dây, lấy 2 đầu:

+Nếu 2 đầu của cùng một dây, thì được 1 vòng, còn lại n-1 dây.

+Nếu 2 đầu của 2 dây, thì được 0 vòng, còn lại n-1 dây.

Mặt khác, có C2n2 cách chọn 2 đầu dây, trong đó có n cách chọn 2 đầu để có 1 vòng.

Xác suất để có 1 vòng là:Pn=nC2n2=n(2n)!2(2n-2)!=n2n(2n-1)/2=12n-1

_________________

 

LOL đề MASSP