Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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
  • Giới tính:Không khai báo
  • Đến từ:Ninh Binh
  • Sở thích:Number theory , Geometry

Đã gửi 05-06-2015 - 19:39

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
  • Giới tính:Nam
  • Sở thích:Bất đẳng thức , Tổ Hợp .

Đã gửi 06-06-2015 - 10:35

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
  • Giới tính:Không khai báo
  • Đến từ:Ninh Binh
  • Sở thích:Number theory , Geometry

Đã gửi 06-06-2015 - 11:56

 

 

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 

 






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

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