Đến nội dung

Hình ảnh

Số fibonacci trong tổ hợp

- - - - -

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
OldMemories

OldMemories

    Hạ sĩ

  • Thành viên
  • 53 Bài viết

$1$ . Cho $n \in \mathbb{N}*$ và $S = \left \{ 1,2,....,n \right \}$ . Gọi $c_{n}$ là số các tập con của S chỉ chứa đúng 2 số nguyên dương liên tiếp . Chứng minh rằng : $c_{n}= \frac{2nF_{n+1}-(n+1)F_{n}}{5}$ với $F_{n}$ là số Fibonacci thứ n

$2$ . Cho 2000 học sinh tham gia 1 cuộc thi trắc nghiệm gồm 5 câu hỏi , mỗi câu hỏi có 4 phương án trả lời , mỗi học sinh chỉ được chọn 1 trong 4 phương án . Tìm $n \in N$ bé nhất sao cho các học sinh có thể làm bài thi theo cách nào đó mà cứ n học sinh thì luôn tìm được 4 học sinh để 2 học sinh bất kì cũng có bài làm khác nhau ở ít nhất 2 câu



#2
NHoang1608

NHoang1608

    Sĩ quan

  • Thành viên
  • 375 Bài viết

1. Bổ đề: Số các tập con không 2 phần tử liên tiếp của $S={1,2,..,n}$ là $F_{n}$ với $F_{n}$ là số $Fibonacci$ thứ $n$.

  Chứng minh.

Đặt $A_{n}$ là số tập con không chứa 2 phần tử liên tiếp nào của tập $S={1,2,...,n}$

Xét các tập con thỏa mãn không chứa $n$ thì các tập này là tập con của $S={1,2,...,n-1}$

 $\Rightarrow$ có $A_{n-1}$ tập con thỏa.

Xét các tập con thỏa mãn chứa $n$ thì tập có dạng ${a_{1},a_{2},....,a_{k},n}$ 

Thấy rằng $a_{1},a_{2},...,a_{k}$ không chứa $n-1$ và là tập con của $S={1,2,....,n-1}$ đồng thời không chứa 2 phần tử nào liên tiếp

 $\Rightarrow$ có $A_{n-2}$ tập con thỏa.

Vậy $A_{n}=A_{n-1}+A_{n-2}$ suy ra $A_{n}= F_{n}$ nên số tập con thỏa mãn bài toán là $F_{n}$.

 

Xét $S={1,2,....,n}$ 

Xét 3 loại tập con: loại 1 là các tập con chứa $n,n-1$, loại 2 chứa $n$ nhưng không chứa $n-1$, loại 3 không chứa $n$

Loại 1 có $F_{n-2}$ tập con.

Loại 2 có $c_{n-2}$ tập con.

Loại 3 có $c_{n-1}$ tập con.

Vậy $c_{n}=c_{n-1}+c_{n-2}+F_{n-2} \Rightarrow c_{n}= \frac{ 2nF_{n+1} - (n+1)F_{n}}{5}$ với $F_{n}$ là số Fibonacci thứ n.

2. Hướng đi: Chứng minh $n=25$ là số nhỏ nhất thỏa mãn.


Bài viết đã được chỉnh sửa nội dung bởi NHoang1608: 07-10-2017 - 09:12

The greatest danger for most of us is not that our aim is too high and we miss it, but that it is too low and we reach it.

----- Michelangelo----


#3
IHateMath

IHateMath

    Thượng sĩ

  • Thành viên
  • 299 Bài viết

2. (CMO 2000, Q6)






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh