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

[namdung]

Các bạn thân mến,

Tôi dự định viết 1 số bài viết mở về các phương pháp đếm nâng cao

+ Phương pháp song ánh
+ Phương pháp Quan hệ đệ quy
+ Phương pháp Quỹ đạo
+ Phương pháp thêm bớt
+ Phương pháp hàm sinh

Tôi rất muốn biết ý kiến của các bạn về vấn đề này, cũng như cần một số bài toán để minh họa cho các phương pháp. Nếu các bạn có ý kiến gì, cũng như có những bài toán hay về đếm số phần tử của một tập hợp, xin gửi lên để chúng ta có "thức ăn" để thảo luận các phương pháp.

Namdung

[TinhCa]

Đọc bài viết này của thầy, em bỗng nhớ đến một bài báo thầy đã viết trên tạp chí THTT về phương pháp đếm phần tử của một tập hợp, hình như năm 2001 hay 2002 gì đó, tiếc là em không nhớ rõ nội dung của bài báo đó nữa, chỉ nhớ về ý mà thầy muốn viết trong bài báo là thay vì đi tính số phần tử của một tập hợp bằng những công thức tổ hợp rất phức tạp, đôi khi phương pháp song ánh lại đem cho ta kết quả đơn giản đến bất ngờ. Và câu hỏi được đặt ra là tại sao 2 tập hợp là tương đương, thế mà đếm số phần tử trên một tập hợp là gần như không thể, trong khi đếm số phần tử trên tập hợp kia lại đơn giản và cực kỳ sáng sủa. Đúng là hồi ấy em cũng đã suy nghĩ về những câu hỏi này nhưng chưa tìm được giải đáp, không ngờ hôm nay lại có dịp được trao đổi với chính tác giả bài báo trên diễn đàn

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ế).

Hỏi rằng có thể có những phương pháp mở rộng lên không gian như thế nào từ bài toán này.

[vnm]

ở topic này có đề cập một ít các bài toán đếm số đường đi:
http://diendantoanho...topic=11404&hl=
Bài viết của thầy NamDung về phương pháp song ánh rất hay;em rất thích cách thầy dẫn dắt vấn đề;lấy ví dụ là bài thi APMO1998;nếu làm theo cách chính tắc(cách 1) bằng công thức tổ hợp thì khá dài dòng phức tạp;nhưng nếu nhìn qua con mắt song ánh thì có thể cải tiến lời giải ngắn gọn(lời giải 2);và đôi lúc nảy ra những ý chói lọi(lời giải 3)
Em sẽ cố gửi bài cho thầy trong thời gian sớm nhất

[Hatucdao]

Các bạn thân mến,

Tôi dự định viết 1 số bài viết mở về các phương pháp đếm nâng cao

+ Phương pháp song ánh
+ Phương pháp Quan hệ đệ quy
+ Phương pháp Quỹ đạo
+ Phương pháp thêm bớt
+ Phương pháp hàm sinh

Tôi rất muốn biết ý kiến của các bạn về vấn đề này, cũng như cần một số bài toán để minh họa cho các phương pháp. Nếu các bạn có ý kiến gì, cũng như có những bài toán hay về đếm số phần tử của một tập hợp, xin gửi lên để chúng ta có "thức ăn" để thảo luận các phương pháp.

Namdung

Hì hi, hồi trước em cũng có 1 ít suy nghĩ viết về pp song ánh (nhân đọc bài của thầy trên THTT:D ), để hôm sau post lên (về lục đã ).

[clmt]

Bài viết của thầy khá sơ sài chỉ trình bày lg của một số bài.Lần này viết chắc phảu công phu lắm.
Thầy có thể trình bày pp 3 và 4 ko?En ko hiểu cách thầy đặt tên.
Các pp còn lại,có thể đọc các sách nước ngoài,họ viết rất hay và hệ thống,nếu có thể đưa vào thì rất tốt .

[namdung]

Thực ra thì tôi cũng chỉ muốn đưa ra những vấn đề để chúng ta cùng xây dựng, chứ không có tham vọng viết được cái gì công phu. Tư tưởng của phương pháp song ánh rất đơn giản: nếu tồn tại song ánh f từ A vào B thì |A| = |B|. Ngoài ra, nếu s = |A|, t = |A| thì s = t. Nó cũng đơn giản như nguyên lý Dirichlet vậy đó. Quan trọng là biết cách áp dụng vào các bài toán.

Phương pháp quỹ đạo, cái này tôi gọi theo lịch sử, thầy Đỗ Đức Thái ngày xưa gọi như vậy, là phương pháp quy các bài toán đếm về các bài toán đếm số đường đi trên lưới nguyên. Trong phương pháp này, có một nguyên lý rất hay gọi là nguyên lý đối xứng gương (ví dụ VNTST 2003, bài 1). Định lý cơ bản của phương pháp này là số đường đi ngắn nhất trên lưới nguyên từ (0, 0) đến (m, n) bằng C(m, m+n).

Phương pháp thêm bớt là Principle of exclusion and inclusion là phép đếm sử dụng công thức mở rộng của công thức |A hợp B| = |A | + |B| - |A giao B| và thể hiện thường thấy nhất là trong lý thuyết đa thức xe (trong giáo trình Toán rời rạc nâng cao hoặc trong cuốn Tìm tòi để học toán của Lê Quang Nẫm có trình này).

Tất cả những điều này không có gì mới. Mục đích của tôi là cùng chia sẻ và trao đổi với các bạn về những phương pháp này.

[clmt]

Em hiểu rồi,thưa thầy,cuốn 'Toán rời rạc nâng cao'có thể tìm thấy ở đâu ?

[nthd]

Thực ra thì tôi cũng chỉ muốn đưa ra những vấn đề để chúng ta cùng xây dựng, chứ không có tham vọng viết được cái gì công phu. Tư tưởng của phương pháp song ánh rất đơn giản: nếu tồn tại song ánh f từ A vào B thì |A| = |B|. Ngoài ra, nếu s = |A|, t = |A| thì s = t. Nó cũng đơn giản như nguyên lý Dirichlet vậy đó. Quan trọng là biết cách áp dụng vào các bài toán.

Phương pháp quỹ đạo, cái này tôi gọi theo lịch sử, thầy Đỗ Đức Thái ngày xưa gọi như vậy, là phương pháp quy các bài toán đếm về các bài toán đếm số đường đi trên lưới nguyên. Trong phương pháp này, có một nguyên lý rất hay gọi là nguyên lý đối xứng gương (ví dụ VNTST 2003, bài 1). Định lý cơ bản của phương pháp này là số đường đi ngắn nhất trên lưới nguyên từ (0, 0) đến (m, n) bằng C(m, m+n).

Phương pháp thêm bớt là Principle of exclusion and inclusion là phép đếm sử dụng công thức mở rộng của công thức |A hợp B| = |A | + |B| - |A giao B| và thể hiện thường thấy nhất là trong lý thuyết đa thức xe (trong giáo trình Toán rời rạc nâng cao hoặc trong cuốn Tìm tòi để học toán của Lê Quang Nẫm có trình này).

Tất cả những điều này không có gì mới. Mục đích của tôi là cùng chia sẻ và trao đổi với các bạn về những phương pháp này.

PP quĩ đạo là phương pháp khá cổ điển các bạn có thể tìm thấy nó trong bài viêt của GS.Hilton năm 1989,hoặc báp THTT năm 1980.

[namdung]

Em hiểu rồi,thưa thầy,cuốn 'Toán rời rạc nâng cao'có thể tìm thấy ở đâu ?

Cuốn "Toán rời rạc nâng cao" của Trần Ngọc Danh, NXB Đại học QG Tp HCM 2004.

[Hatucdao]

Hì, về lục mãi mới ra ... hi vọng góp vài ví dụ minh họa (đây là "phiên bản" thời 2002, ko biết có lạc hậu chưa )

Hình gửi kèm

• 

[Hatucdao]

(tiếp theo)

Hình gửi kèm

• 

[Hatucdao]

(tiếp theo)

Hình gửi kèm

• 

[nmt]

Thưa thầy, các bài viết đếm số phần tử của tập họp bằng song ánh là khá hay. Và em cũng đã nhiều lần muốn đề cập đến, nhưng lại không biết viết cho ai, gửi ở đâu. Có lẽ gửi lên diễn đàn của ta là có vẻ hợp lí. Em sẽ gửi lên những bài đếm số phần tử mà em đã gặp và có thể giải bằng song ánh. Trong số các phương pháp song ánh hay quan hệ tương đương, em thấy có 1 phương pháp khá độc đáo là giải bài từ đáp số, chúng ta có thể "mò" ra đáp số (gọi là dự đoán thì có vẻ khoa học hơn), hoặc giải bằng cách nào đó cho ra đáp số, rồi có thể sử dụng phương pháp song ánh, khi đó lời giải sẽ ngắn gọn hơn rất nhiều. Ví dụ rất nhiều bài cho kết quả là $C^k_n$, hay $2^n$, hay rắc rối hơn như $\sum_1^nC^i_{n+i}...$, thì ta có thể giải bằng song ánh và quan hệ tương đương. Ngay lúc này em không nhớ rõ ràng và chính xác các bài toán có liên quan, nhưng em sẽ gửi lên sớm trong vài ngày tới.

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

[nmt]

Hồi trước trên báo toán có bài tìm công thức tổng quát của dãy số: $a_{n+1}=a_0.a_n+a_1.a_{n-1}+...+a_{n-1}a_1+a_n.a_0$ em không nhớ rõ lắm $a_n=\dfrac{C^n_{2n}}{n+1}$, họ giải bằng cách dùng chuỗi số, và đương nhiên, nó không hề sơ cấp. Nhờ có công thức này mà em cũng đã giải được 1 bài toán khá là lằng nhằng bằng song ánh: Trên đường tròn lấy $2n$ điểm cách đều nhau $A_1,A_2,...,A_{2n}$, tìm số cách nối các điểm đó bởi n đoạn thẳng mà không có 2 đoạn nào có điểm chung (kể cả mút). Mọi người thủ làm bài trên xem sao. nếu có thể hãy giải bằng song ánh, rồi sau đó chứng minh công thức của dãy số ban đầu mà không cần sử dụng chuỗi số như trên báo toán đã làm.

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

[nmt]

Nói riêng về đếm số phần tử của tập hợp thì hình như cách đây mấy năm đã có 1 bài viết của thầy Nguyễn Khắc Minh ở trên bộ và đã gửi về cho các trường chuyên, coi nó như 1 phần của chương trình thi QGia. Ai có thì gửi lên cho mọi người. nmt cũng có nhưng phải đợi dịp nào về Hải Phòng mới tìm lại đựơc.

[namdung]

Chào nmt và các bạn,

1) Đúng là bài $a_{n+1} = a_0a_n + a_1a_{n-1} + ...+ a_na_0$ có thể giải bằng chuỗi (chính là phương pháp hàm sinh). Tuy nhiên, vẫn có thể giải bằng cách khác, sơ cấp hơn. Cái số mà nmt nói ở đáp số gọi là số Catalan. Số Catalan có rất nhiều cách định nghĩa, trong đó có cách dùng 2n điểm trên đường tròn và n dây cung không cắt nhau nối chúng. Ngoài ra có 1 cách khác: đó là số đường đi trên lưới nguyên từ (0, 0) đến (n, n) nhưng không vượt lên trên đường thẳng y = x.
Chính là cách định nghĩa này sẽ dẫn đến 1 lời giải hoàn toàn sơ cấp dùng phương pháp quỹ đạo và cụ thể hơn là nguyên lý đối xứng gương.

2) Bài viết của thầy NKM rất hay và thực sự là xuất phát điểm cho nhiều bài toán sau này. Các bài trong đó còn tổng quát hơn bài TST năm ngoái nhiều.

3) Hình như cái file của hatucdao làm anh em đọc hơi khó. Anh em có cách nào làm cho nó nhỏ lại không?

4) Ý của nmt về chuyện nhìn đáp số tìm ra cách giải ngắn là rất chính xác. Thực ra các lời giải APMO 1997 trong bài viết của tôi không có ngay đâu, mà chỉ có sau khi tôi đã tìm được đáp số bằng cách dài dòng kia.

5) Ai có cách chứng minh đẳng thức $1^3 + 2^3 + ... + n^3 = (\dfrac{n(n+1)}{2})^2$ bằng tổ hợp không?

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

[phtung]

http://diendantoanho...?showtopic=6944
http://diendantoanho...showtopic=10640
http://www.mathlinks...opic-38453.html
http://diendantoanho...?showtopic=8345

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

[nmt]

Cho số nguyên dương $n$, một dãy số gồm $n$ số nguyên dương được gọi là "hoàn hảo" nếu nó thỏa mãn điều kiện: "với mọi $k$ thì cũng có một số hạng khác của dãy bằng $k-1$, đồng thời trong dãy số đó, lần xuất hiện đầu tiên của số $k-1$ đứng ngay trước lần xuất hiện cuối cùng của số $k$"
Hỏi có bao nhiêu dãy số "hoàn hảo".

Bài này có thể giải bằng truy hồi, kết quả khá đẹp là $2^{n-1}$. nếu có thể các bạn hãy giải bằng 1 cách ngắn gọn, sử dụng kết quả trên.
---------------
Bài này hình như là thi chọn đội tuyển năm 97.

Cho trước các số nguyên dương $k,n$ với $k$ $(a_1,a_2,...,a_k)$ của $n$ số nguyên dương đầu tiên mà mỗi chỉnh hợp thỏa mãn ít nhất một trong hai điều kiện sau:
$(1)$ Tồn tại $s,t\in\{1,2,...,k\}$ để: $a_s>a_t$ và $s<t$.
$(2)$ Tồn tại $s\in\{1,2,...,k\}$ để: $2\not|a_s-s$.

Bài trên có 1 cách giải khá nhanh và đơn giản nhờ một tương ứng sau khi biến đổi một chút các $a_i$. Ngoài ra còn 1 cách giải dài dòng hơn bằng truy hồi. Rất mong các bạn cùng tham gia giải, đặc biệt là cách truy hồi.
--------------

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

[1001001]

Ai đó viết qua về pp đếm sử dụng công thức nghịch đảo Mobius và lý thuyết Polya đi .

[gadget]

Cho số nguyên dương $n$, một dãy số gồm $n$ số nguyên dương được gọi là "hoàn hảo" nếu nó thỏa mãn điều kiện: "với mọi $k$ thì cũng có một số hạng khác của dãy bằng $k-1$, đồng thời trong dãy số đó, lần xuất hiện đầu tiên của số $k-1$ đứng ngay trước lần xuất hiện cuối cùng của số $k$"
Hỏi có bao nhiêu dãy số "hoàn hảo".

Bài này có thể giải bằng truy hồi, kết quả khá đẹp là $2^{n-1}$.

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

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