Tìm số tất cả các tập hợp con khác rỗng của tập ={1,2,...,n} sao cho trong mỗi tập con đó không có hai số nào liên tiếp nhau.
Lại là bài tập hợp
Bắt đầu bởi HUYVAN, 08-08-2006 - 08:09
#1
Đã gửi 08-08-2006 - 08:09
#2
Khách- thachpbc_*
Đã gửi 08-08-2006 - 17:10
Bài này quy nạp theo n là ra ngay.
#3
Đã gửi 09-08-2006 - 19:28
Bạn post lời giải lên đi!Bài này quy nạp theo n là ra ngay.
#4
Đã gửi 10-08-2006 - 08:47
Ký hiệu http://dientuvietnam...mimetex.cgi?f(n) là số tập con của http://dientuvietnam...mimetex.cgi?S_n mà không có hai số nào liên tiếp nhau. Ta phải tìm một hệ thức truy hồi cho dãy http://dientuvietnam...mimetex.cgi?f(n). Vậy là xong
The only way to learn mathematics is to do mathematics
#5
Đã gửi 10-08-2006 - 16:33
Tìm hệ thức truy hồi đó như thế nào?Ký hiệu http://dientuvietnam...mimetex.cgi?f(n) là số tập con của http://dientuvietnam...mimetex.cgi?S_n mà không có hai số nào liên tiếp nhau. Ta phải tìm một hệ thức truy hồi cho dãy http://dientuvietnam...mimetex.cgi?f(n). Vậy là xong
#6
Đã gửi 10-08-2006 - 20:39
gọi tập các tập con của http://dientuvietnam...mimetex.cgi?S_n thỏa mãn là http://dientuvietnam...imetex.cgi?X_n. Xét một tập http://dientuvietnam...n/mimetex.cgi?X thuộc http://dientuvietnam...imetex.cgi?X_n. Nếu phần tử lớn nhất của http://dientuvietnam...n/mimetex.cgi?X bằng http://dientuvietnam...n/mimetex.cgi?n thì http://dientuvietnam...n/mimetex.cgi?X không chứa http://dientuvietnam...mimetex.cgi?n-1 suy ra http://dientuvietnam...metex.cgi?X/{n} thuộc http://dientuvietnam...tex.cgi?X_{n-2}, trường hợp còn lại http://dientuvietnam.net/cgi-bin/mimetex.cgi?X thuộc http://dientuvietnam.net/cgi-bin/mimetex.cgi?X_{n-1}. Thành thử ta có công thức truy hồi http://dientuvietnam.net/cgi-bin/mimetex.cgi?f(n)=f(n-1)+f(n-2)
không thể online nhiều được nữa, hẹn gặp lại diễn đàn trong một ngày gần đây
#7
Đã gửi 11-08-2006 - 16:11
Chỗ này là sao?suy ra http://dientuvietnam...metex.cgi?X/{n} thuộc http://dientuvietnam...tex.cgi?X_{n-2}
#8
Đã gửi 11-08-2006 - 16:41
Bài toán tổng quát:Cho số nguyên dương http://dientuvietnam...n/mimetex.cgi?k tìm số tập hợp con http://dientuvietnam...n/mimetex.cgi?A của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1,2,...,n\} sao cho không có hai phần tử http://dientuvietnam...n/mimetex.cgi?p và http://dientuvietnam...mimetex.cgi?k=1 là bài toán ban đầu của bạn.
Bây giờ với mỗi tập http://dientuvietnam...n/mimetex.cgi?A có tính chất trên thì ta sắp thứ tự các phần tử trong http://dientuvietnam...n/mimetex.cgi?A là http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{p_1<p_2<...<p_m\}. Khi đó ta có http://dientuvietnam...gi?q_i=p_i-(i-1)k ta có http://dientuvietnam...cgi?q_{i 1}>q_i suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?B=\{q_1;q_2;...;q_m\} là tập con của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1;2;...;n-(m-1)k\}.
Như vậy có tất cả tập con
Bây giờ với mỗi tập http://dientuvietnam...n/mimetex.cgi?A có tính chất trên thì ta sắp thứ tự các phần tử trong http://dientuvietnam...n/mimetex.cgi?A là http://dientuvietnam.net/cgi-bin/mimetex.cgi?A=\{p_1<p_2<...<p_m\}. Khi đó ta có http://dientuvietnam...gi?q_i=p_i-(i-1)k ta có http://dientuvietnam...cgi?q_{i 1}>q_i suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?B=\{q_1;q_2;...;q_m\} là tập con của http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1;2;...;n-(m-1)k\}.
Như vậy có tất cả tập con
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh