B1. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số cách đi lên bậc thang
nếu có thể đi 1 hoặc 2 bước một lần.
B2 Trong một nhóm có 6 người, trong đó có 2 người là bạn hoặc là thù của
nhau. Chứng tỏ rằng luôn tìm được một nhóm có ba người là bạn hoặc là thù của
nhau
B3 Cho tập hợp X gồm 7 phần tử, X = {1, 2, 3, 4, 5, 6, 7}, anh (chị) hãy chỉ ra
cách tìm tập con kế tiếp của tập 4 phần tử {3, 4, 5, 7}
giải chi tiết giúp mình nhá
B!: Gọi $a_{n}$ là số cách bước lên cầu thang $n$ bậc thỏa đề bài. Bắt đầu bước lên cầu thang ta có 2 TH:
- Đi 1 bậc: có $a_{n-1}$ cách.đi các bậc thang còn lại.
- Đi 2 bậc: có $a_{n-2}$ cách.đi các bậc thang còn lại.
Theo qui tắc cộng, ta có hệ thức truy hồi:
$a_{n}=a_{n-1}+a_{n-2}$; $n> 2$; đk khởi tạo: $a_{1}=1, a_{2}=1$
B2: Để dễ hình dung ta biểu diễn 6 người là 6 điểm trên mặt phẳng, ta nối 2 điểm bất kỳ bằng đoạn thẳng xanh ( tượng trưng quan hệ là bạn) hoặc màu đỏ ( tượng trưng quan hệ là thù). như vậy bài toán đã cho trở thành: Cho 6 điểm trên mặt phẳng, 2 điểm bất kỳ được nối với nhau bởi 1 đoạn thẳng màu xanh hoặc màu đỏ. Chứng minh rằng tồn tại 3 điểm mà các đoạn thẳng nối chúng cùng màu.
Gọi A là 1 điểm bất kỳ trong 6 điểm, Vì các đoạn thẳng nối A với 5 điểm chỉ có 1 trong 2 màu xanh hoặc đỏ cho nên, theo nguyên lý Dirichlet, sẽ có 1 màu xuất hiện ít nhất 3 lần. WLOG, giả sử A nối với B, C, D bằng 3 đoạn thẳng màu xanh.
Nhận thấy:
Nếu BC, CD, BD là màu xanh thì lần lượt các tam giác ABC, ACD, ABD đều là các tam giác có các cạnh là màu xanh.và ngược lại, nếu cả 3 cạnh BC, CD, BD không là màu xanh thì tam giác BCD có các cạnh là màu đỏ. Điều này chứng tỏ rằng luôn luôn tồn tại 3 điểm mà các đọan thẳng nối chúng cùng màu.
B3: Ta có thể dùng phương pháp liệt kê theo thứ tự từ điển để tìm sinh tổ hợp chập $k$ của tập $X$ có $n$ phần tử. Có thể xây dựng tổ hợp liền sau tổ hợp $a_{1}a_{2}...a_{k}$ bằng cách : trước hết, tìm phần tử đầu tiên $a_{i}$ trong dãy đã cho từ phải qua trái sao cho $a_{i}\leq n-k+i$; sau đó thay $a_{i}$ bằng $a_{i}+1$ và các phần tử phía sau cộng dồn 1 đơn vị. Cụ thể:
Trong bài toán này thì $k=4$ và $n=7$. Ta thấy, từ phải qua trái $a_{3} =5$ là số hạng đầu tiên của tổ hợp thỏa điều kiện $a_{i}\leq 7-4+i$ (mặc dù trước đó $a_{4}=7$ đã thỏa đk này nhưng do đã đạt giá trị max nên không tăng được nữa). Để nhận được tổ hợp tiếp theo sau ta tăng $a_{i}$ lên 1 đơn vị, tức $a_{3}=6$ và đặt $a_{4}=6+1=7$. Vậy tổ hợp liền sau tổ hợp $\left \{ 3,4,5,7 \right \}$ là tổ hợp $\left \{ 3,4,6,7 \right \}$.
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 03-06-2021 - 01:30