Các phương pháp đếm nâng cao
#1
Đã gửi 04-05-2006 - 19:19
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
- Trần Đức Anh @@, caybutbixanh, shinichigl và 11 người khác yêu thích
#2
Đã gửi 04-05-2006 - 21:03
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.
- terencetao25 yêu thích
Để một mai tôi trở về cát bụi...
.TCS.
#3
Đã gửi 04-05-2006 - 22:25
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
#4
Đã gửi 05-05-2006 - 20:48
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 đã ).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
Vì chưng xa cách nên người nhớ nhau
#5
Đã gửi 05-05-2006 - 21:00
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 .
#6
Đã gửi 05-05-2006 - 22:15
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.
- terencetao25 và ineX thích
#7
Đã gửi 06-05-2006 - 08:27
#8
Đã gửi 06-05-2006 - 08:31
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.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.
#9
Đã gửi 06-05-2006 - 09:56
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.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 ?
#10
Đã gửi 06-05-2006 - 16:34
- nguyenducnhan yêu thích
Vì chưng xa cách nên người nhớ nhau
#11
Đã gửi 06-05-2006 - 16:36
#12
Đã gửi 06-05-2006 - 16:40
#13
Đã gửi 07-05-2006 - 01:09
Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:05
#14
Đã gửi 07-05-2006 - 01:18
Bài viết đã được chỉnh sửa nội dung bởi inhtoan: 11-06-2009 - 10:05
#15
Đã gửi 07-05-2006 - 01:26
#16
Đã gửi 07-05-2006 - 22:10
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
- terencetao25 và ineX thích
#17
Đã gửi 08-05-2006 - 13:37
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
#18
Đã gửi 09-05-2006 - 23:53
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
- ineX yêu thích
#19
Đã gửi 10-05-2006 - 05:49
#20
Đã gửi 10-05-2006 - 06:34
kết quả là n!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}$.
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
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh