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

[nmt]

kết quả là n!
bài này tớ dùng song ánh để chứng minh S_n=nS_{n-1}

n=3 thì chỉ có 4 dãy
1,1,1
1,2,1
1,2,3
2,1,2
Có lẽ mỗi lần đếm xong bạn nên thử lại

Bài viết đã được chỉnh sửa nội dung bởi nmt: 10-05-2006 - 09:10

[lehoan]

Nhân chủ đề này em xin nêu luôn một vấn đề tự đặt ra nhưng chưa giải quyết xong, đấy là bài toán mở rộng lên không gian từ bài toán gốc: Đếm số đường đi có thể từ một đỉnh của hình vuông đến đỉnh đối diện, thỏa mãn đường đi theo từng nấc đơn vị, không đi lùi, không đi xuống. (Hì hì, để cho dễ thì em tạm diễn đạt như thế).

.

lehoan còn nhớ là bài toán này đã được giải quyết khi ở diễn đàn cũ. Hình như đáp số cho hình hộp ${M\choose{M+N+K}}{N\choose{M+N+K}}{K\choose{M+N+K}}$( có lẽ là thế cũng không rõ lắm )

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:12

[lehoan]

Thầy namdung có thể nói qua cái phương pháp thêm bớt không? lehoan chưa khi nào nghe về phương pháp này

[namdung]

Phương pháp này tiếng Anh gọi là Principle of Exclusion and Inclusion, tiếng Việt chẳng biết dịch là gì (thêm bớt, bù trừ). hệ

Phương pháp này sử dụng công thức mở rộng của công thức

|A U B| = |A | + |B| - |A giao B|

để đếm các tập con của một tập hợp thỏa mãn một số tính chất nào đó.

Ví dụ: Ta cần tìm số nghiệm của phương trình x + y + z = k với x, y, z thuộc [0, 9]. Bài x + y + z = k với x, y, z không âm thì mình biết rồi, đáp số là C(2, k+2). Nhưng điều kiện x, y, z thuộc [0, 9] sẽ loại bỏ đi một số nghiệm. Đặt A = {(x, y, z)| x+y+z = k, x > 9}, B, C tương tự (thay x, bằng y, z) thì số nghiệm bị loại chính là A U B U C và dùng công thức trên ta có thể tìm được |A U B UC|. Đại loại chỉ có thế thôi.

Namdung

[gadget]

are you sure
1,1,1
1,1,2
1,2,3
1,2,1
2,1,2
1,2,2

Bài viết đã được chỉnh sửa nội dung bởi gadget: 10-05-2006 - 13:17

[nmt]

are you sure
1,1,1
1,1,2
1,2,3
1,2,1
2,1,2
1,2,2

lần đầu tiên của k-1 ngay trước lần cuối của k. Bạn còn không đọc kĩ đề bài; )

[nmt]

Phương pháp này tiếng Anh gọi là Principle of Exclusion and Inclusion, tiếng Việt chẳng biết dịch là gì (thêm bớt, bù trừ). hệ

Phương pháp này sử dụng công thức mở rộng của công thức

|A U B| = |A | + |B| - |A giao B|

để đếm các tập con của một tập hợp thỏa mãn một số tính chất nào đó.

Ví dụ: Ta cần tìm số nghiệm của phương trình x + y + z = k với x, y, z thuộc [0, 9]. Bài x + y + z = k với x, y, z không âm thì mình biết rồi, đáp số là C(2, k+2). Nhưng điều kiện x, y, z thuộc [0, 9] sẽ loại bỏ đi một số nghiệm. Đặt A = {(x, y, z)| x+y+z = k, x > 9}, B, C tương tự (thay x, bằng y, z) thì số nghiệm bị loại chính là A U B U C và dùng công thức trên ta có thể tìm được |A U B UC|. Đại loại chỉ có thế thôi.

Namdung

cũng phương pháp này còn có bài: Tính số hoán vị $(a_1,a_2,...,a_n)$của $n$ số nguyên dương đầu tiên mà tồn tại $a_i=i+1$

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:13

[namdung]

Một số bài toán dẫn nhập

1. (Bài toán về những chiếc vé hạnh phúc) Vé xe buýt có số serie là 1 số có 6 chữ số dạng abcdef. Vé được coi là hạnh phúc nếu a + b + c = d + e + f. Hãy tính xác suất để một vé được mua ngẫu nhiên là vé hạnh phúc.

2. (Bài toán về xếp hàng) Có m+n người xếp hàn mua vé (m>=n). Có m người chỉ có tiền 5.000, có n người chỉ có tiền 10.000. Giá vé là 5.000, trong quầy ban đầu không có tiền lẻ. Tính xác suất của sự kiện: trong quá trình mua vé, không có ai phải đợi.

3. (Số nghịch thế) Bộ (i, j) được gọi là nghịch thế của hoán vị f: {1, 2, ..., n} --> {1, 2, ..., n} nếu f(i) > f(j) mà i < j. Hãy tính số nghịch thế trung bình của một hoán vị.

4. (Bài này chưa có lời giải) Có n người xếp thành 1 hàng dọc. Có bao nhiêu cách chọn ra k người sao cho trong 3 người liên tiếp có không quá 2 người được chọn.

5. Bàn cờ 8 x 8 bỏ đi 1 đường chéo chính (a1, b2, c3, ..., h8) và các ô (a2, b3, ..., g8, h1). Hỏi có bao nhiêu cách xếp 8 quân xe trên phần còn lại để không con nào ăn con nào.

Nếu các bạn có lời giải cho một trong các bài toán trên, hãy post lên để chúng ta cùng tham khảo. Tôi sẽ dùng các bài toán này để minh họa cho các PP của đã đề cập.

[gadget]

uh;n! là số dãy t/m vị trí xuất hiện của k-1 ở sau vị trí x/h cuối cùng của k
sorry
các bạn thử làm bài trên xem cũng không dễ

Bài viết đã được chỉnh sửa nội dung bởi gadget: 10-05-2006 - 19:34

[lehoan]

2. (Bài toán về xếp hàng) Có m+n người xếp hàn mua vé (m>=n). Có m người chỉ có tiền 5.000, có n người chỉ có tiền 10.000. Giá vé là 5.000, trong quầy ban đầu không có tiền lẻ. Tính xác suất của sự kiện: trong quá trình mua vé, không có ai phải đợi.

Đối với bài toán này em đã có lời giải cho cả trong trường hợp tổng quát khi mà người giữ xe có trước p tờ 5000.

Em sẽ post lời giải vào ngày mai nhưng nói chung là dùng song ánh.

Thêm nữa ở bài toán sô 1 thì a có thể bằng 0 chứ thầy

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:14

[namdung]

OK, lehoan, em post lên sớm nhé. Những bài toán kinh điển thường có nhiều cách giải đẹp.

Với bài Happy ticket thì đúng là a có thể bằng 0.

[lehoan]

Ta kí hiệu người có tờ 5000 đ là A, người có tờ 10000 đ là B. Như vậy số cách xếp hàng là ${{m+n}\choose{m}}$.

Gọi một cách xếp hàng là tốt nếu nó thỏa mãn bài toán và xấu nếu ngược lại.

Như vậy ta có một cách xếp hàng là tốt nếu tại mọi điểm thì số chữ A không bé hơn số chữ B.

Bây giờ ta có một hàng là xấu nếu tồn tại một chữ B sao cho ở trước chữ B đó có đúng s chữ A và s chữ B. (${{m+n}\choose{m+1}}$. Hay ta có số dãy tốt là :
${{m+n}\choose{m}}-{{m+n}\choose{m+1}}$ .

Còn nếu ban đầu người giữ xe có q tờ 5000 thì tương tự ta có số hàng tốt là :
${{m+n}\choose{m}}-{{m+n}\choose{m+q+1}}$

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:14

[gadget]

ta cần tính số đường đi từ (0;0 tới (m;n) thỏa mãn luôn ở đưới đường y=x
dễ thấy bước đầu tiên là đi tới (1;0)
Số đường đi từ (1;0) tới (m;n) là $C_{m+n-1}^{m-1}$
Mỗi cách đi ở trên đường thẳng y=x ta lấy đối xứng qua y=x những đoạn ở dưới đừong thẳng y=x;cho tương ứng một cách đi từ (0;1)->(m;n)->$C_{m+n-1}^{m}$
->có $C_{m+n-1}^{m-1}-C_{m+n-1}^{m}$ cách

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:15

[gadget]

1bài tổng quát:tìm số đường đi từ (0;0) tới (m;n) luôn ở dứoi đường thẳng y=mx/n.(m;n)=1
Dùng bổ đề:số đường đi từ (0;0)->(w;h) luôn ở dưới dt nối (0;) và (m;n) có k bước rẽ phải là http://dientuvietnam.net/cgi-bin/mimetex.cgi?\dfrac{1}{k+1}C_{w-1}^{k}.C_{h-1}^{k}
bài 3 có trong quyển 19 nước bài 5 có trong quyển Tìm tòi để học toán của LQN

Bài viết đã được chỉnh sửa nội dung bởi gadget: 13-05-2006 - 15:31

[namdung]

Nói một chút về bài toán vé hạnh phúc. Khi tôi còn là sinh viên, trong giới sinh viên truyền tụng nhau câu chuyện về vé hạnh phúc. Họ nói rằng ai mua được vé như vậy sẽ gặp may, như là sẽ có bạn gái đến thăm, đi thi thì bốc được vé dễ ... và đặc biệt sẽ càng may mắn nếu bạn nuốt lấy chiếc vé hạnh phúc đó.

Tôi cũng sưu tầm được mấy chục cái vé hạnh phúc trong mấy năm học đại học của mình. Tuy nhiên, đối với sinh viên khoa toán thì họ còn quan tâm đến 1 câu hỏi nữa. Xác suất để gặp 1 vé hạnh phúc là bao nhiêu?

Để tính xác suất này, ta cần tìm xem trong 1 triệu số từ 000000 đến 999999 có bao nhiêu số abcdef có tính chất a+b+c=d+e+f

Lời giải 1:
Đây là lời giải dễ đi đến nhất, rất tự nhiên. Thời sinh viên chúng tôi đã giải như vậy.
Gọi c(k) là số nghiệm của phương trình a + b + c = k, a, b, c thuộc {0, 1, 2, ..., 9} thì rõ ràng
S = c(0)^2 + c(1)^2 + ... + c(27)^2
c(k) với k < 10 tính được khá dễ dàng nhờ bài toán cơ bản gọi là bài toán chia kẹo của Euler:

Định lý: Phương trình x1 + x2 + ... + xk = n có C(k-1,n+k-1) nghiệm nguyên không âm.

Chứng minh: Ta cho tương ứng một nghiệm của phương trình nói trên với một xâu nhị phân độ dài n+k-1 với n bit 1 và k-1 bit 0 theo nguyên tắc sau

(x1, x2, ..., xk) --> 1..101..10...01...1

trong đó đầu tiên có x1 số 1, kế đến 1 số 0, sau đó lại có x2 số 1, tiếp đến 1 số 0 ... cuối cùng là xk số 1. Nếu chẳng hạn xi nào đó bằng 0 thì sẽ có hi số 0 cạnh nhau.

Dễ dàng chứng minh được tương ứng nói trên là 1 song ánh, và từ đó đpcm.

Tuy nhiên với k=10, 11, ... thì trong các nghiệm nguyên không âm của a + b + c = k có những nghiệm mà a hoặc b, hoặc c lớn hơn 9. Ta phải loại những nghiệm này ra. Đặt A = {(a, b, c)| a+b+c = k, a > 9}, tương tự B, C thì

c(k) = c(2,k+2) - |A U B U C|

Mặt khác, xét (a, b, c) thuộc A thì {a-10, b, c} sẽ là nghiệm nguyên không âm của phương trình x + y + z = k - 10. Từ đó | như A| = C(2, k-8)

Bằng cách như vậy ta tính được c(k) và từ đó tính đựoc f.

Khi nghiên cứu các c(k), có một điều ta có thể nhận ra là tính đối xứng của các c(k). Rõ ràng là c(0) = c(27) = 1, c(1) = c(26) ...

Tính chất này có thể được thiết lập bằng cách xây dựng song ánh

(a, b, c) --> (9-a, 9-b, 9-c).

Rất thú vị là chính song ánh này dẫn đến ta 1 lời giải khác, ngắn gọi hơn, đẹp hơn và ít tính toán hơn.

(Còn tiếp)

[nmt]

lời giải đó chính là tương ứng mỗi số hạnh phúc với bộ số 6 chữ số có tổng bằng 27.

[gadget]

Một vài bài toán nữa
1)(quỹ đạo)Một con ếch nhảy từ đỉnh A của một đa giác đều 2x cạnh.Tại mỗi đỉnh của đa giác trừ điểm đối tâm E con ếch có thể nhảy tới 1 trong 2 đỉnh kề nó.Đến E con ếch dừng lai và ở luôn tại đo.Gọi A_n là số đường đi của con ếch có đúng n bước nhảy.Tính A_n(tổng quát IMO21th)
2)(inclusion-exclusion)Có bao nhiêu cách tô màu một đa giác đều 2n đỉnh dùng n màu thỏa mãn mỗi màu dùng để tô đúng 2 đỉnh và 2 đỉnh cạnh nhau có màu khác nhau
Thật ra bài toán xếp hàng lần đầu tiên xuất hiện dưới dạng sau:
Trong một cuộc bầu cử cử tri A thu được x phiếu cử tri B thu được y phiếu(x>y).Hãy tìm xác suất của sự kiện sau:tại mọi thời điểm số phiếu của cử tri A luôn lớn hơn hoặc bằng số phiếu của cử tri B

Bài viết đã được chỉnh sửa nội dung bởi gadget: 14-05-2006 - 08:30

[namdung]

lời giải đó chính là tương ứng mỗi số hạnh phúc với bộ số 6 chữ số có tổng bằng 27.

Đúng vậy, cụ thể ta xây dựng song ánh giữa hai tập hợp

A = {(a,b,c,d,e,f | a, b, c, d, e, f thuộc {0, 1, ..., 9} và a+b+c=d+e+f}

và

B = {(a,b,c,d,e,f| a, b, c, d, e, f thuộc {0, 1, ..., 9} và a+b+c+d+e+f=27}

như sau: f(a, b, c, d, e, f) = (a, b, c, 9 - d, 9 - e, 9 - f)

Từ đó |A| = |B|

Để tính |B|, ta có thể dùng định lý Euler về chia kẹo (và cũng chính là tổ hợp lặp) và phương pháp thêm bớt để ra đáp số là

C(5, 32) - 6C(5, 22) + 15C(5, 12)

Tuy nhiên, tôi muốn trình bày thêm 1 lời giải bằng hàm sinh, từ đó nên ra tư tưởng của phương pháp hàm sinh.

Hẹn các bạn tối nay nhé.

[namdung]

Hàm sinh

Trong phần này chúng ta sẽ nêu ra định nghĩa của hàm sinh, các tính chất cơ bản của hàm sinh. Tiếp đó chúng ta sẽ nêu ra các ứng dụng cơ bản của hàm sinh trong việc giải quyết các bài tóan đếm và giải các phương trình đệ quy.

Định nghĩa

Cho dãy số $(a_n)_{n=0}^{\infty}$. Hàm sinh của dãy $(a_n)$ ký hiệu là G(x) là tổng hình thức
$1/(1-x)^2$ là hàm sinh của dãy số $(a_n)$ với $(a_k+b_k)$ còn f(x).g(x) là hàm sinh của dãy $(c_k)$ với $(a_k)$ trong đó $(b_k)$ trong đó $1/(1-x)^3$ là hàm sinh của dãy ${c_k}$ với ${a_k}$ cho bởi
$(1+x)^n$. Có một số dãy số cũng có hàm sinh có dạng $(1+x)^u$, trong đó u là số thực. Để làm điều này, ta cần đến một số định nghĩa về hệ số nhị thức mở rộng.

Định nghĩa: (Hệ số nhị thức mở rộng) Hệ số nhị thức mở rộng được định nghĩa bởi
$x^r$ trong khai triển lũy thừa của hàm sinh G(x), trong đó G(x) được xác định bởi các điều kiện của bài tóan. Nếu tìm được đúng hàm G(x), ta chỉ cần tìm khai triển lũy thừa của hàm này từ đó suy ra hệ số của $x^r$.

Ví dụ: Tìm số các cách chọn 3 số nguyên không âm có tổng bằng 10.

Ví dụ: Tìm số các chọn các đồng tiền mệnh gía 1$, 5$, 10$, 20$ để được tổng là 25$.

Ví dụ: Tính số chỉnh hợp lặp chập k của n phần tử.

Ý tưởng chính được trình bày trong các lý luận sau:

Đáp số của bài 1 là hệ số của $x^{10}$ trong khai triển

$\dfrac{1}{(1-x)^3}$

Đáp số của bài 2 là hệ số của $x^{25}$ trong khai triển của

$ (1 + x + x^2 + ...)(1+x^5+x^{10}+...)(1+x^{10}+x^{20}+...)(1+x^{20}+x^{40}) $
Đây là điểm rất quan trọng trong lý luận của chúng ta. Nếu hiểu được điểm này thì ứng dụng thứ nhất của hàm sinh là trong tầm tay của các bạn.

Tôi sẽ quay trở lại chủ đề này trong bài tiếp theo. Trước mắt các bạn hãy xem kỹ lại những gì đã được trình bày.

Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:16

[namdung]

Lời giải bài toán Happy ticket bằng phương pháp hàm sinh

Theo như lý luận trước đó, số vé hạnh phúc bằng số nghiệm của phương trình

http://dientuvietnam...1 x x^2 ... x^9)^6

Mà http://dientuvietnam...metex.cgi?A^{(2)}có thể có những phần tử giống nhau)

Chứng minh rằng nếu tồn tại A, B là các tập hợp thỏa mãn điều kiện 1) A khác B, 2) |A| = |B| = n, 3) thì n là lũy thừa của 2.