Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Sơ Cấp > Thông Tin

News & Announcements

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é !

* Nội quy MathScope.Org

* Một số quy định chung !

* 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

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 30-09-2010, 10:23 PM   #1
ngoctuansp
+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?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
ngoctuansp is offline   Trả Lời Với Trích Dẫn
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)
Old 30-09-2010, 10:57 PM   #2
nguyentatthu
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:
Nguyên văn bởi ngoctuansp View Post
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?
Đây là một chủ đề khá hay. Mình xin đóng góp vài bài
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 $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
nguyentatthu is offline   Trả Lời Với Trích Dẫn
The Following 2 Users Say Thank You to nguyentatthu For This Useful Post:
king_k0m_n (07-10-2010), ngoctuansp (01-10-2010)
Old 01-10-2010, 04:47 AM   #3
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
Đế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!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
Sự im lặng của bầy mèo
huynhcongbang is offline   Trả Lời Với Trích Dẫn
Old 01-10-2010, 01:48 PM   #4
n.t.tuan
+Thành Viên+
 
n.t.tuan's Avatar
 
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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
T.
n.t.tuan is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to n.t.tuan For This Useful Post:
ngoctuansp (09-10-2010)
Old 02-10-2010, 07:35 PM   #5
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,343
Thanks: 209
Thanked 4,066 Times in 778 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
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:
Nguyên văn bởi nguyentatthu View Post
Đây là một chủ đề khá hay. Mình xin đóng góp vài bài
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 $
Lâu ngày không thấy Thu lên SG. Bận làm ăn quá phải không? Hay lại bị em nào bắt cóc rồi?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: namdung, 02-10-2010 lúc 07:38 PM Lý do: Tự động gộp bài
namdung is offline   Trả Lời Với Trích Dẫn
Old 03-10-2010, 07:25 PM   #6
huaminhtuan
+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
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
huaminhtuan is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to huaminhtuan For This Useful Post:
ngoctuansp (08-10-2010)
Old 03-10-2010, 08:35 PM   #7
Galois_vn
+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)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Galois_vn is offline   Trả Lời Với Trích Dẫn
Old 03-10-2010, 10:50 PM   #8
Highschoolmath
Moderator
 
Highschoolmath's Avatar
 
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ự ^^
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
As long as I live, I shall think only of the Victory......................
Highschoolmath is offline   Trả Lời Với Trích Dẫn
Old 03-10-2010, 10:54 PM   #9
Kratos
+Thành Viên+
 
Tham gia ngày: Nov 2009
Đến từ: Toán 0912, PTNK, Tp.HCM
Bài gởi: 87
Thanks: 25
Thanked 160 Times in 73 Posts
Gửi tin nhắn qua Yahoo chát tới Kratos
Trích:
Nguyên văn bởi Highschoolmath View Post
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ự ^^
Seminar sẽ được tổ chức vào 8h30 sáng ngày 10/10 tại phòng A702, trường Phổ thông Năng Khiếu, 153 Nguyễn Chí Thanh, F9, Q5, Tp.HCM.

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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
Kratos is offline   Trả Lời Với Trích Dẫn
Old 06-10-2010, 02:16 PM   #10
nguyentatthu
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:
Nguyên văn bởi namdung View Post


Lâu ngày không thấy Thu lên SG. Bận làm ăn quá phải không? Hay lại bị em nào bắt cóc rồi?
Chào anh! Lâu nay ở trường nhiều việc nên không thoát được anh ah! Chủ nhật này em cũng lên dự semina. Hy vọng sẽ gặp anh
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
nguyentatthu is offline   Trả Lời Với Trích Dẫn
Old 07-10-2010, 06:20 PM   #11
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,343
Thanks: 209
Thanked 4,066 Times in 778 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
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}?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
namdung is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to namdung For This Useful Post:
ngoctuansp (08-10-2010)
Old 08-10-2010, 12:15 AM   #12
avip
+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 ).
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: avip, 08-10-2010 lúc 05:46 PM
avip is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to avip For This Useful Post:
ngoctuansp (08-10-2010)
Old 09-10-2010, 02:45 PM   #13
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,343
Thanks: 209
Thanked 4,066 Times in 778 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
Ngày mai sẽ có cà phê Toán học và giới thiệu sách, tài liệu mới (và rất cũ).
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
namdung is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to namdung For This Useful Post:
Lan Phuog (09-10-2010)
Old 09-10-2010, 10:22 PM   #14
No Problem
+Thành Viên+
 
Tham gia ngày: Feb 2010
Bài gởi: 29
Thanks: 9
Thanked 31 Times in 16 Posts
Trích:
Nguyên văn bởi namdung View Post
Ngày mai sẽ có cà phê Toán học và giới thiệu sách, tài liệu mới (và rất cũ).
zậy mai thầy không dạy ở CLB hả thầy ? mà mai con nghe nói có bài kiểm tra cho CLB phải ko thầy?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
No Problem is offline   Trả Lời Với Trích Dẫn
Old 10-10-2010, 08:16 PM   #15
namdung
Administrator

 
Tham gia ngày: Feb 2009
Đến từ: Tp Hồ Chí Minh
Bài gởi: 1,343
Thanks: 209
Thanked 4,066 Times in 778 Posts
Gửi tin nhắn qua Yahoo chát tới namdung
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)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
namdung is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 08:08 PM.


Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 103.19 k/118.53 k (12.94%)]