Đến nội dung

Hình ảnh

Tìm số hoán vị $a_{1},a_{2},...,a_{n}$ của tập $\left \{ 1;2;...;n \right \}$

- - - - - truy hồi

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

#1
Belphegor Varia

Belphegor Varia

    Thượng sĩ

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

Dùng quan hệ truy hồi để giải : 
Bài 1: Tìm số tập con từ tập 
$\left \{ 1;2;...;n \right \}$ thỏa mãn : mỗi tập có đúng 3 phần tử và tổng các phần tử chia hết cho 3
 

Bài 2 : Tìm số hoán vị $a_{1},a_{2},...,a_{n}$ của tập $\left \{ 1;2;...;n \right \}$ thỏa mãn $1\leq \left | a_{i}-i \right |\leq 2$ ,với mọi $i=\overline{1,2,...,n}$ ( VMO 2003A - TC THTT)


Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 06-06-2015 - 11:54

$ \textbf{NMQ}$

Wait a minute, You have enough time. Also tomorrow will come 

Just take off her or give me a ride 

Give me one day or one hour or just one minute for a short word 

 


#2
khanghaxuan

khanghaxuan

    Trung úy

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

Bài 1 :  Ta xét 3 trường hợp : $\left\{\begin{matrix} n=3k & & \\ n=3k+1 & & \\ n=3k+2 & & \end{matrix}\right.$

Mình lấy ý tưởng cho trường hợp $=3k$ thôi nhé :)) (Các TH khác có lẽ tương tự :P )
Vì $n=3k$ nên $n+1=3k+1$ nên gọi $a_{n}$ là số tập con cần tìm tại $n$

Nếu ta thêm một số $n+1$ thì số đó phải là số chia 3 dư 1 . Do đó $a_{n+1}$ sẽ có 2 khả năng : 

- KN1 : Không chứa số $n+1$ thì ta sẽ có $a_{n}$ số tập con

-KN 2 : Tập có chứa số $n+1$ , hơn nữa vì tổng các phần tử chia hết cho 3 nên hai phần tử còn lại có thể là : $\left\{\begin{matrix} 3k & \\ 3k+2 & \end{matrix}\right.V\left\{\begin{matrix} 3k+1 & \\ 3l+1 & \end{matrix}\right.$

Mà ta đã có n chia hết cho 3 nên ta dễ dàng tìm được số bộ các số trên 

Ý tưởng là như thế :)) 

Spoiler

 

Bài 2 : Thấy nó sao sao ấy :huh:


Điều tôi muốn biết trước tiên không phải là bạn đã thất bại ra sao mà là bạn đã chấp nhận nó như thế nào .

- A.Lincoln -

#3
Belphegor Varia

Belphegor Varia

    Thượng sĩ

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

 

 

Bài 2 : Thấy nó sao sao ấy :huh:

Đã sửa đề bài  :P


$ \textbf{NMQ}$

Wait a minute, You have enough time. Also tomorrow will come 

Just take off her or give me a ride 

Give me one day or one hour or just one minute for a short word 

 






Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: truy hồi

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

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