|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
30-09-2010, 10:23 PM | #1 |
+Thành Viên+ Tham gia ngày: Aug 2008 Bài gởi: 1 Thanks: 9 Thanked 5 Times in 1 Post | Seminar " giải bài toán đếm bằng cách sử dụng công thức truy hồi" Chào các bạn. Seminar tuần tới diễn ra vào ngày 10/10/2010 đúng vào ngày đại lễ 1000 năm Thăng Long Hà Nội, mình xin giới thiệu với các bạn phương pháp giải quyết bài toán đếm bằng công thức truy hồi. Một trong những ví dụ nổi tiếng sử dụng phương pháp này là bài toán "Tháp Hà Nội". Ý tưởng giải bài toán đếm bằng phương pháp truy hồi đưa bài toán đếm từ n đối tượng về bài toán đếm với ít đối tượng hơn và do đó độ phức tạp của bài toán cũng giảm đi. Theo cá nhân mình đầy là chủ đề khá thú vị, các bạn có ví dụ gì hay thì đóng góp cho chủ đề này nhé. Để khởi động minh đưa ra hai bài toán sau: Bài 1. Có bao nhiều xâu nhị phân độ dài 8 trong đó ba bit 1 không được đứng cạch nhau? Bài 2. Cho hình bát giác đều ABCDEFGH. Một con ếch xuất phát từ A. Tại bất kỳ một đỉnh nào trừ đỉnh E, con ếch có thể nhảy tới một trong hai đỉnh kề nó. Nếu con ếch nhảy tới E thì dừng lại. Hỏi con ếch có bao nhiều đường đi gồm n bước từ A đến E? |
The Following 5 Users Say Thank You to ngoctuansp For This Useful Post: | huynhcongbang (01-10-2010), king_k0m_n (07-10-2010), Lan Phuog (03-10-2010), nguyentatthu (01-10-2010), yugioh_vt1993 (01-10-2010) |
30-09-2010, 10:57 PM | #2 | |
Super Moderator Tham gia ngày: Nov 2007 Đến từ: BH Bài gởi: 212 Thanks: 135 Thanked 345 Times in 92 Posts | Trích:
Bài 1:có bao nhiêu số tự nhiên có 2010 chữ số chia hết cho 3 được lập từ các số 3,4,5,6. Bài 2: Cho số nguyên dương$ n $. Gọi $M $ là tập các số tự nhiên có $n $ chữ số, các chữ số đều lớn hơn $1 $ và không có hai chữ số khác nhau cùng nhỏ hơn$ 7 $ đứng liền nhau. a) Chứng minh: trong $M $ , số các số tận cùng bằng $2 $ và số các số tận cùng bằng $3 $bằng nhau. b) Tính số phần tử của $M $theo $n $ | |
The Following 2 Users Say Thank You to nguyentatthu For This Useful Post: | king_k0m_n (07-10-2010), ngoctuansp (01-10-2010) |
01-10-2010, 04:47 AM | #3 |
Administrator | Đếm bằng công thức truy hồi thực sự là một công cụ rất mạnh trong tổ hợp, các bài toán đếm dạng này cũng thường xuất hiện trong các kì thi HSG QG, TST, IMO. Bản thân em cũng rất thích phương pháp này vì sự thú vị của nó và các bài toán khó mà nhờ nó có thể giải được; mong rằng sẽ nhận được thêm nhiều điều mới mẻ và thú vị từ buổi seminar sắp tới! Xin cảm ơn thầy nhiều! __________________ Sự im lặng của bầy mèo |
01-10-2010, 01:48 PM | #4 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 1,250 Thanks: 119 Thanked 616 Times in 249 Posts | Trong này [Only registered and activated users can see links. ] có một bài viết về kỹ thuật đếm sơ cấp. __________________ T. |
The Following User Says Thank You to n.t.tuan For This Useful Post: | ngoctuansp (09-10-2010) |
02-10-2010, 07:35 PM | #5 | |
Administrator | Bài này mới nè: (Đề chọn đội tuyển KHTN 2010) Tìm số hoán vị của {1,2,3,...,n} $(n \ge 2) $ thỏa mãn cả hai điều kiện sau: a) $a_i \ne i $ với mọi i = 1, 2, ..., n b) $a_{i+1} - a_i \le 1 $ với mọi i = 1, 2, ..., n ------------------------------ Trích:
thay đổi nội dung bởi: namdung, 02-10-2010 lúc 07:38 PM Lý do: Tự động gộp bài | |
03-10-2010, 07:25 PM | #6 |
+Thành Viên+ Tham gia ngày: Aug 2008 Bài gởi: 1 Thanks: 1 Thanked 1 Time in 1 Post | Seminar này em chắc chắn sẽ rất thú vị bởi vì đây là một phương pháp rất hay để giải quyết các bài toán đếm và em cũng xin được góp vài bài 1)có bao nhiêu xâu nhị phân dộ dài 7 và ko có 2số 1 liên tiếp 2)cho n đường thẳng trong mp sao cho ko có 2 đường nào song song và ko có 3 đường nào đồng qui a)giả sử n>=2 ,có bao nhiêu giao điểm b)giả sử n>=3,có bao nhiêu tam giác đc tạo thành c)n đường đó chia mp ra làm mấy phần |
The Following User Says Thank You to huaminhtuan For This Useful Post: | ngoctuansp (08-10-2010) |
03-10-2010, 08:35 PM | #7 |
+Thành Viên+ Tham gia ngày: Nov 2007 Đến từ: Konoha Bài gởi: 899 Thanks: 372 Thanked 362 Times in 269 Posts | Ôi , chờ đợi cho qua đám Hình học .Mong đến serminar kì này , nhưng kẹt sinh hoạt chính trị cuối khóa rồi . Seminar vào ngày nào vậy các bạn ? (hi vọng không trùng) |
03-10-2010, 10:50 PM | #8 |
Moderator Tham gia ngày: Apr 2008 Đến từ: Hàm Dương-Đại Tần Bài gởi: 698 Thanks: 247 Thanked 350 Times in 224 Posts | Seminar lần này tổ chức ở đâu và khi nào hả các bạn? Các bạn cho mình biết dùm, có bỏ học cũng phải đi tham dự ^^ __________________ As long as I live, I shall think only of the Victory...................... |
03-10-2010, 10:54 PM | #9 | |
+Thành Viên+ | Trích:
Nhân đây cũng nhắc mọi người luôn: Seminar sẽ diễn ra 2 tuần 1 lần, vẫn ở địa điểm và thời gian như trên. | |
06-10-2010, 02:16 PM | #10 |
Super Moderator Tham gia ngày: Nov 2007 Đến từ: BH Bài gởi: 212 Thanks: 135 Thanked 345 Times in 92 Posts | |
07-10-2010, 06:20 PM | #11 |
Administrator | Vậy là tuần này vui rồi. Bổ sung thêm mấy bài toán nữa. [1] (Canadian MO 2009) Cho hình chữ nhật 3 x n ô. Một quân xe xuất phát từ ô góc trên bên trái và đi đến ô góc dưới bên trái sao cho đường đi của nó tạo thành một đường gấp khúc không tự cắt. Hỏi có bao nhiêu cách đi như thế? [2] Cho X = {1, 2, ..., n}. Có bao nhiêu tập con A của X thỏa mãn điều kiện: Không tồn tại a, b thuộc A sao cho |a-b| thuộc {1, 3}? |
The Following User Says Thank You to namdung For This Useful Post: | ngoctuansp (08-10-2010) |
08-10-2010, 12:15 AM | #12 |
+Thành Viên+ Tham gia ngày: Sep 2010 Bài gởi: 392 Thanks: 135 Thanked 247 Times in 159 Posts | Em mới lớp 10 thôi, lại bị trùng giờ nên không tham gia seminar đc. Tuy thế nhưng vẫn cố "bon chen" đóng góp một bài (mới học): Cho $n \in \mathbb{N*} $; $X = \left \{ 1, 2, ... n \right \} $. Đếm số hàm $f : X \rightarrow X $ thoả $f(f(n)) = n \forall n \in X $. Bài này hơi đơn giản. Nên theo thiển ý của em, thầy cô làm seminar có thể tìm một số bài khác trong chủ đề "đếm số hàm $f $ thoả" để làm seminar phong phú hơn. Thầy ngoctuansp biết cuốn "A Path to Combinatorics for undergraduates" của Titu Andreescu chưa ạ? Nếu chưa thì trên đà "bon chen", em đề cử với thầy 5 định lí, 14 ví dụ và 12 bài tập trong chương Recursion. Đương nhiên là không thể tránh khỏi có một số bài cùng chủ đề / cùng ý tưởng với những bài các thầy cô anh chị đã đóng góp. Tuy vậy, vẫn còn nhiều bài lạ và hay (một số ví dụ + bài tập có thể do chính tác giả sáng tác), và quan trọng hơn, hầu hết các ví dụ đều có đến 2 solution. PR cho cuốn sách ghê quá Tất nhiên đó chỉ là ý kiến của cá nhân em, quyền tuyển lựa và quyết định là ở thầy Link down ebook : [Only registered and activated users can see links. ] (xin lỗi anh huynhcongbang vì tội "đạo link" của anh ). thay đổi nội dung bởi: avip, 08-10-2010 lúc 05:46 PM |
The Following User Says Thank You to avip For This Useful Post: | ngoctuansp (08-10-2010) |
09-10-2010, 10:22 PM | #14 |
+Thành Viên+ Tham gia ngày: Feb 2010 Bài gởi: 29 Thanks: 9 Thanked 31 Times in 16 Posts | |
10-10-2010, 08:16 PM | #15 |
Administrator | Seminar đã diễn ra rất hấp dẫn với phần trình bày của thầy PNTuan. Thông qua các ví dụ, thầy Tuấn đã dẫn dắt các thành viên seminar tìm hiểu phương pháp đếm bằng truy hồi, chủ yếu qua các kỹ thuật: 1) Phân hoạch, chia thành bài toán nhỏ 2) Sử dụng bài toán liên hợp Các ví dụ đã sử dụng 1. Bài toán tháp Hà Nội 2. Cho lục giác đều ABCDEF có tâm O được nối với các đỉnh của lục giác bởi các bán kính. Đếm số đường đi độ dài n xuất phát từ O và kết thúc ở O. 3. (Thụy Sĩ 2007). Cho X = {1, 2, ..., 2n}. Tìm số các tập con A của X thỏa mãn điều kiện: không tồn tại hai phần tử x, y thuộc A sao cho x + y = 2n+1. 4. (Bulgaria 1995) Tìm số các hoán vị $(a_1, a_2, ..., a_n) $ của (1, 2,...,n) sao cho tồn tại duy nhất một chỉ số i thỏa mãn điều kiện $a_{i+1} < a_i $. 5. (VMO) n giác đều được chia thành n tam giác nhỏ bởi các bán kính. Hỏi có bao nhiêu cách tô các tam giác này bằng k màu sao cho 2 tam giác có chung cạnh được tô khác màu. 6. (ĐHKHTN 2010) 7. (Canadian MO 2008, bài 5) Thầy Tuấn sẽ trình bày chi tiết thành chuyên đề để gửi lên diễn đàn sau. Seminar sẽ được tiếp tục vào ngày 24/10 và 7/11 với các chủ đề sau: 24/10: Các bài toán về nghiệm của đa thức (Lê Phúc Lữ và K0) 7/11: Về các cuộc thi Toán ở Nga và các nước thuộc LX cũ (Trần Nam Dũng) |
Bookmarks |
|
|